Zlobober's blog

By Zlobober, 7 years ago, translation, In English

I'm sorry for a delay with publishing the editorial.

731A - Night at the Museum

Problem author: egor-belikov, developer: timgaripov

In this problem you have to implement exactly what is written in the statement, i. e. you should find minimum number of rotations from letter a to the first letter in the input, then to the second one and so on. The only useful knowledge that may simplify the solution is that the distance between points x and y on the circle of length l (26 in our case) is min(|x - y|, l - |x - y|).

This solution works in O(|s|), and, of course, fits in time limit.

731B - Coupons and Discounts

Problem author: olympiad jury, developer: platypus179

In a correct answer we may guarantee that for any two consecutive days we use no more than one coupon for bying pizzas in these days. Indeed, if we have two coupons for buying pizzas in days i and i + 1, replace these coupons for two discounts, one for each of the days i and i + 1.

Consider the first day. According to the fact above, we may uniquely find the number of coupons for buying pizzas in 1 and 2 days we are going to use: it's either 0, if there is going to be an even number of pizzas in the first day, or 1 otherwise. The remaining pizzas in the first day will be bought by using discounts. If we use 1 coupon, then we may subtract 1 from the number of pizzas in the second day, and in both cases consider the second day and repeat the same actions.

If at some moment we have the odd number of pizzas and we don't need any pizzas in the following day, then it is impossible to buy all pizzas using only coupons and discounts, and we may output "NO". If it didn't happen, then we were able to buy everything using only coupons and discounts.

Such a solution works in O(n).

Question: Prove that the answer is "YES" if and only if any maximal contiguous segment without zeroes in the input sequence has the even sum.

731C - Socks

Problem author: egor-belikov, developer: wilwell

When solving this problem, it is convenient to use graph interpretation of the problem. Consider the graph, whose vertices correspond to the socks and edges connect those socks that Arseniy wears on some day. By the statement, we have to make that any two vertices connected by an edge have the same color. It actually means that any connected component should share the same color.

For each connected component let's find out which color should we choose for it. In order to recolor the minimum possible number of vertices, we should leave the maximum number of vertices with their original color. It means that the optimum color is the color shared by the most number of vertices in this connected component.

So, we have the following solution: consider all connected components, in each component choose the most popular color and add the difference between the component size and the number of vertices of this color. In order to find the most popular color you may, for example, write all colors in an array, sort it and find the longest contiguous segment of colors.

Such a solution works in .

Question: How to implement this solution so that it works in O(n + m)?

731D - 80-th Level Archeology

Problem author: olympiad jury, developer: Flyrise

Denote as x the number of alphabet cyclic shifts we will perform. Our goal is to formulate the statement of lexicographical order in terms of x.

Note that x may be considered as an integer between 0 and c - 1, i. e., as a residue modulo c. Let's also consider all characters as values between 0 до c - 1 as we may subtract 1 from the value of each character.

Consider two consecutive words in the given list. There are two possibilities corresponding two cases in the definition of lexicographical order:

The first case is when there exists such a position that these words differ in this position and coincide before this position. Suppose that first word has value of a on this position, and second word has the value of b. Then these words will follow in lexicographical order if and only if . It's easy to see that if we consider all residues modulo c as a circle, then this inequality defines an arc of possible x's on this circle. So, this pair of contiguous words produces the following statement "x belongs to some arc on the circle".

The second case is when there is no such a position, i. e. one word is a prefix of another. If the first word is a prefix of second one then these words always follow in lexicographical order irrespective to the choice of x. In the other case (second word is a proper prefix of the first word) we can't do anything with these to words since they will never follow in a lexicographical order, so we should print  - 1.

Now we have to find a point on the circle belonging to the given set of arcs. Suppose we have k arcs. Consider a line segment from 0 to c - 1 instead of a circle; each arc will transform to either one or two its subsegments.

Now we have to find out if there exists a point covered by exactly k segments. It may be done in different ways, for example you may add 1 on each of this segment by using some data structure, or you may add 1 to the left endpoint of each segment and  - 1 to the point after the right endpoint of each segment, and consider prefix sums (an off-line way to handle range addition queries). Or you may write down all endpoints of all segments, sort them by a coordinate and iterate over them from left to right, keeping the number of open segments. If at some moment you have exactly k open segments, then the answer is "YES".

731E - Funny Game

Problem author: meshanya, developer: ipavlov

First of all, comment on such type of games. In CS the game where two players are willing to maximize the difference between their own score and the score of their opponent is called a "zero-sum game". A useful knowledge is that problems for such a kind of games are usually solved using dynamic programming.

Note that at any moment the first sticker contains the sum of numbers on some prefix of an original sequence. This means that the state of a game is defined by a single number i: the length of an original sequence prefix that were summed into a single number.

Let's make two observations. First of all, for any state i the turn that current player will perform doesn't depend on scores of both players. Indeed, at any moment we may forget about the scores of both players since they add the constant factor to the resulting score difference, so we may virtually discard both players current scores. So, all we need to know about state i is what difference there will be between the current player score and his opponent score if the game would have started from the state i with zero scores.

Second observation is that the turn chosen by a player from the state i and the final difference of scores at the end does not depend from which player is currently making a turn (Petr or Gennady), i. e. the game is symmetric.

Denote as D[i] the difference between the first player score and the second player score if the game would have started from the state i with zero scores.

It is a convenient way to think about this game as if there were no separate scores of two players, but only a single balance value (difference) between them, and the first player is adding some numbers to the balance at his turn аnd second player subtracts some numbers from the balance. In such formulation D[i] is a balance change at the end of the game if the current player is willing to maximize it and he is currently in the state i. The answer for a problem will be, as one can see, D[1]. Note that if the current player would be willing to minimize balance, then the final balance change from the state i would be  - D[i] because the game is symmetric.

