Hi,
I have just read the editorial for Constrained Topological Sort from AtCoder Beginner Contest 304. It seems as if found a counter-example to disprove the en_translator editorial (no code linked to it) but for some reason it passes several submissions and I am not sure why.
According to my understanding of the editorial (re-worded a bit):
Define a node x as assignable to label i if:
- Labels 1, 2, ..., i - 1 have been assigned.
- For all edges (f, x), f has been assigned a label j < i
- L_x \leq i
Conduct Kahn’s algorithm with the difference being you pick the assignable node x for all x has minimal R_x for amongst all asignable nodes in the priority queue (not just a simple FIFO queue).
But here is my counter-example (same form as the input):
4 2
3 1
4 2
1 4
2 2
1 3
1 4
We have 4 nodes 1 … 4.
3 has an edge to 1 and 4 has an edge to 2.
1 must have a label between 1 and 4, 2 must be between 2 and 2, 3 must be between 1 and 3, while 4 must be between 1 and 4.
According to my understanding of the solution, node 3 is picked first (since R_3 = 3 < R_4 = 4).
Then either node 1 or 4 will be picked, but eitherways 2 will be missed out upon since it must be the 2nd node selected.
The real solution though is to pick 4 first and then 2 followed by 3 and 1.
This clearly means the official solution is incorrect - but why does it still work?
