In order to score ~10\%~ of the points, we need to find the necessary and sufficient conditions for the patriotic triangulation to exist.

Claim 1: In each triangulation with ~N \ge 4~ there are at least two "ears", i.e., triangles that share two sides with the input polygon.

Sketch of the proof: Induction. Claim holds for a square. Let a diagonal divide the polygon into two smaller polygons. If one of them is is a triangle, that is an ear. Otherwise, we make an inductive argument.

Let there be ~a~, ~b~ and ~c~ sides with colors ~1~, ~2~ and ~3~ respectively. It obviously holds that ~a+b+c = N~. It is also clear that ~\max\{a, b, c\} < n~ because otherwise no ear would exist.

Claim 2: If a patriotic triangulation exists, numbers ~\{a, b, c\}~ have the same parity.

Sketch of the proof: Double counting the number of edges colored ~1~ across the triangles:

$$\displaystyle 2 \cdot (\text{number of diagonals colored }1) + a = N-3$$

From which we conclude that ~a~ has the same parity as ~N-3~. The same holds for ~b~ and ~c~ by analogy.

The aforementioned conditions are also sufficient; this is easiest to prove by a constructive algorithm which solves this task.

In short, we will inductively build ears using the sides of two different colors without changing (prove it!) the equal parities of numbers ~\{a, b, c\}~ in a new polygon which is missing a side. We also need to watch out whether the new polygon is monochrome.

One nice implementation is as follows:

For each vertex of a polygon we will remember its successor in the current polygon and the edge color which connects them. Searching for a spot to build a new ear is, in fact, simple. We will just circle around and build an ear on a vertex whose predecessor and successor edges are of the same colors and at least one of those colors is the one that is most frequent among the current polygon sides. If each time we start from the place where we've built our last ear, it can be proven that the complexity is an amortized ~\mathcal O(N)~.

Implementations with time complexity of ~\mathcal O(N \log N)~ should also receive full score on this problem.