https://codeforces.net/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.net/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.

Added a few more videos to my playlist:

• Round 883 (Div. 3)
• Round 886 (Div. 4)

I think the solutions are quite intuitive (and hope they are well-explained), check them out. Also keep an eye out for more solution videos.

https://www.youtube.com/playlist?list=PLMSo_-spVQ_9YunnChdhx8uMUTEW4bkO3

My first programming video, showing solutions I made in this round.

It's possible one or two of them are not completely optimized but I think these approaches are intuitive.

The description contains a text document which I used to guide this video. The document also contains my CF submissions for the problems.

https://youtu.be/ha8bQkBvYVs?si=05BOR09SVxPFg_pK