Mousa_Aboubaker's blog

A harder version of the problem 1013F, Igor and Mountain
By Mousa_Aboubaker, history, 13 hours ago, In English

when I was solving this problem, I thought that Igor can go directly to any cell in any row above his current row as long as the Euclidean distance between that cell and his current cell is less than or equal to $$$d$$$

but in the last minutes of the contest, I realized that he can only go to any cell in the row that is exactly above him if he can reach it

with this, I found the solution for the problem faster and I got AC

now, I'm wondering, how to solve this problem if Igor can go to any row as long as he satisfies the constraints ?

for example, in the second testcase, Igor can go from the last row to the first row as mentioned in the image above

the result should be 70

how many ways to reach the first row for each X cell

what is the optimal solution for such a problem ?

I'm looking forward to see your ideas and solutions, and thanks ^_^

Tags dp
  • Vote: I like it
  • +18
  • Vote: I do not like it

»
12 hours ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't think it's solvable because the cells that satisfy the distance constraint form half a circle, so each row has a different size so we can't do 2D prefix sum.

→ Reply
  • »
    »
    12 hours ago, # ^ |
    ← Rev. 3   Vote: I like it -8 Vote: I do not like it

    deleted

    → Reply
  • »
    »
    12 hours ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Yup, I thought about 2D prefix sum but found that it won't work

    my idea to solve it is to modify the solution of the original problem by taking the $$$d$$$ rows above the current row, it would be $$$O(n * m * d)$$$ I guess, I'm looking if there is any optimization to reduce this time complexity or no

    → Reply
  • »
    »
    10 hours ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think that the problem is phrased in a way such that the weird condition reduces to a simple perfix sum, it's not intended to be understand as it is. Else, $$$n\leq 2000$$$ is certainly not Div 3 level since solving that might require some very heavy DS (or just plainly unsolvable).

    Yes
    → Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I also misread the problem to be this during the whole contest and failed to solve it (was wondering why div3F was so hard lol). I couldn't think of anything better than $$$O(n \cdot m \cdot d)$$$, although if it's changed to Manhattan distance instead of Euclidean distance then I think it can be solved efficiently using prefix sums on both rows and diagonals.

→ Reply
  • »
    »
    8 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nah, i have to use a fenkiwck tree with range after the contest when i realise my solution was O(n*m*d) T_T

    After the contest, it's works in O(n*m*log(d)), but probably using prefix sum intead of dp can work too... mmmm

    → Reply
  • »
    »
    7 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    FFT?

    → Reply