wuhudsm's blog

By wuhudsm, history, 4 weeks ago, In English

Due to my poor understanding ability, I can't totally understand official editorials of some problems, even after got AC. So I plan to rewrite some of the editorials.

Some principles:

  1. Divide and conquer. Divide a large, hard problem into several smaller, easier problems.

  2. For ease of understanding, use visual expressions as much as possible.

  3. The shorter the better.

If you have any other problems you'd like me to rewrite the editorial for, feel free to let me know in the comments. Also, I believe writing an editorial with your own understanding is a great way to make progress.

Let's go.

1.CF #749 F

Rating: $$$2500$$$

Attempt and Insight
How to prove it?

2.Codechef Simultaneous Robots

Rating:???

Some easy observation
A classical trick
Patch for official editorial (the most interesting part)
Can it be extended to any k?
Another Approach

3.CF #965 E

Rating: $$$2200$$$(easy)/$$$2500$$$(hard)

Solve easy version first
Solve hard version
When we go up, won't we visit too many edges?

4.Hello 2025 D

Rating: $$$2000$$$

Observation1
Trick
Observation2
Classical technique

5.CF #999 E

Rating: ???

Observation1
Observation2
How to prove?
  • Vote: I like it
  • +97
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Thanks for the proof for the Codechef problem today! After some googling, it seems like it's generalized by the vertex-connectivity version of Menger's theorem.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, the maximum number of non-intersecting path is the maximum flow. And Menger's theorem is the same as maximum flow minimum cut theorem.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, but the vertex-connectivity version of Menger's theorem is more immediately useful — all that's needed to prove the problem is to notice that the shortest path DAG can't have a min-vertex-cut of size 1 if there's at least 2 vertices in each level (besides source and sink).

      You don't have to think about constructing the flow graph with 2 new vertices per original vertex anymore, and can think in terms of min-vertex-cuts instead of min-edge-cuts.

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

In Simultaneous Robots :

a[n-1][m] = a[n][m-1] = '.'

Can anyone explain why this part should be true for the answer to exist because in the case where the first robot follows the second robot (for d + 2 seconds as answer) then they both can make the exit through one of a[n-1][m] , a[n][m-1].

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Just do a simulation, you will understand.

    Spoiler
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I initially thought the goal was to reach a[n][m], but I realized my mistake.

      For those brainstorming a solution to this question, here's an explanation:

      If there is a shortest path to a[n][m] that passes through a[n][m-1], then the following sequence of events will occur:

      1) At time d, Robot 2 will reach a[n][m]. 2) At time d+1, Robot 1 will move to a[n-1][m], while Robot 2 will move to a[n][m-1]. 3) At time d+2, both robots will arrive at a[n][m] simultaneously.

      I hope this clears up any confusion!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

D. Gifts Order
E. Kevin and And
Can you rewrite for these two problems?
Thanks in advance!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for writing. Btw, for the Simultaneous Robot's problem, I first found a shortest path. Then I blocked all the squares in the shortest path except top left and bottom right. Then I ran bfs again and if I find another shortest path of same initial length then I conclude there exists two disjoint shortest paths. I can prove till this part. However, if the second bfs can't find shortest path of same initial length, I don't understand why we can say that there exists no two disjoint shortest paths. However, this logic got AC when I submitted. Can you please prove this or it's weak testcases? TIA:)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I also did the same thing and I think this works because there are only 4 directions to walk and every time your order of preference for the direction is same. i.e. dx dy arrays. This makes sure that you are going through corners whenever possible => choosing same direction whenever possible leads you to reach boundaries faster. Hence, your first path cannot cut your to be second path so you can find it just by simulation.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    you got AC? i don't think it should work. i can give you an example where it does not work.

    ..##

    ..##

    ....

    ....

    preferences of directions are down, right, up, left.

    i even tried to give different preferences to my directions. i did not get an AC. could you share your code?

»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Help me with this -

Why are we checking for this - if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || grid[n-1][m-2] == ‘#’ || grid[n-2][m-1] == ‘#’) for unavailability of path.

Instead of this - if(grid[0][1] == ‘#’ || grid[1][0] == ‘#’ || (grid[n-1][m-2] == ‘#’ && grid[n-2][m-1] == ‘#’))

Let’s consider a case - n = 3 m = 3; grid = [[. . #] [. # #] [. . .]] In this case, the answer should be 6, the robot 1 will follow the path of — (0,0)->(1,0)->(2,0)->(2,1)->(2,2) and robot 2 will follow — (0,0)->(0,1)->(0,0)->(1,0)->(2,0)->(2,1)->(2,2) so the answer should be 6 in this case. But the solution its accepting returns -1 for this case. We should only have to check for the starting position because on the first time we move, the robots should be on different cells but for destination we have to check for at least an adjacent open cell of destination cell.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Robots are in the same position after 2 seconds.

    • »
      »
      »
      4 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      See it like this, if we have to move from starting point (0,0) to (n-1,m-1) and if there's path from starting point to destination point or there's many paths but we have to take the shortest one right? So, if there's at least 2 paths of same shortest length then the answer will be the shortest path length 'D' but if not then the other path will be of length 'D+2' as the grid is a kind of bipartite graph.

      After 2 seconds, the robot1 will already move to its path and the robot 2 in that scenario will be at (0,0) and the robot1 will wait for robot2 at the ending cell.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        If I understand correctly, you are saying this:

        Robot 1 moves to (N,M) in D seconds. Robot 2 starts from (1,1) after 2 seconds, following the same path.

        This does not work. Try simulating the idea; you will know why. They will always meet after D+1 seconds.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Can you help me like in the test case which I gave initially or similar test cases like that — after 2 seconds, robot1 will be at (2,0) and the robot2 will be at (0,0) is it incorrect?

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            No, it is correct. Take your example and simulate the process.

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

in Simultaneous Robots i don't understand, how we can get 2 disjoint shortest paths using shortest path tree. please explain?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You only need to determine the existence of 2 disjoint shortest paths. If you want to construct them, you can use the maximum flow algorithm.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      before Patch for official editorial (the most interesting part) in a classic trick you mentioned -> To to find two disjoint shortest paths, we have a classic idea: only walk along the edge of the shortest path tree.

      i have not read below that section.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the explanation of problem Codechef Simultaneous Robots. I tried solving it using Denic's Algorithm and got stuck with TLE here. With the given constraint, the runtime on bipartite graph is $$$O(V\sqrt E)$$$. In one of the worst case we have a grid $$$10^{3}*10^{3}$$$ where total nodes are $$$10^{6}$$$ and total edges(if all paths possible) just $$$4*10^{6}$$$. With these constraints, I don't think it would pass but am interested if anyone solved it using Network Flow Algorithms.

I solved the problem with distance technique shown in the editorial above and thanks for the counter example for $$$k=3$$$ but this is like a trick that you have to remember with limitation $$$k<=2$$$. Network flow logic is more intuitive for me(maybe skill issue XD).

PS: Take everything I said with a huge grain of salt as this is my first time coming across Network Flow.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I wish you would write explanation of 1209E1. I still can't understand official editorial.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

E. Exposition

This one please