Walk on the Grid

Hasinur_ Criterion 2021 Round 11

Alternate Writer upobir(Sabbir Rahman) came up with a nice solution.

If we choose A and B such that $A + B - 1 = L$ then the functions can be defined as:

$F(A,B)$ = $(R-A+1)\times (C-B+1)$

$G(A,B)$ = ${L-1}\choose{A-1}$

We can also write $F(A,B) = F(A,L-A+1)$ and $G(A,B) = G(A,L-A+1)$

It can be proved that log of the above functions are ternary searchable, so log of $F(A,B)\times G(A,B)$ is ternary searchable also.

Time complexity: $\mathcal{O}(T\times \log_\frac{2}{3}{L})$

Space complexity: $\mathcal{O}(L)$



39% Solution Ratio
sansaquaEarliest, Mar '21
sajib_readdFastest, 0.1s
Matrix.codeLightest, 3.1 MB
amurtoShortest, 2075B
Toph uses cookies. By continuing you agree to our Cookie Policy.