Tima's blog

Grand Prix of Asia
By Tima, history, 9 years ago, translation, In English

Let's discuss problems. How to solve B and J?

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

Comments Comments (17)
| Write comment?
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

How to solve M?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 10   Vote: I like it +10 Vote: I do not like it

    When N is odd, put N points around a circle, and choose all isosceles triangles.

    When N is even,

    • Put N-1 points around a circle, and choose all isosceles triangles.

    • Add (the remaining point) — (i) — ((i+1)%N) for each 0 <= i < N.

    • Add (the remaining point) — (i) — ((i+2)%N) for each 0 <= i < N.

    • Remove extra triangles.

    We should find proper coefficients but basically this is the idea of the answer.

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

What is test #3 in problem L ?

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

    My team had the same problem. We mistakenly believed that the line of "e" can not get the string "egg". After fixing, we passed the test. Perhaps a similar case in the test 3. P.S. Sorry for my bad english

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

How to solve G?

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

Where can I find the final standings?

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

how to solve I?

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 4   Vote: I like it +12 Vote: I do not like it

    We only need some edges. For every point we can reach this point from maximum 4 points(point J which has smallest Y, X[I] = X[J] and Y[J] > Y[I] and have direction 'D'.also for all other 3 direction). So we only have maximum 4 * N edges and now we can use simple dijkstra algorithm to get switch time of every robot. solution author LashaBukhnikashvili

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

How to solve D?

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

    If someone is still interested in solution, it's dp[i][j] where i and j are the suffixes of the given permutations. If s1(i) != s2(j) then dp[i][j] = dp[i + 1][j] + dp[i][j + 1]. If s1(i) = s2(j) so let len be the length of the longest common prefix of these suffixes. Then we are in danger of counting some array twice untill one of our indices(i or j) has reached position i + len + 1. So let's say i will move to i + len + 1 before j will move to j + len + 1. Let's try every k so that we will go to the state dp[i + len + 1][len + k], k <= len. We need to count number of arrays that can be obtained from substring (i ... i + len) of the first permutation and from substring (j ... j + k — 1) of the second permutation. We will avoid double counting if we will not take number from the second permutation if we took less numbers from the first permutation. So it's equivalent to the number of bracket sequences with len opening brackets and k closing brackets. It can be precomputed by simple dp or using formula described in this comment http://codeforces.me/blog/entry/23266?#comment-276645. Then we have do the same for the index j. There are only O(n) such states.

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

Does anyone know how to solve problem J?

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

    Pleade read about Prufer codes (that's a bit overkill, but a very nice one).

    → Reply