Hohol's blog

By Hohol, 12 years ago, translation, In English

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).

  • Vote: I like it
  • +76
  • Vote: I do not like it

| Write comment?
»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will the problem description be in English or Russian?

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does the contest effect rating?

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the link for the contest?

  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Codeforces Gyms
    Find 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.

»
12 years ago, # |
  Vote: I like it +29 Vote: I do not like it

Thanks for the nice problems, it's the first time ever I can solve more than 5 problems in one contest, it's 8!!!!!!!!!!!

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B, G, K?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    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.

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

will there be solutions or put those problems on problem set?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
12 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Why the test cases in the practice mode , aren't shown?( like other contests ) It helps to find what's wrong with our code...

»
12 years ago, # |
  Vote: I like it +16 Vote: I do not like it

for problem C,we tried a greedy alog,but wa on test 8,,,anyone knows how to solve it ?

  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it +13 Vote: I do not like it

    First of all, if you have WA 8, make sure that you don't output inversed permutation.

    My solution:

    1. 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.

    2. 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.

    3. 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).

    4. 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 :)

  • »
    »
    12 years ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

    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]].

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      dp[f(i)] <= lefEnd[i] you probably mean dp[i] <= x[best[i]] where x[best[i]] is a coord of our point?

»
12 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Don't forget that tomorrow there will be another gym contest: http://codeforces.net/blog/entry/7493

»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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?

  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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].

»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Finally ACed probelm C and problem I , really nice problems!!!!!!

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :(

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your checking of the existence of the answer is correct. I think you have a bug in the next part of the solution.

  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A hint for the second part: you can set the monochrome for each image immediately after the sorting.