### lucyanna2018's blog

By lucyanna2018, history, 10 months ago, ,

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

•
• +62
•

 » 10 months ago, # | ← Rev. 2 →   0 Problem B: SpoilerYou can use the idea of maintaining a dp on connected components described in here: http://codeforces.com/blog/entry/47764Here 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) and dp2(i, j).dp1(i, j) is the number of ways to place the first i elements in j components, such that no component ends in an  < . Similarly dp2(i, j) is the number of ways to finish placing the elements, if we've already places the first i elements and currently we have j components 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 k you just combine dp1 and dp2. You get an O(N2) solution this way. Here's the source: linkAlso would be nice to hear a solution for I.
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 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.)
•  » » » 2 months ago, # ^ |   0 "(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?
•  » » » » 2 months ago, # ^ | ← Rev. 4 →   +3 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 ≤ di ≤ 1). Let ci = 2xi + di. 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 x satisfying the equation. because of the connectivity of the lattice. Also, (mod 2). So, c = 2x + d is a solution to (i), (ii).
 » 9 months ago, # |   0 UP I am eager to hear a solution for problem E!
•  » » 9 months ago, # ^ |   +10 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. Input8 10 1 2 1 5 1 8 2 3 2 6 3 4 4 5 5 6 6 7 7 8 The kingdoms are 1,6,7,8 and 2,3,4,5 and the roads are built between 2,5 and 1,6
 » 7 months ago, # |   0 Auto comment: topic has been updated by lucyanna2018 (previous revision, new revision, compare).
 » 2 months ago, # |   0 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.