PotemkinCycle is Intense.

Its someday of the week. I am in Germany. I wake up in the morning. Open messenger. Adhyyan has asked us to try Potemkin Cycle from CEOI 2015 day1. I ignore it for the day, but again the next day there is some discussion about it in the group. I download and open it too. A biggg mistake.

Problem: find any cycle with >3 nodes so that there are no edges between 2 nodes in this cycle unless they are consecutive nodes. (Chordless cycle ?!).   N=1000. M=100,000

Simple enough statement. How hard can it be. Its the next day morning, and I start thinking on it. Have a few ideas but quickly discard them. Finding a cycle and checking is ofcourse exponential. Can the solution be randomized? Maybe. Who knows. Meanwhile it see that adhyyan has already seen the editorial, and coded. WA. Anay meanwhile reads it, and after a few minutes (as always) says he has got it. PMing Adhyyan.I have another wrong idea : fix 1st and 3rd node of cycle and see if a possibke 2nd and 4th nodes exists or not. But ofcourse. 4 cycle is not necessary to br the answer. Adhyyan has got AC now. But cant prove the complexity. I ask him whether Anay's soln was correct. Nop. He had seen the editorial by then. Now both of them are stuck on the complexity. I have another solution. Fix an edge. Now discard all nodes that have an edge to *both* the endpoints of my selected edge. Now from the set of nondiscarded nodes.. Select any 2 nodes such that one of them is adjacent to one of the endpoints of my edge and another that is adjacent to the other endpoint of my selected edge. These 4 nodes seem to be an arc of atleast 1 such cycle. That is to say, we can connect the 2 nodes we selected last and the shortest path between them + the nodes on our selected edge is a good cycle. I tell this to adhyyan. "Suspicious that ur soln is so simple when there was only 1 AC incontest". Well, i got the countercase pretty much instantly after that. Ugh. Another wrong solution. Sad.I now start thinking about the triangle property. There exists a theorem which says that there are only O(mroot(m)) triangles in a graph with M edges. Can that be used? I think for about half an hour. No progress. I have spent a total of 50 minutes by this time behind the problem. I have to go out. Have to roam about Munich too. Life is bigger than 1 problem. But its addicting so i return to it while on the city bus.

I suddenly get an idea. Seems promising. For each node, make a BFS tree. In that, order the cross edges by their height. Now cross edges that connect levels1 to 1, makes all cross edges between the respective subtrees of those level1 nodes   invalid. I claim that the first  valid cross edge now gives (since it has been ordered) a cycle, if we consider that cross edge and the parent linkings to root. Proof is easy, as since its the lowest valid cross edge   between those two subtrees, there are no other cross edges lower than it. 

Now we just see if such a valid cross edge exists in atleast 1 of the BFS trees.

Seems promising. Even my claim is true.

But it turns out that it does not detect all possible scenarios. After that I found even Shashwat had the same BFS Tree idea. Especially  when our cycle can have more than 2 of its edges as cross edges. Example: a 4cycle where all its nodes are connected to a 5th node. Shashwat and Anay gave this case. Sad. This was the 12th wrong solution among the 4 of us. Shashwat cant prove the time complexity of the editorial solution either. I resist seeing it. Its night now. The problem   is too addicting to sleep. How to avoid the triangles. Thats all we need to do. 

I have another idea. Make another graph in a dp-ish style, where each node is a pair of nodes in our current graph (a,b). A and B must  have an edge between them. Its basically like the (prevnode,currnode) storing  idea, where we remember which was our previous node. For edges in the graph, join (a,b) to (b,c) if abc is not a triangle. Now we find a cycle in this new graph. This will corrospond to a cycle in the original graph with the property that no 3 consecutive nodes are a triangle. This was the constraint in our new graph. So what we get a cycle with the property that the cross edges divide the cycle into sectors with more than 3 nodes. No triangles remember? 

This seems promising. Correct. But is it? Adhyyan doesnt get it for a long time, but maybe i explain badly. There js some discussion about this. Shashwat gives a fake disprove (yes, fake DISPROVE) and it confuses me for a while but i disprove his disprove. Intense. But i want to waste more time on this addicting Problem. And i do. I try to find other solutions, but fail to do so. I was afraid i had a high constant factor as my solution was o(n*m) it might TLE. A day passes. I havent coded it yet. Its sunday  now.  I dont go out in the first half today. Berlin can wait, this cannot. I start coding it. I submit. WA. I dont give up. It has to work. I spend around 3 hrs. My cycle finding is rekt. So many bugs. But now the score is upto 60. It might still work. There is a very stupid bug now. I fix   it. Atlast. The AC. A good ending to a intense problem. My alternate solution works. I look at the editorial. And now i am stuck on proving its complexity. :(