Блог пользователя Swistakk

Random Walk: Hard version
Автор Swistakk, история, 9 лет назад, По-английски

Hi!
On recent OpenCup — Makoto Soejima Contest 4, problem "Random Walk" was posed. We were requested to determine the expected number of visited cells after n steps of random walk on a plane — in each move from (i, j) we go either to (i+1, j), (i-1, j), (i, j+1) or (i, j-1) — all with prob 1/4. More precisely, we needed to output , where M was some integer. In this problem constraint was n ≤ 5000. Actually, this problem becomes much more interesting if we try to solve it for n ≤ 105 in a reasonable time (assume M = 109 + 7 for simplicity). Can you see the solution (if I'm not mistaken — it exists)?

  • Проголосовать: нравится
  • +80
  • Проголосовать: не нравится

»
9 лет назад, # |
← Rev. 4   Проголосовать: нравится +18 Проголосовать: не нравится

I have a solution with complexity . We have the following O(n2) solution:

,

,

.

Let's calculate zk using sqrt-decomposition, so

, where b is the position of the start of block. The first sum we can calculate for all k after each block using FFT. So we have complexity from the above .

Working time for n = 105 is 14.12s, but it's not optimized, so it can be decreased a lot. Code.

UPD: Actually it works in time , so for we have

→ Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    It seems that I understand how to speed up your solution to . Basically, we have two arrays. One is known beforehand (wi), elements of other are revealed to us one by one (zi) and we want to find their convolution. Solution to this problem can be seen here (check editorial of problem Div 1 E).

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, that's the approach I had in my mind :). If put in other words, problem we are dealing with is finding an inverse () of a generating function and such approach leads to complexity, whereas straightforward computations of course give O(n2).

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +20 Проголосовать: не нравится

      Actually today I was solving CF309 in a virtual mode and right before I seen this blog entry I was trying to solve the problem E using the same technique as here 16036613 (without editorial) and it got TL. It seems I should look at the editorial the improve my solutions for both problems :-)

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Got it. Very nice idea. Both my solutions with sqrt-decomposition and that idea gives the answer modulo 109 + 7 352371679 for n = 105. The second one works in time 7s.

      → Ответить
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    Glad that you gave this probem a shot and indeed that's a good direction, however there are still some issues. First of all w2k should be equal to , but you got it right in your code :). If length of block was taken with more care, I think we can achieve using the same approach, however my solution runs in .

    For those, who are not familiar with basic version of this problem, wk was meant to be number of paths of length k which end up in their start position and zk is number of paths of length k that do not ever visit their start position again. Presented formula for wk is really nice, but also hard to derive, observing it is a significant part of improving running time (for n ≤ 5000 it can be simply bruteforced by fixing number of horizontal moves), I encourage readers not familiar with this to think a while about it :).

    → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      If I'm not mistaken, we need to calculate this sum:

      After reducing some factorials we have:

      For calculating we can say, that it's coefficient of the monomial xmyk - mxk - myk = xkyk in (x + y)k(x + y)k, which is obviously

      Am I right?

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks. I fixed the formula. I was in a hurry so I didn't have time to find the optimal size for the block. Now I updated it.

      → Ответить
    • »
      »
      »
      9 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

      It's easy to prove the formula for wk: we can assign the signs (plus/minus) to the directions in a ways and also we can assign the axis (x or y) to the directions in a ways, so we have .

      UPD: There is a mistake in proof see the comment below.

      → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
        ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

        That's a bit more complicated. Before that, we need to rotate whole coordinate system by 45 degrees and instead of considering coordinates (x, y) we need to look at (x + y, x - y), which I consider really tricky and insightful. Before rotating changes are of type ( + , 0), ( - , 0), (0,  + ), (0,  - ) and after rotating they are exactly what you wanted to ( + ,  + ), ( + ,  - ), ( - ,  + ), ( - ,  - ) (which was basically whole difficulty in problem C5 on Petrozavodsk, which was solved just by 6 teams).

        → Ответить
        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Of course you are right, I hurried one more time). On one of the problem analysis in Petrozavodsk this winter aid uses the same trick with rotating of coordinate system.

          → Ответить
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        Btw, I learned that rotating trick from this problem: http://mirror.codeforces.com/contest/538/problem/G

        → Ответить