Um_nik's blog

TCO17 3A
By Um_nik, history, 7 years ago, In English

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.

Tags tco
  • Vote: I like it
  • +47
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +93 Vote: I do not like it

and I also cannot find anything related on TopCoder itself

Common case with Topcoder website :(

→ Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

It seems to be in the calendar here, link.

→ Reply
»
7 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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?).

→ Reply
»
7 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Very nice problems, 600 was very nice and 900 also looked interesting.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +40 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply