Блог пользователя Nerevar

Автор Nerevar, 10 лет назад, перевод, По-русски

363A - Соробан

Not so much to say about this problem. You need to extract the digits of the given number (read it as string or repeteadly divide by 10 and take the remainders). Then carefully do the mapping of digits to its' representation.

363B - Забор

Another easy problem. We need to calculate the sum of every consequtive segment of k planks. One way to do this is to calculate partial prefix sums: . Then the sum of heights of the planks i, i + 1, ..., i + k - 1 is si + k - 1 - si - 1. The other approach is to calculate the sum of the first k planks: h1 + h2 + ... + hk. By subtracting h1 and adding hk + 1 we get sum of k planks starting from the second plank. Then, by subtracting h2 and adding hk + 2 we get sum of k planks starting from the third plank, and so on.

363C - Исправление опечаток

The general idea of the solution is the following: while there are three consequtive equal characters, remove any one of them. After that we can only have typos of the second type. So, if we have one couple of equal characters immediately after another couple of equal characters (xxyy), we need to decide which character to remove, x or y? Let's find the leftmost typo of the second type in the string. It is easy to see that we can always remove the character from the second couple.

All these can be done in a single pass. Go through the characters of the given string and build the resulting string ans. Let's denote the current character as ch. If ch is equal to the last two characters of ans, skip ch. If ch is equal to the last character of ans and ans[length(ans) - 2] = ans[length(ans) - 3] (assume that ans is 1-indexed), skip ch. Otherwise, append ch to ans.

363D - Прокат велосипедов

Let's do a binary search over the number of boys that can rent a bike. So let's say that we want to check whether it possible for k boys to rent bikes. If some k boys can rent a bike, then the k "richest" boys (with the most amount of personal money) also can do that. It is easy to see that if they can rent bikes, they can rent k cheapest bikes (if we first sort the bikes in increasing order of price, it will be just the first k bikes).

So, take k richest boys and try to match them with k cheapest bikes, spending as much common budget as possible. The following algorithm works (try to understand and prove it before asking questions): take the boy with least number of money (of course, among the considered k richest) and try to give him the cheapest bike. If the boy has ehough personal money to rent this bike, use his money to do this. Otherwise, use all his money and take some money from the common budget. Continue this process with the second cheapest bike and the second "poorest among the richest" boys. This process can end in two ways: we will either run out of budget and fail to rent k bikes, or we will successfully rent these bikes.

363E - Два круга

At first, for each valid center cell (i, j) calculate circleSum[i][j] — sum of values inside the circle with center at (i, j). This can be done with the code like that:

 for (int i0 = r; i0 + r < n; i0++) {
            for (int j0 = r; j0 + r < m; j0++) {
                int sum = 0;
                int lj = j0, rj = j0;
                for (int i = i0 - r; i <= i0 + r; i++) {
                    while (dist2(i0, j0, i, lj) > r * r) lj++;
                    while (dist2(i0, j0, i, lj - 1) <= r * r) lj--;
                    while (dist2(i0, j0, i, rj) > r * r) rj--;
                    while (dist2(i0, j0, i, rj + 1) <= r * r) rj++;
                    sum += rowSum[i][rj + 1] - rowSum[i][lj];
                }
                circleSum[i0][j0] = sum;
            }
        }

This code iterates over all rows from top to bottom and keeps lj and rj — the leftmost and the rightmost columns in current row i that are inside the circle with center at (i0, j0). The function dist2 returns squared distance between two cells, rowSum[i][j] is equal to sum of first j cells in row i. In total, values lj and rj will be changed O(n + m) times, so the complexity of this part is O(nm(n + m)).

In the second part of the solution, for each row i we calculate several values:

  • leftMax[i][j] — maximum of circleSum[i][k] for k ≤ i
  • cntLeftMax[i][j] — the number of corresponding maximum values
  • rightMax[i][j] — maximum of circleSum[i][k] for k ≥ i
  • cntRightMax[i][j] — the number of corresponding maximum values

All these values can be calculated in O(nm) time.

The third part of the solution is the most tricky one. Let's say that the cell (i, j) is boundary cell for the circle centered at (i0, j0) if it belongs to this circle and is the leftmost or the rightmost such point in row i. It is easy to see that two circles A and B intersect if and only if there exists a boundary cell of the circle A that belongs to the circle B. As long as we have O(n + m) boundary cells for each circle, checking whether two given circles intersect can be done in linear time. Now, for each pair (di, dj), which means the relative position of one center to the other, we can determine if such two circles intersect. There are O(nm) pairs (di, dj), so the total complexity of this part is O(nm(n + m)).

And, finally, in the fourth part we are going to calculate the answer. Let's iterate over all triples of values (i0, j0, i), where (i0, j0) is a valid center cell and i is a row number. Consider the set of cells (i, j) in the row i such that the circle centered at (i, j) intersects with the circle at (i0, j0). It is clear that this set is consists of some (possibly zero) consequtive cells in a row. Let's assume that these cells are (i, lj), (i, lj + 1), ..., (i, rj), values lj and rj can be found in the third part of the solution. We are interested in cell that are not in this set: (i, j) with j < lj or j > rj. To find the maximum sum in such circles in O(1), we use arrays computed in the second part. Overall complexity of the solution is O(nm(n + m)).

Разбор задач Codeforces Round 211 (Div. 2)
  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's Amazing to see tutorial of CF round #211 before round #210

»
10 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Could you please send me the standard solution for problem E?

