It's a tough problem set. Even if it only contains 10 problems, I find that, to finish the problem set is harder than other subregional contests (with more problems).

How to solve problem B and problem E? I got TLE with an O(n^2logn) algorithm on problem B, and have no idea on problem E.

Thanks!

Problem B:

SpoilerYou can use the idea of maintaining a dp on connected components described in here: http://codeforces.com/blog/entry/47764

Here the connected components will be just the current continuous parts of our currently built path. Now, if we view the dp dependencies as a DAG, the problem kind of reduces to finding the number of paths through a vertex. For this we maintain

dp1(i,j) anddp2(i,j).dp1(i,j) is the number of ways to place the firstielements injcomponents, such that no component ends in an < . Similarlydp2(i,j) is the number of ways to finish placing the elements, if we've already places the firstielements and currently we havejcomponents and we are not allowed to attach anything to the right-most component or create a new component to the right.Now to get the answer for each

kyou just combinedp1 anddp2. You get anO(N^{2}) solution this way. Here's the source: linkAlso would be nice to hear a solution for I.

Problem I: The problem asks whether all the lattice points can be 2-colored. If the answer is not, there must exists an odd cycle. By the defination of edges, an odd cycle means a (obviously non-zero) solution exists for the following equations:

for each i = 1..n: sigma(x_j * v_ji) = 0, j = 1..k;

sigma(x_j) = 1 (mod 2), j = 1..k.

To check the existence of the solution, we can use gaussian elimination. Since they are mod-2 linear equations, we can use bit operations to speed up. The complexity is about O(K^2*N) with a constant factor about 1/100, which fits into the time limit.

(I think taking the first group of equations modulo 2 is easy to come up with, but the reason why we can do this is not that obvious.)

UP I am eager to hear a solution for problem E!

I'd be interested in a solution for E as well.

I looked at the master-solutions in the gym (the two which get AC in the gym) and they crash on the following input.

InputThe kingdoms are

`1,6,7,8`

and`2,3,4,5`

and the roads are built between`2,5`

and`1,6`