### wilcot's blog

By wilcot, history, 7 years ago,

Very interesting contest.

But, how to solve task K, L and H?

• +16

| Write comment?
 » 7 years ago, # |   +5 L: We construct tree greedy , then solve problem with centroid-decomposition code: https://ideone.com/kzZmuP
 » 7 years ago, # |   0 L: Once we have the shortest paths tree, computing the answer can be done using centroid decomposition.The tree can be computed with Dijkstra's algorithm, modified to prefer parents with a smaller path from the root (with respect to the lexicographical order). Checking if a path is smaller can be done with binary lifting, in a way similar to the computation of LCAs.
•  » » 7 years ago, # ^ |   +13 You can build tree without comparing pathes. After Dijkstra algorithm you can use DFS using only edges related to some shortest path, one thing you need before DFS is to sort edges by destination.
 » 7 years ago, # |   0 H. Let p = x - y, q = y - z, r = z - 1. Then, in pqr-space, a subhill is of the form p ≥ const, q ≥ const, r ≥ const, p + q + r ≤ const.Fix the value of p + q + r (try all O(N) possibilities). Now the task is a standard 3D-sum problem. In total it works in O(N4).I believe it's also possible to solve it in O(N3) but looks quite messy.
 » 7 years ago, # |   +29 H: Let's split each 3d update/query into <=100 2d updates/queries. For fixed y, we get update/query on some rectangle. First do all updates using inclusion/exclusion (adding +-1 to points (X,Z) to denote adding +-1 to all x>=X, Z>=z and then taking partial sums to find value at position (x,z)); now you can answer each 2d sum query in O(1) using partial sums once again.K: Kind of divide-and-conquer. Let's assume that each query contains element n/2. In this case we can calculate dp for each suffix of the left part of the array and for each prefix of the right part; now in order to answer a query you can combine corresponding suffix of first part and prefix of second part in O(D). Now we are left with queries which are completely contained within left or right subarray; OK — let's solve them recursively. That gives us O(D * M) to answer all queries and O(N * D * logN) to calculate all DP values at each level of recursion.
 » 7 years ago, # |   0 Is there any new upsolving? When I access upsolving system, the last problem is old -> "O-17 Sphenic Numbers".
•  » » 7 years ago, # ^ |   0 Can you give the links of old problems? I don't understand what is Grand Prix. I see blog of its discussion on codeforces but there is no link to the actual problems. Is it a private contest?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   +3 It is private, but very good contest. Site is p̶r̶i̶v̶a̶t̶e̶c̶u̶p̶.̶r̶u̶ opencup.ru You can participate if you are registered in team, and your coordinator (in my case he is a lecturer in my university) gave you credentials.
•  » » » 7 years ago, # ^ |   +8 Yes, it's a private series of ACM ICPC-style contests called Open Cup (website is in Russian only). Problems are private, participation is restricted to "sectors" only (it's basically a multi-site contest).
•  » » » » 7 years ago, # ^ |   +1 Is there a site where old problems are available for public in English? Is it illegal for the participants to share the problem statements?
•  » » » » » 7 years ago, # ^ |   +1 I don't think there is one. No idea about the legality.
•  » » » » » 7 years ago, # ^ | ← Rev. 2 →   +1 Actually, there are a lot of problem statements of previous seasons in public access here: http://opencup.ru/Just choose season in left menu with the button "Выбрать сезон".Then choose stage in menu "Выбрать этап" and there you can find problem statements.
•  » » » » » » 7 years ago, # ^ |   +4 I do not see the extended menu like you. Maybe you are logged in? I just see Div2/Div1 Results, Yandex and they also require login credentials.
•  » » » » » » » 7 years ago, # ^ |   0 It's at the very bottom of the page, on the left side. Extended menu appears on hovering the "Выбрать этап" button.
•  » » » » » » » 7 years ago, # ^ |   0 There are no statements for this season. Check some previous, for example: http://opencup.ru/index.cgi?data=newstape&menu=index&head=index&ncup=och&class=och
•  » » 7 years ago, # ^ |   0 Finally, upsolving have apear!
•  » » » 7 years ago, # ^ |   0 ...and later disappeared by 'Service is not available' :(
 » 7 years ago, # |   +5 Where can i find problems?
 » 7 years ago, # |   +5 F?
 » 7 years ago, # |   +5 B?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Find the rightmost '(' that can be paired with some ')' in the range, and the leftmost ')' that can be paired with it, and remove them.
 » 7 years ago, # |   0 D?
•  » » 7 years ago, # ^ |   +10 We can get digit D as answer if all non-null digits in N are not less than D and all digits after first occurence of D in N are equal to 9. Find the biggest D we can get.
•  » » 7 years ago, # ^ |   0 Lets compare digits by parameter 'how much this digit meets in the range 1..N'. How to make this comparator: The base observation is an each digit meets equal amount of times in numbers in the range 1..10^x-1. So lets process digits of number N from left to right, suppose current digit is X, there are three cases (suppose lhs < rhs): if x > rhs or x < lhs just continue, because it means that lhs and rhs occured equal times in numbers, in numbers with this prefix. if x == lhs, than lhs is better if x == rhs, than lhs is better, excluding the case if remaining suffix contains only '9', in this case we should just continue as we did in the first case. If lhs not better than lhs, we can take rhs. So as result we can find maximum D where D have the same amount occurences as 1.
 » 7 years ago, # |   +50 Does anybody know when (approximately) contest will be unfrozen? Just curious.
•  » » 7 years ago, # ^ |   +10 snarknews said it'll be done after 4pm tomorrow, after Vekua event in Tbilisi.
•  » » » 7 years ago, # ^ |   0 Thanks :)
 » 7 years ago, # |   +24 Problem A is copied from this one.And I think problem F is also copied from problems of Multi-University Training Contest in China. In my mind, I have solved this problem before.
 » 7 years ago, # |   0 how to solve C??
•  » » 7 years ago, # ^ |   0 Consider all 4! permutations, after left,right,top,bottom fixed, you can fix horizontal & vertical offsets between left & right. After that you can find answer using dp (hint: for fixed horizontal offset precalc cnt[i][j] for top/bottom strings — count positions p, that s[p]=i and s[p+offset]=j).
•  » » » 7 years ago, # ^ |   +36 Spoiler