Блог пользователя Um_nik

TCO17 3A
Автор Um_nik, история, 7 лет назад, По-английски

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.

Теги tco
  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +93 Проголосовать: не нравится

and I also cannot find anything related on TopCoder itself

Common case with Topcoder website :(

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

It seems to be in the calendar here, link.

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +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?).

→ Ответить
»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +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.

      → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 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.

→ Ответить