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

Автор Sumanto, 4 года назад, По-английски

https://cses.fi/problemset/task/1625 I am applying staright forward DFS to the problem but it's getting Time Limit Exceeded. How to optimise the code. I checked out William Lin's Livestream but did'nt get his approach to the problem

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

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://cses.fi/book/book.pdf page 52 (the printed page number) or 62 (the pdf page number)

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

    i understood the optimisations, but can you explain the runtime mathematically? the explanations there looks more experimental.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone with a sharp eye help me please? I basically tried “to go by the the book”, and do the pruning of the T-shaped wall hits, — just as @tmwilliamlin168 does for this problem in his epic 11-hour stream.

Still, however, I'm getting 30+ seconds on the all-question-marks 88418 paths case. What am I missing? I tried to code it up in a clean way, so you probably won't have any trouble following the logic.

Thanks!

The code
  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    So, seems like, the constraints are really tight, and the constant factor caused by all the nice code factorizations was simply killing it. After I unrolled all the DRY-ness, and uglified the code to the point listed below, it got accepted.

    UPD: Ah, btw, the absolute numbers in seconds I quoted above are not quite representative, as I ran the code with memory sanitization, and all the optimizations disabled. So, it should be, like, 7 times faster, when run by the OJ.

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

      I have also tried many optimization but still getting TLE after spending too much time on the problem. If could you please suggest me some improvements

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

        It doesn't seem like the code is pruning the impossible paths early enough. Am I right, that it recurs until it runs out of moves, or hits the end point?

        Did you read “Pruning the search” section starting from the page 51 of the CSES book?

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

          the moveTo method is doing the pruning part as mentioned in the book. whenever I reach the boundary I avoid atleast one direction of movement.

          Other optimization which I have done is the generalized part as mentioned in the book. Though I am not sure the way I have implemented is correct or not.

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

            Ah! I see, indeed. So, right, there's pruning in case of hitting a wall. For me it was not enough. It was also necessary to prune when hitting an already visited cell, and forming a T-shape, not just a T-shape on the boundary.

            x--x
            |  |
            x->|
               x--
            
            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              I have handled that too, by using the concept of direction. For each cell I have stored the direction from which I have arrived that cell, and in case (the one which you have mentioned about) suppose I reach cell (i, j) and I notice that cell (i, j+1) is already visited so in that case I have only two directions to move, out of which only one direction is good. I tried some examples and deduced that the direction which is not favourable is the direction specified by me in proceed() method [which is the direction of arrival at that cell]. so if up direction is stored in direction[i, j+1] then I will avoid going upwards from cell (i, j). I think that's what you mean by the T-shape. I am not sure if my way of handling is inappropriate or it is just time consuming.

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

                Oh… Ok.

                Could it be that in such a case — $$$(i, j + 1)$$$ visited, you shouldn't even consider visiting the $$$(i, j)$$$?

                Here's my code handling that exact situation:

                if ((pattern[i] == '?' || pattern[i] == 'R') &&
                    is_possible(covered, ro, co + 1)) { // R
                    bool locked = !is_possible(covered, ro, co + 2) &&
                                  is_possible(covered, ro - 1, co + 1) &&
                                  is_possible(covered, ro + 1, co + 1);
                
                    if (!locked) {
                        covered[ro][co + 1] = true;
                        recur(pattern, ans, covered, i + 1, ro, co + 1);
                        covered[ro][co + 1] = false;
                    }
                }
                

                So, if $$$(i, j + 1)$$$ is visited, and the path would form a T-shape, I don't even go from $$$(i, j - 1)$$$ to $$$(i, j)$$$. The $$$locked$$$ boolean here means “there would be a T-shape”.

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

                  thought of something like that but got confused regarding the correctness. Thanks by the way!!

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

                  one update!! I did one more optimization which is if somehow I have created an Island of zeroes surrounded by ones in the matrix then again the answer is not possible. For that I am doing an explicit dfs for checking the number of connected components with zeroes if such number is greater then one then the answer is not possible in such case and we need to do backtrack rather than moving on. But still I am getting TLE on some cases.

                  updated code (10/20 testcases passed)
»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I've done the optimizations but still TLE, it turned out switching from

vector<vector<bool>> seen(7, vector<bool>(7, false));

to

bool seen[7][7]; memset(seen, false, sizeof(seen));

Made the difference from TLE on 5 testcases (including all '?') to getting AC. This sucks because I hate memset :P