maryanna2015's blog

By maryanna2015, history, 6 weeks 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!

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

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

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks 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