lucyanna2018's blog

By lucyanna2018, history, 7 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  

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

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

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

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

  • »
    »
    6 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
»
4 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).