In ACM ICPC Amritapuri Onsite Replay, there wasthis problem that I spent more than 40 minutes trying to AC on. Somehow I’m getting WA.

My approach is this:

Appeal to the geometry of the problem. First consider two colors. If n is even, and every edge connects an odd and an even vertex, then 2 colors suffice : 1,2,1,2,...

Now let’s show it’s always possible with 3 colors. Note that there are at most n-3 chords and no two intersect. So add more chords on your own so that there are exactly n-3 chords and we have a triangulation of the polygon. Now start with a triangle adjacent to an edge and color its vertices 1,2,3. Now continuously move to adjacent triangles and color the “replacement vertex” accordingly. It’s easy to see that this works.

Now I had a lot of trouble “completing” the triangulation and adding adjacency relations, but after a while I thought I had it but I was getting WA after WA.

If I had got this I’d have got 7 questions.

Can anyone help me with this approach? Very good question by the way.

Can anyone help?