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

Автор wrg0ababd, история, 8 лет назад, По-русски
Tutorial is loading...
Tutorial is loading...

Вот ссылка на простую реализацию вышеописанного решения: http://ideone.com/IoSts1

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Проголосовать: нравится
  • +145
  • Проголосовать: не нравится

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

Auto comment: topic has been updated by wrg0ababd (previous revision, new revision, compare).

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +38 Проголосовать: не нравится

И почему ваше решение по G должно работать 6.5 секунд? А мое 26623331 с таким же количеством вершин и ребер — нет?

UPD: выложите, пожалуйста, код авторского решения.

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

    Присоединяюсь. С радостью услышу хоть какие-нибудь соображения, почему авторское решение имеет разумную сложность (где, кстати, его можно почитать?), и чем плохо моё (26623566).

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

    Вот код авторского решения: 26628260

    UPD. pastebin

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

      Недостаточно прав для просмотра запрошенной страницы

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

    Перписал со спарстейбла на ДО, получил OK за 1.6 сек: 26628410. Такое.

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

    Дописал в разбор, почему должно работать.

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

      Если честно, не очень убедительно (или я не понял)

      Кажется, что оценки с корнями возникают, когда пропускные способности единицы

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

        Ну, меня Коля убедил.

        Теорема 1 здесь, если её применить к графу с деревьями отрезков и (внимание) рёбрами на каждый прямоугольник даёт оценку в фаз. Действительно, у нас интересные вершины в такой конструкции это только вершины деревьев отрезков, а у каждой вершины дерева отрезков одна из входящей и выходящей пропускной способности это просто количество вершин в покрываемом ей отрезке, то есть, в сумме получается .

        Кажется очень естественным, что если заменить рёбер на прямоугольник на 2 раза по путём введения фиктивной вершины, то, хоть напрямую оценка и перестаёт работать, из оценки на предыдущем графе следует, что и в таком решении фаз будет .

        Итоговая сложность получается порядка миллиарда условных попугаев, в это хоть как-то можно поверить.

        На спарсах такая оценка правда не работает совсем, и, может быть, поэтому они и ТЛятся.

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

          Да, спасибо, согласен. Сперва неправильно понял, какое утверждение имелось ввиду

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

          Я тут подумал, еще остаётся вопрос, как оценивать время работы одной итерации, потому что если делать всё тупо, то одна итерация может работать вплоть до O(VE).

          Хотя возможность это заабузить сомнительна, но всё-таки

          Или может это тоже уже все знают, как делать?

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

            А, на самом деле, видимо, получается, что одна итерация работает за O(E + V|Fcur|), то есть суммарно то, что мы оценили плюс O(V·|F|) т. е O(n2) в нашем случае.

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

            Да, вопрос не праздный. Я всё время забываю, что есть у нас не единичная, а блокирующий поток ищется за O(E) только в единичных сетях. В данном случае блокирующий поток весьма бодро может проходить несколькими путями по одному и тому же ребру (если это ребро ДО, например).

            KAN, что скажешь?

            UPD всё, я понял, что написал Алексей, звучит разумно. Действительно, к сложности добавляется суммарный множитель в O(V|f|), что есть O(n2), то есть какие-то жалкие 100 миллионов.

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

              А про sparse кто-нибудь что-то понял? Есть какая-то разумная оценка для sparse?

              И какой вывод? Писать ДО всегда, когда видишь такую задачу?

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

                Ну, про sparse понятно только то, что в лоб оценки Карзанова не работают. Никаких работающих разумных оценок я не знаю.

                Видимо, ДО как промежуточная конструкция в такого рода задачах работает получше.

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

          Вроде как вершины прямоугольников независимое (в неориентированном смысле) множество образуют. А нельзя просто такое множество выбросить из расчета потенциала, помножив число итераций на 2? Лемму (1) из текста будем доказывать декомпозицией потока с последующим замечанием, что любой путь не проходит дважды подряд через вершины независимого множества, так что хотя бы l/2 потенциала скушает.

»
8 лет назад, # |
Rev. 5   Проголосовать: нравится +79 Проголосовать: не нравится

Доказательство G в студию? На опенкапе была похожая задача (была ли эта придумана после той?), но ее решение оказалось кукареканьем.

UPD Со ссылкой на викиконспекты стало понятно, откуда это берется. Страно, что эта полезная информация раньше была не сильно известна. Впрочем, для задачи с опенкапа эта оценка совершенно не работает, но там и тесты были с большим временем работы постфактум сделаны.

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

