### Hohol's blog

By Hohol, 7 years ago, translation, ,

Hello everyone.

We invite you to take part in the training on problems of VI Samara Regional Intercollegiate Programming Contest. It was held March 31 in Samara State Aerospace University.

Problem writers are members of team Samara SAU Teddy Bears. Problem tester is ashmelev.

Difficulty is the same as in our previous contests: 3 stars. Duration — 5 hours.

Contest starts this Saturday (April 27) at 02:00 PM (MSK).

• +76

 » 7 years ago, # |   +5 Will the problem description be in English or Russian?
•  » » 7 years ago, # ^ |   +13 Both.
 » 7 years ago, # |   0 Does the contest effect rating?
•  » » 7 years ago, # ^ |   +11 No.
 » 7 years ago, # |   0 What is the link for the contest?
•  » » 7 years ago, # ^ | ← Rev. 2 →   0 Codeforces GymsFind our contest (it's on the top now), register and solve the problems.Remember that it's already running and you will have less time. After finish you can participate in virtual mode.
•  » » » 7 years ago, # ^ |   0 This contest is targeted at advanced programmers, judging by problems ...
 » 7 years ago, # |   +29 Thanks for the nice problems, it's the first time ever I can solve more than 5 problems in one contest, it's 8!!!!!!!!!!!
 » 7 years ago, # |   0 How to solve B, G, K?
•  » » 7 years ago, # ^ |   +14 For B: calculated number of occurrences n_i of each character, probability to pick each letter is n_i/n, where n is total length of the string, and we'll see it n_i times. Expected value is sum of such probabilities.
•  » » 7 years ago, # ^ |   +11 B — ans = sum(count(c) * count(c)) / |s|, where count(c) means each char, how many times it appears in s. K — you are going to construct an array which has the inversion number equals to k, you can do it greedily.
•  » » 7 years ago, # ^ |   +7 For K, I start with the decreasing order which has the inversion equal to n * (n-1) / 2, and try to reduce it to k. For example, if the order is 5, 4, 3, 2, 1. We can reduce it by 4 by moving 5 to the end (4, 3, 2, 1, 5), then reduce it by 3 by moving 4 to the position next to 1 (3, 2, 1, 4, 5). The total number of inversion we can reduce is (n-1) + (n-2) + ... (n-m) where m is the number of time we reduce. We try to keep this sum greater than (n * (n-1) / 2)-k. Thus, for the last round of reducing, we will know the position that we need to move the number in the front to. Here is my code 3643676
 » 7 years ago, # |   0 will there be solutions or put those problems on problem set?
•  » » 7 years ago, # ^ |   +3 You can solve these problems in practice mode. Enter the gym (link) and enjoy.If you're stuck on some problems, ask here, someone will help you for sure.
 » 7 years ago, # | ← Rev. 2 →   0 Why the test cases in the practice mode , aren't shown?( like other contests ) It helps to find what's wrong with our code...
•  » » 7 years ago, # ^ |   +3 In Codeforces Gyms, the tests aren't shown in practice mode.
•  » » 7 years ago, # ^ |   +5 Address this question to MikeMirzayanov)
 » 7 years ago, # |   +16 for problem C,we tried a greedy alog,but wa on test 8,,,anyone knows how to solve it ?