Let's calculate all D[i] using dynamic programming. At the end of the game, i. e. in the state n the value D[n] is equal to zero because the players won't be making any turns, and so the balance won't change.

Consider some state i. Suppose current player will take all the stickers up to the j-th (here j-th means the index in the original sequence). In such case he will change balance by S[j] (where S[j] is the sum of first j numbers in an original sequence), and game will move to the state j. After that his opponent will change the balance by  - D[j] (note that the balance change value is added with an opposite sign since the opponent will be playing from this state).

So, the final balance change when making such a turn will be S[j] - D[j]. In the DP definition we play for a player that is willing to maximize the balance, so .

Such a formula produces a solution in O(n2), but one may find that that it's enough to keep the maximum value of S[j] - D[j] on suffix j > i, recalculating it in O(1) when moving from i to i - 1. So, we have the solution that works in O(n).

Question: Which data type should be used for D[i] (and for the answer, in particular)?

731F - Video Cards

Problem author: olympiad jury, developer: vintage_Vlad_Makeev

First observation is that if we fix the leading video card power x, we may take all the video cards of power at least x, as each of them brings the positive power value. So, we may sort all the cards in the ascending power order and then we will always choose some suffix of cards in such an order.

The final total power equals to . Note that under the summation there is a number that is divisible by x and that is no larger than 200 000 at the same time. It means that there are no more than different terms in this sum. Let's calculate the value of a sum spending the operations proportional to the number of different terms in it.

To do it we need to find out for each of the values x, 2x, 3x, ..., how many video cards will have exactly such power at the end. It's easy: final power kx corresponds to those video cards, which originally had the power between kx and (k + 1)x - 1. Their number can be found out in O(1) if we build an array C[i] storing the number of video cards of each power and calculate prefix sums on it.

It means that we got a solution that performs about operations. It's useful to know that the sum inside brackets is called a harmonic series, and that its sum is very close to the natural logarithm of the number of terms (up to a constant factor in limit).

It means that we got a solution in complexity of where m is the maximum power of a single video card.

Question: One may try to submit a solution assuming that the optimum power is always one of the first, let's say, 100 unique video cards in an ascending power order. How to build a test where the optimum power lies between 1/4 and 3/4 of a sorted power list, i. e. a counter-test for such a solution?

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

| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve E if it was modified by "Instead of replacing first k ≥ 2 stickers by a new stricker S' with value of their sum, we replace S' by first two stickers only."

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

I got stuck with problem C because I completely missed the he has to finalize the colors now. part. I thought we could change the colors more than once.

Any idea how to solve this problem in a reasonably amount of time if it's valid to change the colors more than once, i.e., every day you can choose to change the colors as needed? Not surprisingly I couldn't come up with a good idea.

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

Can someone give a better explanation for problem-D. I was not able to follow the editorial that well. Thanks !

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

    Imagine that you have only 2 sequences. You'd calculate the set of non-negative integers A, that for every if you perform a changes, then the first sequence is lexicographically not greater than the second. Then you do this for every n - 1 pairs of sequences (the 1st and the 2nd, the 2nd and the 3rd, the 3rd and the 4th, and so on...), so you calculate A1, A2, ... An - 1 sets. The answer is in the set , if it's empty then answer is  - 1.

    For more information how to deal with sets, check out my submission: 21613184 (basically you make an array and use partial sums)

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

Any one found anything greedy for the E?

i tried either taking all the numbers on the first step or taking the first n-1 numbers , got WA

can't find a case where the difference between both answers will be larger than the difference of either all the array and 0 or forcing the enemy to take a negative value then forcing him on the last array number,

But this doesn't seem right....

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

Another (more complex) idea of problem E.
Sort all values, than calculate res[i] — answer for videocardi like leader.

N = a * b, so that
We iterate over videocards and want to do no more than operation per one. There are two cases:
1) Current videocard is leader. We assign xi like a and try .
2) Current videocard isn't leader. We assign xi like N and want to add xi to some leader videocard, where . So try
There is basic idea. You can check my solution for more details or ask me

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

can anyone help me with the F I am not able to understand it

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

It seems that I solved DIV 2 C (SOCKS) problem same way as mentioned in editorial but getting TLE on test #33. Any suggestions for optimization?? or is my solution wrong?? Any help is appreciated. Thanks

My Submission

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

    my tle submission — tle my ac submission — ac

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

      Thanks, got it accepted by inserting colors in the set and then resetting count array to zero. But shouldn't this approach be slower than the last one? We have inserted n elements in set in O(N log N) time, whereas the previous approach took only O(n) time. Why was it getting TLE then??? Again, any help will be appreciated.

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

        In tle solution, every time I visit a non-visited node, I am assigning tot[node] to zero for all node, which is taking O(n) time. Suppose you have to perform bfs n/2 times then, you running time complexity would be O(n^2). But after inserting values in set,I only have have to assign those values to zero which I have visited in current bfs operation .

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

          Wow...!! Never thought of that. I always ignored initialisation during analysis. Thanks. Something good came out that TLE.

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

          I think, best way to do this is to use map and clear the map after each dfs, it takes less memory than total memory of array and set. Correct me if I am wrong.

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

In E, tc 2 4 1 -7 -2 3 move 1, petya takes 1 -7 score p -6 g 0 seq -6 -2 3 move 2, gena takes -6 -2 3 score p -6 g -5 game ends diff -6 — (-5) = -1 what's wrong? -1 is better than -3

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the greedy implementation for C, and how on earth we came around graph on reading this problem?