### Tima's blog

By Tima, history, 4 years ago, translation, , Let's discuss problems. How to solve B and J? Comments (19)
 » How to solve M?
•  » » 4 years ago, # ^ | ← Rev. 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.
•  » » » Seems that you mixed up odd and even
•  » » » What does equal number of trianges in your solution for odd and for even n?
•  » » » » If you are interested in details, here is my solution: http://ideone.com/o9GMsI
•  » » » » » Got it.
 » What is test #3 in problem L ?
•  » » 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
 » How to solve G?
 » Where can I find the final standings?
•  » »
 » how to solve I?
•  » » 4 years ago, # ^ | ← Rev. 4 →   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
 » How to solve D?
•  » » 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.
 » Does anyone know how to solve problem J?
•  » » Pleade read about Prufer codes (that's a bit overkill, but a very nice one).
•  » » » Thank you!
 » How to solve B?