One of the hardest problems of March Long 20 featured the following problem:

Given an undirected graph, find an acyclic orientation of its edges such that if there exists edges and , then there exists or .

Such orientation exists, if and only if the graph is chordal. At first I forgot the acyclic orientation, in this case pseudoforests can also satisfy the condition. Some problems that are in NP for a general graph can be solved in polynomial time for chordals.

Some correct solutions were getting an incorrect veredict, I read the judge many times and I couldn’t find the bug, I even tested the judge locally. It turns out that the stack size of spoj is very reduced, and the program that checks if a solution is correct crashed because an stack overflow (because of the recursive dfs). Kudos to the tester for noticing that!

I setted the tie-break problem, is about gathering all points in a plane by choosing a polygon and moving each point towards to its adjacent point with integer coordinates.

The problem was reviewed by our even-admin Alexey, his approach is as follows: