Editorial for Appleby Contest '20 P4 - Philosophy Class
Submitting an official solution before solving the problem yourself is a bannable offence.
We can break the solution down into casework:
- If a triangle exists, the answer is ~3~. We can loop across all triangles in worst case ~\mathcal O(N^2)~ time by fixing one node on the triangle and checking all pairs of incident edges.
- Next, we check if the answer is ~4~. For this to be the case, we need to find a pair of edges such that share no nodes.
- If the answer is not ~3~ or ~4~, then it is impossible.
The first subtask was meant to reward brute force solutions.
The second subtask was meant to reward contestants who found the three cases, but checked for all triangles in the graph in ~\mathcal O(N^3)~ time.
Time complexity: ~\mathcal O(N^2+M^2)~