Recent actions
 0 but I'm not good at competitions . what I'm good at is spend many days on a very hard problem,but not solve easy problem fast
 0 Thank you very much !It seems that you are really strong :)
 0 since you are Chinese I have write a Chinese version solution:https://user.qzone.qq.com/441766573?ptlang=2052&source=friendlistmy English is not well,sorry..
 0 What is your idea?Is it the same as Editorial?
 0 I have solved problem F using dynamic programming with segment_tree+Lazy propagation optimazationhttp://codeforces.com/contest/856/submission/30362019
 0 how to prove greedy for B?
 0 Could you please elaborate on the proof?
 0 Spent a couple hours solving D, then while reading the editorial realized the misuse of the term 'cactus' -.-
 +13 It's quite easy idea-wise, but when the judge says "WA", you get stuck.
 0 About the Hash solution to problem B, I tried a lot but even I commented out other part, the initial part itself is TLE on test 2. I wonder whether the hash solution workable. Here is my code with all other parts commented out :http://codeforces.com/contest/856/submission/30314085.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 why unrated....
 +36 E is not hard. It seems that many people are afraid of geometry.
 0 sorry for bothering, I found the reason.
 0 Hello, I am so confused about problem B. Why is my code running so inefficiently? Actually, I cannot tell the difference between my answer and this one. Can anyone help? Thank you! 30251276, which is from team Pulato: IcyGirl, RefluxNing, qiancy981 30261692, and this is my solution. Thanks!
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Thanks a lot . :)
 +11 In problem D, I think it should be gu = sp - fu, not gu = fp - fu.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +2 Please enable upsolving.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +5 let dpnode be the maximum sum of edges you can add such that those edges belong in this subtree and the subtree is still a cactus. let Then if you do not make any cycle pass though node then dpnode = sumnode. otherwise if you take the edge (u, v) , lca(u, v) = node and make it's cycle pass through node , then dpnode is . All you need to do is tree sum updates and queries which can be done by building a bit on dfs start end times easily in NlogN.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago Created or updated the text
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +4 Let's look at the longest string at the moment. If we will take it to the answer, we block only one string — the taken one without first letter, and because from these two strings we can take only one, our move is not worse, than any else. Thus, if at each step we take the longest possible string, then we get the best answer.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I've started implementing a solution using centroid decomposition and think I understand where u and v come in: they're one of the paths, clipped to the current tree — hence either u or v is the exit to some ancestor root, which constrains the search space.However, I've still having some trouble. Let's say I have a tree rooted at r with two subtrees S and T, and I want to compute f[u][v] for some u, v both located in S. I then compute f[u][v] within S and I compute the maximum beauty in T. But then I also need to consider adding new edges whose paths pass through r (from S to T). This means I now need to consider two constraints in S: u->v must be untouched, but so must the part of the new path that lies within S.Any tips? I've not used centroid decomposition much so I may be missing something standard.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 ``````This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved. ``````
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 why & how would the sorting work ? could you please explain ?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +3 Check that all numbers A[i] are different. Generate random number from 1 to 106 (define it x) Check x. (if it`s bad — repeat 2) Add to set all pairs A[i] + x. Repeat 2,3,4 N times
 0 Nevermind
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +11 Can't submit solution now. When will be it in archive ?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +43 Can option to upsolve problems on CF be enabled?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +41 Five years ago I wrote C.How to solve F? It looked like the most interesting problem.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 The intersection of two satellite coverage area can be formed as a satellite-like coverage area.If this satellite-like coverage area is covered by other satellites, there will exists at least one satellite coverage area which contains this satellite-like coverage area (instead of some union).Considering the projections of coverage areas on the half-circle border (as intervals), the query is equal to determine whether there exists one interval (except i-th and j-th) which is able to cover the intersection of i-th interval and j-th interval.When I finally realized that, I tried to modify my wrong solution but actually I didn't have enough time :(Our recommended solution is to sort all the intervals by their left endpoints, and use a segment tree to maintain the maximum right endpoints, which can be done in .
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 .| 1 41| 2 55| 6 9
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Brute force, since all b[i] <= 1e6, you can try for each i in {1..1000000} to loop through the array a and find for each a[j], if i+a[j] is visited before, if not add that i to the answer list, and mark i+a[j] for all a[j] as visited, you need to break when the answer list equal to n.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 but it is not correct for this test case i guess...2 1 4as diff is 3 we can take b[1]=1 b[2]=4 as u r saying....
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +3 How to solve A?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Yes, it's an overkill but I can add a check if the longest suffix is obtained by removing exactly 1 character.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +8 @flashmt: No@bmerry: Easy enough to add the "only one level up" check :)
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 maximum independent set in trees, f[u][b]=maximum number of vertices we can take from subtree u, b can be 0 or 1 indicating if we can pick or not u
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I solved E in a robust way, maintaining points with (angle OAP, angle OBP) The common covered area by (A, B) and (C, D) is (min(A, C), min(B, D)). To cope with query 3, I checked if all points other than i, j don't have (P, Q) such that P >= min(A, C) and Q >= min(B, D) and the point is not in the circle. This can be done with ordinary segment trees.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I don't think Aho-Corasick is exactly what you need: you want to link each node to the suffix formed by removing exactly the first character (or no link, if no such node exists), whereas Aho-Corasick will link to the longest suffix that does exist.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I thought exactly the same till step 3,and couldn't do more, can you explain step 4 (dp).
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I sort the points by angle made at A and at B, and rank them. Then I place them in a new coordinate system, where x1 < x2 means A-P1-P2 is counter-clockwise and y1 < y2 means B-P1-P2 is clockwise. Now satellites P1 and P2 can be connected if there is an intersection outside the planet, and there is no other satellite (x, y) such that x <= max(x1, x2) and y <= max(y1, y2) in this other coordinate system. That I do by keeping the smallest y coordinates for each x coordinate (using a set for each x coordinate), and then maintaining a segment tree over those.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +18 Am I the only one who used Aho-Corasick for B? Using suffix links, we can build a forest and the problem reduces to finding maximum independent set in a forest, which is straightforward.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +13 Where can I resubmit my code of this contest? emm... I think I will get AC this time.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 You are completely right because that t.me/ContestWatcherBot has just sent me "ContestWatcherBot: System testing has finished for Russian Code Cup 2017 — Finals Unofficial Mirror, Div. 1 Only Recommended, Teams Allowed. Waiting for rating changes." Actually,I have afraid of it because I couldn't solve any problem so I will take downrated by FUNRATED (cheating)
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +10 dp[v][0] — maximum beauty of substree when v is not in any cycledp[v][1] — maximum beauty of substree when v is in cycleWe have u, v, cost. Let's try to add cycle at lca(u, v). In order to get right sum we need to count on path from u, v to lca the sum of beauties not including this path. It can be done by calculating sparse table the same way we do with lca. O(nlogn)
 +40 My solution for problem A was different from yours.Find such minimal k (simply checking it each time for O(n)) that all ai have distinct remainders modulo k. Then we say that B = {1, k + 1, 2k + 1, ...}.It's clear that no two numbers from B have the same difference as some two numbers from A. The question is why such k ≤ 10000 exists. I haven't proved it during the contest (but I had some arguments like "each pair from A forbids all divisors of some number below 106, the number of pairs is about 10000 / 2, but these sets of divisors intersect each other, blah blah).
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Maybe a DP on the tree, using some data-struct like segment tree to obtain the sum of a path. The answer of the subtree of node x is ans[x] = max(sans[x]. max{i.c + sans[x] + sum(x,i.a) + sum(x,i.b)}), for i in V[x], V[x] is the set of input triple where lca(a,b)=x, sans[x] = the sum ans of x's children, sum(a,b) if the sum of value[x] for each x on the path(a,b), value[x] = sans[x] — ans[x]
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 when doing centroid decomposition the sum of sizes of roots is nlogn
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 What are u, v in this case? I assume it can't be all vertices in the tree, since that would be O(n^2).
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 centroid decomposition and dp f[u][v]=maximum beauty of subtree u if vertices in the path u->v are in a cycle
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I used a bit different idea. Every satelite covers the area, but also the arc of the circle. So i made interval tree for the arc coverage and checked if min(i, j intersection) <=2. It got TLE :(
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +22 I think rated->unrated is very gaoxiao.do you think so?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 How to solve D?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 It's always possible — just greedily add the smallest possible element to B that doesn't violate the constraints.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I solved with DP, but there was people that solved in 11 minutes, maybe there is an easier solution. My idea, lets consider every prefix of all strings and build an graph, where exists an edge between the prefix and the prefix without the first letter. It will be a forest. No two adjacent vertex can be at the set and just the vertexes that are prefix can be choose. Since you have to find maximun, you can apply dp.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Observe the input. check the difference between any 2 numbers in given array. B should not have this difference. Choose smallest number which is not one of these differences as b[1]. Repeat from b[2] and so on
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I think I have a solution based on that idea, but it got TLE despite being N log N. I think my function to determine whether the intersection point is inside the circle is too slow (right after the contest I realised a much simpler way to test it, but during the contest I had to use a bignum class to avoid overflows).
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 build the trie build another graph G where the vertices are the nodes of the trie (all possible preffixes) and add an edge from v to u if string v can be obtained from u by removing the first letter G is a forest now the problem can be solved with dp
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I tried something different. I'm pretty sure my idea is valid but my implementation is wrong. This is my idea: first of all, we will use rolling hashing to quickly compare strings. We say string A is a child of string B if the first letter of A can be removed to get B. We construct a tree or many trees with all the prefixes. Now the problem is equivalent to the most nodes you can "color" so that no two adjacent nodes are both "colored". You can solve with two dp arrays. dp1[i] will be the most you can color in the subtree of i while coloring i. dp2[i] will be the most you can color in the subtree of i without coloring i. We get the recursive formula that dp1[i] = 1 + sum of dp2 of children and dp2[i] = sum of max(dp1, dp2) of children.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +1 Yes, greedy by decreasing of length.If we sort all prefixes by decreasing of length, we can take them greedy. And with hashes we can check if we can pick current prefix.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 How to solve A??
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 What was the solution idea for problem B ?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 How to solve B? Is it some kind of greedy? (Just a wild guess since it looked NP-complete)
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Was E maximum interval tree?
 Created or updated the text
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +2 Now I understood why it was recommeded for Div 1 round! Because of its Statement
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +10 I don't know. :(
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +6 So will it be fixed？
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 Judgement Failed??
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +6 I answered the first problem then i submitted it then i get (Judgement Failed) what does this mean
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +9 What does Judgment Failed means ??
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +34 rip judge
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 For me! It is Downrated!
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +11 Additionally to the official standings, there are contestant list, standings with TC and CF nicknames, text translation of contest flow on English and on Russian available.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +3 Round is unrated, BUT you could find possible rating change here (after round starts)Extensions for browsers: Have fun & high rating :)Are you first time hear about CF-Predictor? You could read about it in my blog======================================================================Раунд не рейтинговый, НО посмотреть возможное изменение рейтинга можно тут (после начала раунда)Расширения для браузеров: Удачи и высокого рейтинга :)Впервые слышите про CF-Predictor? Можете прочитать про него мой блог
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +12 It's fixed, and the calendary says unrated also.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago -48 .
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +35 Funrated.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +74 rated or unrated ?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago 0 I see a boom for stupid accounts that post meaningless comments trying hard to achieve very low contribution. Will achieving lowest contribution ever make you feel better? Stop trashing and go get a life or some better goal.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago -8 I don't understand informal English very well, sorry. But yes, "unrated" means "no rating".
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago -8 Publisher said that this round will be unrated.
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +65 The title says “Teams Allowed”. But how can I register as a team member?
 On RussianCodeCup → RCC 2017 — Finals + CF Round, 6 months ago +20 The online mirror probably coincides with TCO17 Wildcard Round, right? According to this calendar TCO17 Wildcard and also rated "Fun SRM" is held in 19:00 MSK to 22:00 MSK, and RCC online mirror is held in 16:35 MSK to 19:35 MSK.
 On andrewzta → Russian Code Cup — Eliminataion Round, Some News, 10 months ago +37 Marcin_smu, you lucky bastard :P
 On andrewzta → Russian Code Cup — Eliminataion Round, Some News, 10 months ago Created or updated the text
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 I got the answer from I_love_natalia. It seems memory allocator/deallocator are slow on RCC. I guess my solution was slow because I used too much vectors/priority_queues.
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago +5 Thank you!To RussianCodeCup: I still don't know why I got TLE for E during the contest. My submission is #27152353 of http://codeforces.com/gym/101397/status/E, and it's much faster (2027ms) than genomes_iz_2modules.cpp (2870ms). Is it possible that my code works very slowly on RCC's server?
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago +30 Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 0n25, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 Will there be a place to submit solutions after the contest?
 On RussianCodeCup → Russian Code Cup 2017 Elimination Round — Editorial, 10 months ago +15 My solution (http://ideone.com/ahuhnB) is a little different from described here. For each point I generate a set of vectors from it. The number of right and obtuse triangles is equal to number of pairs of vectors with non-positive scalar product. To find it I rotate the vector and support the set of such vectors. Once it becomes co-directional with one vector I increase number of bad triangles by number in the set. Supporting it is quite simple since a vector enters this set from the moment it coincides with one of orthogonal vectors and leaves after it coincides with another. So I put into the set of events for each point 3 events: add point, query result, remove point. I start with vector slightly above vector (-1,0) and make a full circle counterclockwise.
 On RussianCodeCup → Russian Code Cup 2017 Elimination Round — Editorial, 10 months ago 0 Could someone please paste their implementation of D (which they think is elegant)?
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago +3 I mean how can I use the checker to check my solution on my computer. I don't see a main function in the checker, and I see a lot of "import ..." that I've never seen before.Sorry for my inexperience with Java.
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 You can try DFS, you just need hash table to check point exists or not and same for visited.
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago +3 How to use the checker for problem C on my computer ?
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 Just count for every vertex v, number of pairs (u1
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 What is solution for D?
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago 0 No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).
 On RussianCodeCup → Russian Code Cup 2017 Elimination Round — Editorial, 10 months ago 0 If we take n vertices of regular n-gon then the answer will be about .
 On RussianCodeCup → Russian Code Cup 2017 — Elimination Round, 10 months ago +8 My solution is O(N2), but it didn't pass test 9 because of the corner case.I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).