Editorial for New Year's '18 P8 - Snowy Streets

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: r3mark

For the first subtask, each square has two states: either it can be visited from (1, 1) or it can't. Also, a square will only change states at most once. Then we can DFS to change the states whenever a square becomes blocked.

Time Complexity: \mathcal O(Q+RC)

For the second subtask, we use the same idea as the first subtask. The only difference is that we need to handle the type 1 operations better. To do this, keep an RMQ segment tree on each row of the grid and lazily update it for each type 1 operation. Then, find the maximum to check whether or not any of the squares in a row became blocked. If so, then you update the blocked squares with -\infty so that they never show up again.

Time Complexity: \mathcal O(QR\log C + RC\log C + RC)

For the final subtask, keep track of when a square becomes blocked and call this the square's value. The type 2 operations will be answered offline. Call the distance between two squares the minimum value on a path from one to the other. For each square on the middle column, determine the maximum distance from it to every other square. Then, split the grid into two halves along that column. For each of these two new grids, repeat the process. This entire process takes \mathcal O(R^2C\log C). With these computed numbers, the maximum distance (which can be used to easily determine the answer) for any type 2 operation can be found in \mathcal O(R). This is done by finding a portion of the grid where one of the squares in the query is on one half of the grid and the other square is on the other half. Then, the computed distances to those two squares from each square of the corresponding middle column can be merged.

Time Complexity: \mathcal O(QR\log C + RC\log C + R^2C\log C + QR)

Comments


  • 2
    mmaxio  commented on Jan. 4, 2018, 8:26 p.m. ← edited

    There is also an easy \mathcal{O}(QRC / 64) online solution to type-2 queries with bitset (R \le 50 makes it even easier).


  • 1
    SamZhangQingChuan  commented on Jan. 4, 2018, 10:04 a.m. ← edit 5

    Could you plz give more details on the solution for subtask 1? I'm not sure how to dfs so that the overall complexity is \mathcal{O}(Q+RC).

    I understand the last solution tho...Thanks for proposing the problem.

    nvm, I get it now.

    The test cases of subtask 2 is too weak btw. I passed with an \mathcal{O}(QRC) solution. https://dmoj.ca/submission/733056


  • 0
    NT_AUTHORITY_SYSTEM  commented on Jan. 3, 2018, 2:35 a.m. ← edit 3

    EDIT: Nevermind, this doesn't work, but it's still an interesting algorithm nonetheless

    There is an alternate, simpler solution to this problem

    Keep a 2d array to represent the amount of snow

    For type 1 operations, simply brute force

    For type 2 operations, keep 2 stacks for DFS and a 2d visited array

    Push onto one stack when moving down, and the other stack when moving to the right

    Here a wall is defined as the boundaries of the rectangle (a,b) (c,d), where (a,b) is the source and (c,d) is the destination

    When you run into a wall or a visited node while moving right, clear the "right" stack

    When you run into a wall or a visited node while moving down, clear the "down" stack

    When popping, pop from the stack with the most recently pushed element

    If one stack is empty, obviously don't pop from it

    If both stacks become empty without finding a valid path, there is no path

    Calculating the time complexity is left to the reader as an excercise


    • 0
      r3mark  commented on Jan. 3, 2018, 2:38 a.m. ← edited

      This solution is incorrect and runs in \mathcal{O}(QRC) in worst case (your implementation of it runs in \mathcal{O}(QRC\log R \log C) iirc). Since this contest is non-systested, your in-contest submission will not be affected, but I'll be adding new test cases to kill DFS brute-forces soon.


      • 0
        NT_AUTHORITY_SYSTEM  commented on Jan. 3, 2018, 2:56 a.m. ← edited

        Sorry if I trolled you, you see, I've been a problemsetter before and I know how annoying those pesky trolls can be.

        But I think the complexity of my implementation should be \mathcal{O}(QR \log C) for type 1

        As for type 2, I'm not very sure, but I think it is not \mathcal{O}(QRC \log R \log C)

        Querying one square takes \mathcal{O}(\log C) time

        Obviously, it will never visit every square in the rectangle, but I don't know how to calculate how many squares would be visited


        • 0
          r3mark  commented on Jan. 3, 2018, 4:21 a.m. ← edited

          Okay, I've taken a closer look at your solution and it's worst case \mathcal O(QRC\log C) (there are situations where your code visits almost every square). I've also uploaded a few cases to each subtask which your solution both TLEs and WAs on.


          • 0
            NT_AUTHORITY_SYSTEM  commented on Jan. 3, 2018, 7:26 a.m.

            Well, good game I guess. You definitely have the better algorithm.

            I can understand why it TLEs, but do you mind enlightening me as to why it WAs?


    • -4
      Kirito  commented on Jan. 3, 2018, 2:37 a.m.

      This solution only passes because of weak test data. As the contest was not systested, we could not upload a countercase.