lucyanna2018's blog

By lucyanna2018, history, 10 months ago, In English,

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

 
 
 
 
  • Vote: I like it  
  • +62
  • Vote: I do not like it  

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem B:

Spoiler

Also would be nice to hear a solution for I.

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      "(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   Vote: I like it +3 Vote: I do not like it

        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, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    Input
»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by lucyanna2018 (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.