Editorial for Appleby Contest '20 P4 - Philosophy Class

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Plasmatic

We can break the solution down into casework:

If a triangle exists, the answer is $3$ ~3~. We can loop across all triangles in worst case $\mathcal O(N^2)$ ~\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$ ~4~. For this to be the case, we need to find a pair of edges that share no nodes.
If the answer is not $3$ ~3~ or $4$ ~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)$ ~\mathcal O(N^3)~ time.

Time complexity: $\mathcal O(N^2+M^2)$ ~\mathcal O(N^2+M^2)~

Comments

There are no comments at the moment.