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!

Edit: Petr has posted a blog post to discuss problem E. Problem statement can be found here. Please refer to these two links for details:

http://codeforces.com/blog/entry/56977

http://petr-mitrichev.blogspot.com/2018/01/an-otherland-week.html

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.)

"(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.)". I'm trying to understand the reason why we can do this for I while but without success. Can you explain more this step?The problem is to find if there is a solution to the system of equations(condition for no odd cycle):

(i)

(ii) (mod 2)

Consider equation (iii) as equation (i) mod 2. We will prove that it doesn't matter if we replace (i) by (iii), which is to say that the system (i), (ii) has a solution iff the system (iii), (ii) has a solution.

One side of the proof is trivial. As any solution to (i), (ii) is also a solution to (iii), (ii).

Say there is a solution to (iii), (ii), say

d(where 0 ≤d_{i}≤ 1). Letc_{i}= 2x_{i}+d_{i}. Then equation (iii) says that (mod 2), (ii) says that (mod 2), and (i) is of the form :.

Clearly, RHS vector is even and we can cancel out 2. Now, there exists an

xsatisfying the equation. because of the connectivity of the lattice. Also, (mod 2). So,c= 2x+dis a solution to (i), (ii).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`

Auto comment: topic has been updated by lucyanna2018 (previous revision, new revision, compare).I would be interested in a solution for problem J. Thank you! I was thinking at a binary search, but I am not sure if there will be problems with precision.