### Um_nik's blog

By Um_nik, history, 4 years ago,

cgy4ever, when will the round be? clist.by says that it will be tomorrow in 19:00 (MSK), but three days ago it was 18:00 (MSK) and I also cannot find anything related on TopCoder itself. For example, there is no such competition in Web Arena calendar.

• +47

 » 4 years ago, # |   +93 and I also cannot find anything related on TopCoder itself Common case with Topcoder website :(
 » 4 years ago, # |   +15 It seems to be in the calendar here, link.
 » 4 years ago, # |   +50 The email reminder says it will be at 12:00 UTC-4, that is 19:00 MSK (why don't they put a link to timeanddate in their email?).
 » 4 years ago, # |   +21 Very nice problems, 600 was very nice and 900 also looked interesting.
•  » » 4 years ago, # ^ |   +25 Any ideas on 600?900 can be solved using 2-SAT on variables "i-th person in subtree of j-th vertex". There are some condition on this variables depended on tree structure, like, if you are in subtree of vertex, you are in subtree of it's parent. I lost condition, that you can't be in subtrees of two vertices wich are different sons of one, so failed systest. Each of problem conditions can be expressed in terms of "both vertex in subtree of x[i], and at least one of vertices not in subtree of each son of x[i]". This changes a bit if r[i] is son of x[i]. But all subtrees for all roots are subtrees or their complements of original tree, so it's ok.
•  » » » 4 years ago, # ^ |   +40 Let N be the number of points. We can see that (the number of finite regions) = (the number of crossings) + (the number of components) — N. Since the number of components is a constant (unless we make really stupid choice of directions), we want to maximize the number of crossings.Now, let's convert the coordinates, and assume the following: Half-lines go to left or down from each point. Each coordinate is between 0 and N, and of the form "integer + 0.5". We want to color the points red and blue, and maximize the number of pairs of red point R and blue point B such that x(R) < x(B) and y(R) > y(B).Here, in one optimal solution, we can prove that their is a shortest path from (0, 0) to (N, N) that splits the square [0, N] × [0, N] into two regions, such that in one region all points are red and in the other region all points are blue. Now it's not hard to come up with an O(N2) DP.
 » 4 years ago, # |   0 Am I right the solution for 900 is the 2-SAT on statements "person x lives in the subtree of directed edge y"? I've coded this, but haven't managed to get it working in time.
•  » » 4 years ago, # ^ |   +15 Ok, thanks PavelKunyavskiy :)