I think Problem D constraints are very bad, because O((n + m) * n ^ 2 * k) solutions passed, but there is O((n + m) * n * k) solution...

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

and using intervals instead of segments

What is the difference between intervals and segments?

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

Можно ли как-то оценить, какой эпсилон нужен в C? Кроме как методом тыка, имея целочисленное решение

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

    Нижняя и верхняя границы интервала это дроби вида p / q со знаменателем порядка 105, значит их разность это дробь со знаменателем порядка 1010. Опуская некоторую лирику, это значит, что можно положить eps = 10 - 11.

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

Откуда такая асимптотика в D? Перебираем за n*n*2*k(левая граница, правая граница, в левой или в правой границе мы сейчас, сколько ходов осталось) все отрезки. Переходы из каждого отрезка находим за n. В итоге O(n^3*k)

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

    Переходы из каждого отрезка находим за n

    Переходы из всех точек совершаются за O(n + m) суммарно. Домножим это на варианты противоположных границ отрезка — O(n), и на глубину рекурсии (количество сделанных переходов, O(k)).

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

      Можно делать переходы из каждого отрезка за n, если хранить ребра в матрице смежности.

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

    Переберем, сколько вершин осталось посетить (k). Переберем левую и правую границы (n2), а также вершину, в которой находимся (n). Переберем ребра, исходящие из текущей вершины (их mi) и осуществим допустимые переходы. Значит, осуществим все действия за , так как посетим все вершины, а суммарно ребер у нас m.

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

For Problem C, making the value of eps more precise changes verdict from WA to AC. But, aren't we supposed to take any difference < 1e-6 as zero, as it is mentioned in the problem statement as well, that even the judge will compare the answers with error limit = 1e-6?

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

    It's not fair, i think, but in statement it says that it compares answers, but not anything else, printing -1 should be very precise :/

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

    The problem is there was a case (40) where using a large epsilon would give -1 but the answer was actually 0.99998999989999903804, so the output is completely off from the answer.

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

I thought that there has to be an equal number of vertices instead of leaves in E. The renaming of "leaves" and "vertices not being leaves" to "offices" and "departments" was strange. ;_;

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

    Problems were confusing to be honest, I fell for it too.

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

    Same! I get that they try to wrap the problem in something so that it doesn't seem boring, but clarity should be the #1 priority always.

    It's a shame as well, I really liked the problem otherwise.

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

I tried the following for problem C:

  1. Find a time Ti for each mice i in which the mice will be in the maze, using ternary search.
  2. Use binary search to find the lower and upper bound of the time, using Ti
  3. Do the intersection of the bounds and take the smallest time.

But I got WA on test 30 because of the precision error. Can you find where I did the mistake? and How to find a good EPS which will meet the requirement.

Submission: http://codeforces.me/contest/793/submission/26625111

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

При n=1 и m=1, как может гарантироватся что символы «S» и «T» встречаются ровно по одному разу?

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

here is my Solution for B i used almost exactly what you mentioned first (naive recursive). passed pretests but got TLE on test 10.

adding the below code passes test 10 but TLE on 11. any help please?

if(turns==2 && (dir=='u' || dir=='d') && y!=sj) return;
if(turns==2 && (dir=='l' || dir=='r') && x!=si) return;

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

    26615391 : same solution. TLE on test 10.

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

    My problem was TLE, and it's solved by using a boolean visiting 4D array to mark the position I have already checked with the direction and number of turns that I have checked the position with.

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

      Your solution is 90% identical to mine what a coincidence :D however i didnt use the visited array and still it worked in less time even thought im using java, i dont think u need the visited array maybe u have to recheck ur base case conditions or the recursive function , or maybe stop it when u have done already 2 turns and ure not the same line or column of the destination, cause in that case ull need one more turn to get to dest, so stop it from the beginning when turns=2 and Tx!=x and Ty!=Y

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

        Here is my code 26655398. I have already put these return cases you mentioned. However, I'll back to this problem soon, thank you:D. Edit: please look back to my previous comment, direction instead of destination, sorry for this mistake.

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

It seems to me C is in something easier to solve this way(sorry if someone have alredy written about this): We used bisection method for minimal time calculate. Let start with L=0, R=10^11. Let us now be at time M = (L + R) / 2. Then it is easy to calculate for every mouse her coordinates Xi and Yi. Obviously when Yi >= Y2 and her y-speed >= 0, we must move the right border, since she will never be inside a rectangle. Similarly examine the three other cases:

Yi <= Y1 and y-speed <= 0

Xi <= X1 and x-speed <= 0

Xi >= X2 and x-speed >= 0

