### suxrib's blog

By suxrib, history, 4 years ago, , Let us discuss div2+div1 today's Opencup problems here Comments (21)
 » How to solve div2 D Nice set of Points?
•  » » There was similar problem on Yandex finals 2011 (link). Solution on Russian is explained here.
 » How to solve B and J?
•  » » 4 years ago, # ^ | ← Rev. 2 →   B — Let's say that 2 points are connected if they can be paired. it's possible to pair 2*N points iff each component of such graph has even size (I don't know proof). To make number of edges linear connect each point only with 2 closest points in each direction (not 1 point because this point can be deleted). Now we need to check if sizes of all components are even if we delete a vertex. This can found with similar approach to finding articulation vertices.Code
•  » » » The proof is obvious if you know Tutte theorem. Let's assume the graph is connected and |V| is even. If we delete vertex v, there will be at most 2 connected components(one will contain vertices on the same vertical as v, other will contain vertices on the same horizontal). Therefore, if we delete k vertices, there will be at most k + 1 connected components. If for some subset of size k after deleting it there will be k + 1 odd components, then which is odd. Contradiction.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   sorry, this not, the sol to the problem J
•  » » J — I have some shitty dp, but some team solved it very fast so I believe that there exists neater solution.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   A simpler approach: DP[position in array][mask of used positions in permutation][remainder]; code.
•  » » » » Nice! On the other hand my solution is polynomial :)
•  » » » » Can you please explain the idea behind it?
•  » » » » » Let's process positions one by one. We'll keep track of current position, mask of entries in the final permutations which we already picked and remainder of current distance. The trick is — in case you know that mask, you can calculate how many times you'll pass through the next segment (and therefore how much does it add to the total length of the route) — for each two adjacent positions in your route you can check the mask and see if they are on the same side of the segment or not.
•  » » 4 years ago, # ^ | ← Rev. 2 →   E You need 3 facts (I'll list them without proof). First, our trajectory has period g = gcd(h, w). Second, if the trajectory period has u up moves (along h side) and r right moves, then gcd(u, h) = gcd(r, w) = 1. Third, any trajectory satisfying these constraints is good, so the answer is , where gcd(u, h) = gcd(g - u, w) = 1.