I have some wonder on the correctness of the solution. ( See this post: http://codeforces.com/blog/entry/9538 )

thank you.

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

the fact that the length of tutorial for problem E exceeds the sum of lengths of the other four problems suggests how difficult it is :P

EDIT: tutorial for problem E has been removed now! i wonder why, as very few coders solved it during the contest!

»
10 лет назад, # |
  Проголосовать: нравится -11 Проголосовать: не нравится

Hi, anyone can tell me why i got WA in this submission for problem C? 5069514

»
10 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Problem E is Knapsack problem?

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    O_o No way, it's some sort of precomputation-geometry stuff. Not sure what exactly, it's ugly.

  • »
    »
    10 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +11 Проголосовать: не нравится

    For each circle, compute the sum of its cells. Then we fix one circle (x1, y1) and try to find the maximum possible other one (x2, y2).

    Notice that because the radius is fixed, we can easily precompute for every value of x1 — x2 what is the maximum value of k such that we can't place the second circle on the segment from (x2, y1 - k) to (x2, y1 + k). So we only need to loop for every value of x2 and get the maximum of all circle from (x2, r + 1 ... y1 - 1 - k) and (x2, y1 + 1 + k ... n - r). This can also be precomputed.

    Total time complexity is O(N^3)

  • »
    »
    10 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

    I precalced all circle sums: Calculate sum of first circle in O(R²), calculate sum of other O(N²) circles in time O(R) (use sum of adjacent circle and update border). O(N*N*R)

    Then, for each row: For the first cell, create a map (circle sum => count), which counts occurrences of circle sums in the whole field excluding circle sums of colliding circles in O(N²). We can pair the circle at the current position with K other circles with a total of (sum of current circle) + V, where V is the biggest V in the map (V=>K). Update end result accordingly. For the other O(N) cells, update the map in O(R) (and update the end result). For all rows this is: O(N * (N*N*logN + N*R*logN))

    This results in O(N*N*N * log(N)).

    At first I ran into the time limit. I speed up my solution by skipping circle sums for the map that are obviously irrelevant (smaller than: best sum of two circles (so far) — maximum of a circle sum in the current row).

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In solution to D, you are actually maximizing the number of children who can rent a bike. For this you are doing a binary search on the number of possible answer (i.e. from 0 to m).

But there is another secondary condition which needs to be fullfiled and that is minimizing the personal amount. Taking k richest boys can satisfy to buy maximum k cheapest bikes but it may not be the minimized personal amount spent. There can be some shared amount left in renting k bikes and hence another boy (not in the k top richest boys) can be able to rent this buy with lesser personal amount.

Let me know if i am missing anything.

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Actually, choosing k richest boys and k cheapest bikes is just to check if it is possible to rent k bikes. Once it is possible to do so, we simply spend all of the shared budget renting k bikes (min(shared budget, total costs of k bikes)) to minimize the personal amount. It doesn't matter which boys are chosen in this case.

»
10 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain the proof of greedy property form problem D? :D Thanks in advance

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I do not know how to formally prove it but here's my best to explain my thought:

    assume we have sorted boys money in A[], sorted bikes price in B[];

    assume we have fix k boys a_1, a_2 ... a_k and k bikes b_1, b_2...b_k and a_i boy buys b_i bike

    I want to check if any other scheme will make me use less share money (as it can potentially make more boys buy bikes)

    Let's pick any a_i,a_j and b_i, b_j where i < j,

    try to swap them to see if we can use less share money

    i.e. a_i buy b_j and a_j buy b_i

    Case 1: if b_i <= a_i, then a_i, a_j >= b_i, it is always better using a_j buy b_j as a_i can afford b_i by himself --> No swapping

    Case 2: if b_i > a_i, no matter b_i > a_j or b_i <= a_j, swapping them won't able to make result better --> No swapping

    So using this greedy scheme to buy the bikes uses least share money for a fixed k boys and k bikes.

    Then, obviously for a fix k after bsearch, we can, again,

    greedily choose the richest k boys to buy the cheapest k bikes as they should make us possibly save more share money

    Lastly, when we know how many bikes k we can buy, we do not need to know which k boys buy them, as the total minimum answer is always the cheapest k bikes minus all share gold

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

" You are allowed to delete letters from both ends and from the middle of the word."

so why are we deleting from anywhere in string?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Even I'm confused with the problem statement. I think the problem setter intended to say "You are allowed to delete any character from the word, including characters at both ends."

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I have a test case for 211 div2 D problem? suppose following is the test case:

3 3 10
5 5 4
7 6 8

Then what should be the output? I think it is "3 10" . Because 1st bike can be bought with personal 4 rubles from 1st person,2nd bike can be bought with personal 3 rubles from 2nd person,3rd bike can be bought with 4 rubles from 3rd person.With the shared money it is always possible. But in the AC solution it gives output as "3 14". Any help??

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In the task it is said that we need to output the minimum amount of personal money spent, not common.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

What is the meaning of the statement "You are allowed to delete letters from both ends and from the middle of the word" in the question FIXING TYPOS. I thought we could only delete an element at the beginning, or at end or in the middle at once.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    exactly !! like for a test case "abcdefgghhi" output should have been "abcdefggh" with length 9 but according to the tutorial given its "abcdefgghi" with length 10 ! I used recursion for the deleting condition as given in question but its giving TLE for testcase 5.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with this test case of problem B Fence? I can't figure out what is going wrong here . Submission link: https://codeforces.com/problemset/submission/363/110904366

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    update your sum, everytime you move out from block.

    n_sum = sum;
    while(end<n){
            sum=sum-a[st]+a[end];
            st++;
            end++;
            if(sum<n_sum){
                n_sum=sum;
                start=st;
            }
        }