And we must move the right border, if all mouses are in the rectangle. If these conditions are not met, move the left border. When we have done all iterations, we have right border as an answer. We will get it, if all mouses were in the rectangle at the same time. Else deduce -1

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

B has easier solution. Paint crosses on S and T with different colors (say 's' and 't'), then examine each line and each column if any of them contains /S\.*T/ or /T\.*S/ (c++26615732).

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

    Awesome idea! Thank for your share!

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

      Similar idea:
      1. Paint 's' to the left and to the right from 'S'. Same with 'T'.
      2. Rotate whole field.
      3. Repeat step "1".
      4. Try to find S+dots+T or T+dots+S (ignoring case).
      5. Repeat step "2".
      6. Repeat step "4".
      Implementation in perl (26638162).

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

Why do you give him so many downvotes?After all he prepared the round and posted the editorial!

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

The post is hidden because of too negative feedback, click here to view it

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

Same code shows two different verdict why?

Accepted code: Wrong Answer code:

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

    The code works fine with C++14 but not with C++11 but I don't know why, maybe it's a precision-related issue.

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

For problem B, I got WA on test 62. Here is my submission: 26615111

Can anybody help me ? What's wrong in my code ?

Update: I have found my bug. I was using visited array as vis[row][col][mov], using visvis[row][col][dir][mov] got AC. Here is my AC code: 26632674

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

I have written dfs solution for Problem B but it has got WA for test case 24.

My Code
»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

С из разряда "сначала подумай, потом пиши". Я вот не догадался решать отдельно для x и y, а бросился решать в 2D.

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

I don't like this round...

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

In problem B, I used DP to get the minimum number of direction changes to reach 'T' from a given cell.

The DP state is: (row, column, current direction).

If the starting cell can reach 'T' in 2 direction changes or less, then the answer is YES.

This code gives me WA.

Is there a logical problem with my method?

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

    You essentially do a DFS instead of a BFS, so when you find a path, it is not necessarily the shortest one.

    In other words, such a dynamic programming solution should care about the order of visiting the cells, and yours doesn't.

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

How can problem B be solved just using 3(currx,curry,dir) states in case of bfs whereas for recursive dfs I need 4 states (currx,curry,dir,turn). I couldn't understand this part can someone explain it to me . Thank you

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

    Using 0 - 1bfs, a bfs on a graph where the edges weights are 0 or 1. This BFS instead of using a queue, uses a deque (double ended queue).

    If you change the direction, then this edge has weight 1, otherwise it has weight 0. If you go through an edge with weight 1, push it to the end of the deque, otherwise push it to the front.

    While doing the BFS, always pop the front of the deque

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