•  » » 7 years ago, # ^ | ← Rev. 2 →   +13 First of all, if you have WA 8, make sure that you don't output inversed permutation.My solution: We can easily check if the answer exists, using sweep line approach: make events "beginning of the segment", "point" and "end of the segment" and sort them. If we process the beginning of the segment, add pair (its end, its index) to the set. If we process point, take the minimal pair from the set (it's obvious that better to match point with the earliest closing segment). If the set is empty at this moment, matching does not exist. Now check if the answer is not unique. Answer is not unique if for some points p1, p2 (p1.x <= p2.x) exist two segments s1, s2 such that max(s1.beginX, s2.beginX) <= p1.x, p2.x <= min(s1.endX, s2.endX), and they match each other in some full matching. Consider that we are processing point p2 and it matches with segment s2. When the situation above can take place? There should exist some point p1 (p1 is earlier in the sorted array) such that s2.beginX <= p1.x. Also the end of the segment s1, which matches with point p1 (p1 was already processed since it is earlier in the points array) should be greater or equal than coordinate of point p2: p2.x <= s1.endX. How to check it? Let's create a segment tree which can do operations getMax(L,R) and set(index,value). How does this segment tree work? For every point we will store the end of the segment which matches with this point. Ok, our sweep line is now processing point p2 and it matches with segment s2. What can point p1 be? Its coordinate should be greater or equal than s2.beginX — find the index of such point with binary search (let it be leftIndex). Then consider all points in the subarray [leftIndex, i-1] (where i is the index of the point p2, after all points are sorted). Make query on this segment and we will find the rightest end of the segment s1 which matches with such point p1 that can be also matched with segment s2. Now, if p2.x <= s1.endX, the answer is multiple. And update the segment tree using set(i, s2.endX). In fact, we copypasted this problem from Timus. But our problem has much higher contraints :)
•  » » 7 years ago, # ^ | ← Rev. 3 →   +17 I've found very elegant O(N) DP for checking uniqueness of the answer after some simple O(N * log N) preprocessing.At first I sort segments by their right ends and maintain points in the set. For i-th segment I choose the least available point on it and delete it from the set (if it exists). Denote it as best[i]. Then for future needs I also save the next least available point to next[i] (if it exists).The matching exists if and only if best[i] exists for each i and we can find the answer easily by array best[]. Denote as segm[i] the segment that matches with i-th point. So segm[best[i]] = i.Now how we can check uniqueness. The found matching is lexicographically smallest in some sense. Let's seek for the lexicographically next matching. For this we should try to replace best[i] by next[i] for each segment i in order N, ..., 1, since next[i] is the next best choice for the i-th segment. When we do such a replacement, the segment j = segm[next[i]] looses his point and we should either replace it by best[i] if possible, or otherwise take next[j]. In the latter case we should proceed to segm[next[j]] and so on. The replacement is possible once at some step we reach the segment that contains point best[i] and in this case we perform some cyclic shift of the subsequence of our matching.But we don't need to do this walk each time. Instead we can check each segment by clever DP in O(1) time. Namely, let dp[i] be the smallest left end of the segments in the walk i, f(i), f(f(i)), ..., where f(i) = segm[next[i]]. Then second matching via i-th segment is possible if and only if dp[f(i)] <= leftEnd[i] dp[f(i)] <= x[best[[i]]. Calculating of dp[i] is simple: if next[i] does not exist than dp[i] = leftEnd[i], otherwise dp[i] = min(leftEnd[i], dp[j]), where j = segm[next[i]].
•  » » » 7 years ago, # ^ |   0 dp[f(i)] <= lefEnd[i] you probably mean dp[i] <= x[best[i]] where x[best[i]] is a coord of our point?
 » 7 years ago, # |   +23 Don't forget that tomorrow there will be another gym contest: http://codeforces.ru/blog/entry/7493
•  » » 7 years ago, # ^ |   +4 will a contest with four stars be as hard as CF div1 ?
 » 7 years ago, # |   0 I hope that the questions will be easy as in previous gym contest.
 » 7 years ago, # |   +9 How to solve the problem I？I don't have the idea after thinking a lot？ Can someone give me some idea about problem I？
•  » » 7 years ago, # ^ |   +1 Build all derivatives starting from derivatives of higher orders.Example.Let b = [1,0,0,1,1]4-th derivative has length 1. Any array of length 1 is both increasing and decreasing. But we have restriction for 3-rd derivative: it should be increasing also. This means elements of 4-th derivative should be positive.a[4] = [1]3-rd derivative has length 2. We already have built 4-th derivative, so we know that a[3][1]-a[3][0] = 1. 2-nd derivative should be decreasing => elements of 3-rd derivative should be negative.a[3] = [-2,-1]With similar reasoning we get:a[2] = [-1,-3,-4]a[1] = [9,8,5,1]a[0] = [1,10,18,23,24] At every step we should keep absolute values of derivatives minimal possible to satisfy restrictions on elements of resulting array — they must be in range [-10^9..10^9].
•  » » » 7 years ago, # ^ |   +3 Thanks a lot!
 » 7 years ago, # |   +10 Finally ACed probelm C and problem I , really nice problems!!!!!!
 » 7 years ago, # |   0 any hints on problem G? I have tried a greedy constructive approach, like sort the k string (i see each block as a string) first and check if it is impossible to have an answer (ie: s[i][k] > s[i+1][k] where s[i] is the i-th string in the sorted array), then try to fill each '1' which is not yet filled before. I have also tried those case with duplicate blocks given, etc. Still I keep getting WA in case 3, 5, 12. :(
•  » » 7 years ago, # ^ |   0 Your checking of the existence of the answer is correct. I think you have a bug in the next part of the solution.
•  » » 7 years ago, # ^ |   0 A hint for the second part: you can set the monochrome for each image immediately after the sorting.