BeanBurrito's blog

Solution accepted, not sure why
By BeanBurrito, 4 months ago, In English

https://codeforces.me/contest/1971/submission/268388372

This submission was getting TLE. Basically I was constructing the implication graph from the 2-SAT clauses

Then, for each variable x, I run a DFS starting at x looking for “not x”. If there is no path, we move onto the next variable since a contradiction exists if and only if a path exists from x to not x and not x to x.

If there is a path from x to not x, I reset my “visited” vector and do the DFS from not x to x.

However, if I do not reset the visited vector when I move on to the next variable, the solution is accepted:

https://codeforces.me/contest/1971/submission/268389153

Why? If there are still nodes marked as visited shouldn’t the DFS on the next variable be invalid and eventually lead to a wrong answer? Are the tests simply insufficient?

I haven’r gone through the process of actually doing it but it seems like someone could adversarially design a graph/test case that would break this code.

Would appreciate any insight.

  • Vote: I like it
  • -10
  • Vote: I do not like it

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

Sets have an extra factor of log(n) for find and insert operations. If the tree has only one connected component, then there isnt any point in performing dfs over all nodes (visited or unvisited).

From what I can read in the blog, I get youre trying to find a path from every x to !x, instead you only need to find whether any x and !x are in the same connected component.

you can do that by maintaining a set or unordered set or just linear pairs for every connected component instead of finding paths individually.

I hope it helps.

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

    I understand that but that isn’t my question. My question is why this solution passes the tests even though the visited vector is not reset before we DFS on a new pair of variables

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I saw your submission now and understood what you're trynna do.

      Look you're checking for if !x is reachable from x, if it is reachable, then you instantly print no (which means you're not filling the visited part again, and you're answer is still O(n). if not reachable, then you don't do anything (still makes your solution O(n))

      You are right, your version of answer can be "hacked" from a test case. But if you solve it optimally, you don't have to even think of it.

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        If !x is reachable from x, then I reset the visited vector and check if x is reachable from !x.

        But if !x is not reachable from x, then I just move to the next pair (e.g. y and !y) without resetting visited.

        If !x is reachable from x, but x is not reachable from !x, we move onto the next pair (also without resetting visited).

        Originally I had a visit reset before each search, but it was getting TLE so I removed it just to see what would happen.

        I agree that it can be hacked, I'm surprised it got AC in the first place, seems like a rather common case would be able to break it.

        Appreciate the response, probably will try out the SCC approach but will also try to fix this version

        → Reply