Скажите пожалуйста,как вы решали задачу B через DFS(строка,столбец,направление,кол-во поворотов).Я так и сдавал,но почему-то не заходило(

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

    Вот 26615099 , любая клетка задаётся координатой направлением и кол-вом поворотов уже совершенных. Таким образом, мы получаем граф, нужно проверить можно ли из стартовой клетки добраться до финишной клетки.

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

For Problem G,could anyone please tell me the detailed way to cut the field into O(n) rectangles without deleted cells? I can't understand the way mentioned in the editorial.Thanks!

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

    In my solution, I did a scan line, maintaining a partition of (currently) non-deleted rows into ranges in a map. There will be two types of events:

    1. Some deleted rectangle appears. In this case, we need to remove all the ranges that overlap with this rectangle's range (and output a new non-deleted rectangle) and create up to 2 new non-deleted ranges to the left and to the right of deleted range. For example,
    partition before:  [.1.][.2.]....[.3.]...[..4..][.5.]
    new deleted range: .......[................].........
    partition after:   [...][]..................[..][...]
    

    The algorithm will create non-deleted rectangles for ranges 2, 3 and 4 and create two new ranges as shown above.

    1. Some deleted rectangle disappears. In this case, we simply create a new non-deleted range. For example,
    partition before:  [...][]..................[..][...]
    old deleted range: .......[................].........
    partition after:   [...][][................][..][...]
    

    My solution for reference (submit).

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

Can E be solved for N ≤ 106? It's possible to calculate knapsack for this constrains.

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

    Yes, should be doable in O(n*(sqrt(n)+log^2(n))) with FFT convolutions.

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

      How ?

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

        Here is the simpler version in and small constant (/64 with bit-compression): Let's split the weights into two groups: and w < k.

        1. In the first group, there are at most values (because their sum doesn't exceed n).

        2. In the second group, there are at most k distinct values, and each group of equal weight w can be replaced with O(logn) equivalent (for knapsack) weights: if there are m weights equal to w, let's replace them with w, 2w, 4w, ..., , .

        This way, we can reduce the size problem to at most weights, which can be solved with regular knapsack dp (possibly with bit-compression)

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

          Let's replace w,w,w by 2w,w while we can (it my be done in O(n)), after that it will be only different weights by the same bound.
          So extra log is not needed

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

Can someone give more detailed explanation of problem D ?

Thanks

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

    Ok, I'll try explain my solution

    Oleg can't go near offices he visited, so if now he is in office v, he visited q, q > v, he can't visit office k, where k > q. That means if now he's in office v, he can only visit office q, l < v < r, l is rightmost visited office which position is less than v and r is leftmost visited office which position is more than v. So we have to solve our problem for state [v][l][r][s], where s count of steps we made. We have 2 options. First is go to left and second is go to right. If we go left, we are not interested what is r, and if we go right we are not interested what is l. So our state now is [left border][right border][direction][s]. State [v][l][r][s] becomes 2: [v][r][right][s] and [l][v][left][s]. We can exactly identify our current position. If we go left it's right border, and if we go right it's left border. Now, when we are in state [l][r][direction][s] and now we are in office v, we have to just find all offices q, l<=q<=r and c[v][q] != 0 and solve our problem for [l][q][right][s+1] and [q][r][left][s+1] and take minimum. For it we can use recursion. We can start from any office, so we have to solve problem for [0][v][left][0] and [v][n+1][right][0] and take minimum.

    We have n^2*2*k states. In each state we check make not more than n operations. So algo works in O(n^3*k)

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

      How is the time complexity O((n+m)*n*k). I didn't even understand how the naive algorithm works in O((n+m)*n^2*k)

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

Problem G can be solved using Hopcroft-Karp algorithm, if you optimize it hard enough: 26669894.

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

I think problem B has a better solution with brute force and a little dp firstly, initialize 2 arrays h and v so that h[i,j]=number of cell with road work from (i,1) -> (i,j) and v[i,j]=number of cell with road work from (1,j)->(i,j) since igor can only make 2 turns so his way must be one of these: --- — ---- | ^ | | | | | | <-- --> | V ---- so we just need brute force and calculate the number of cell with road work on the path (get it from h and v cause he can only go up, down, left or right)

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

Problem F has a tag "divide and conquer". Is there a solution with O((n + m + q)polylog(n + m + q)) time complexity?

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

    Yes. Check submission of niyaznigmatul: 26621779.

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

      Thanks!

      For other people who are trying to understand this code: The setmin function sets every element of the interval to be the minimum of its value and val. The getmin function returns the first index in the interval whose value is larger than val.

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

I have a solution for problem F with time complexity O((N+M)logN) using segment tree.

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

Just in case someone is looking for a proof for problem A (793A - Oleg and shares)

We can't increase the values of any number, so we have to make bigger numbers equal to smaller numbers by subtracting k (zero or more times) of them.

Suppose the array is sorted.

At some point we'll have to make numbers arr[i] and arr[0] equal, and the only way is by subtracting k from arr[i] some number (q) of times and subtracting k from arr[0] some number (p) of times so we have: (a = arr[0], b = arr[i] for simplicity, 0 < i < n)

a — pk = b — qk

(b — a) = k (q — p)

We don't know (and we don't need to know) values p and q, but now it's certain that (b — a) must be divisible by k.

Now the key step is that if k divides (b — a), then we can make b equal to a by subtracting k (b — a) / k times because the only criteria to make a = b — qk is that k divides (b — a). This is optimal.

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

Getting W.A. for problem B......Can anyone provide a test case for which this fails?

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

Very easy solution brute force solution B- no DP or dfs/bfs at all. It takes full advantage of the fact that the solution must use at most 2 turns:

Because of the two turns limitation, there are two possible cases for our final path. Our directions for the travel can either be D/U => L/R => D/U or L/R => D/U => L/R.

Assuming the two locations are (r1, c1), (r2, c2), the first case case can be handled as such:

Iterate through all subarrays board[i][c1:c2]. If a subarray with 0 obstacles inside is found, and the subcolumns board[i:r1][c1] and board[i:r2][c2] also contain 0 obstacles, then we've found an answer. These subarrays/subcols by themselves will represent a valid 2 turn path, so if they contain no obstacles, it is obvious an answer has been found.

This same logic can also be applied to the second case. If searching both cases yields no answer, then we can safely return "NO".

Accepted implementation: https://codeforces.me/contest/793/submission/164203477