### Tima's blog

By Tima, history, 8 years ago, translation,

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

• +37

| Write comment?
 » 8 years ago, # |   +8 How to solve M?
•  » » 8 years ago, # ^ | ← Rev. 10 →   +10 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.
•  » » » 8 years ago, # ^ |   0 Seems that you mixed up odd and even
•  » » » 8 years ago, # ^ |   0 What does equal number of trianges in your solution for odd and for even n?
•  » » » » 8 years ago, # ^ |   +8 If you are interested in details, here is my solution: http://ideone.com/o9GMsI
•  » » » » » 8 years ago, # ^ |   0 Got it.
 » 8 years ago, # |   0 What is test #3 in problem L ?
•  » » 8 years ago, # ^ |   +8 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
 » 8 years ago, # |   +8 How to solve G?
 » 8 years ago, # |   +5 Where can I find the final standings?
•  » » 8 years ago, # ^ |   +11
 » 8 years ago, # |   +6 how to solve I?
•  » » 8 years ago, # ^ | ← Rev. 4 →   +12 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
 » 8 years ago, # |   +11 How to solve D?
•  » » 8 years ago, # ^ |   0 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.com/blog/entry/23266?#comment-276645. Then we have do the same for the index j. There are only O(n) such states.
 » 8 years ago, # |   0 Does anyone know how to solve problem J?
•  » » 8 years ago, # ^ |   0 Pleade read about Prufer codes (that's a bit overkill, but a very nice one).