codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

353.md (6098B)


      1 Source: https://codeforces.com/blog/entry/9145
      2 
      3 [353A - Domino](/contest/353/problem/A "Codeforces Round 205 (Div. 2)")
      4 
      5 Let's denote the sum of numbers on the upper halves of pieces as *s*1, and the sum on the lower halves — *s*2. If this sums are even, than the answer is obviously 0. Note, that if the numbers on both halves of piece have the same parity, than parity of *s*1 and *s*2 won't change after rotation this piece. If the numbers on halves have different parity, than parities of both *s*1 and *s*2 will change after rotation. Therefore, if *s*1 and *s*2 have different parities, than the answer is  - 1. If both *s*1 and *s*2 are odd, than we should check, if there is a piece with numbers of different parities. If so, the answer is 1, otherwise, the answer is  - 1.
      6 
      7 [353B - Two Heaps](/contest/353/problem/B "Codeforces Round 205 (Div. 2)")
      8 
      9 Let's say for shortness, that we put numbers, that are painted on cubes, in piles, instead of cubes themselves.
     10 
     11 Note, that the answer is the product of *c*1... *c*2, where *c**i* is the number of different numbers in the *i*-th pile. Let's consider that all numbers are different. In this case the answer is *n*2. Now, let's suppose that we have two equal numbers and all the other are different. Then, if we put them in different piles, the answer will be *n*2, but if we put them in one — *n*·(*n* - 1). Obviously, the first case give greater product.
     12 
     13 Thinking in similar manner, you can conclude, that we should do the following. Take numbers, that appear more than once, and put one of them in the first pile, one of them in the second pile and the other put aside. After that, divide the numbers, that appears once, in two equal part and put the first part in the first pile and second part in the second pile. Finally, take the numbers, that we put aside, and separate them in two pile in any kind.
     14 
     15 [353C - Find Maximum](/contest/353/problem/C "Codeforces Round 205 (Div. 2)")
     16 
     17 Let's see on the highest bit of *m*. If it equals to zero, than for any ![](https://espresso.codeforces.com/82bfd78b9ec5ce07767875a86696eb7b2eb3031c.png) there is a zero on the (*n* - 1)-th position, so *a**n* - 1 doesn't affect the answer and we can put it aside and find the answer for smaller number of elements.
     18 
     19 If the highest bit of *m* equals to 1, than *a**n* - 1 for some *x* will present in *f*(*x*), but for some will not. Let's consider such *x*, that *a*{*n* - 1} will present in *f*(*x*) with zero coefficient. It is obvious that ![](https://espresso.codeforces.com/1afa5e1c01821c9eb75380a7d909ea9346d5df07.png). In this case *f*(*x*) will have maximum value when *x* = 2*n* - 1 - 1. Try to update the answer by this value.
     20 
     21 Now we should analyze the case, when ![](https://espresso.codeforces.com/1e91d5c0ab7f315e0a3e351ea55021c6393b98e8.png), find the maximum value of *f*(*x*) for all such *x* and try to update the answer by this value. Let's note, that in all such *x* there is 1 in (*n* - 1)-th position. Therefore we can find the maximum value of *f*(*y*) for all ![](https://espresso.codeforces.com/96f416b8656e45ba100abc9eeb197de6e7844e13.png) and add *a**n* - 1 to it.
     22 
     23 [353D - Queue](/contest/353/problem/D "Codeforces Round 205 (Div. 2)")
     24 
     25 Note that if there are some girls in the begining of the line, they will never move. So let's remove them and will consider that the first schoolchildren in the line is a boy. Also note, the relative order of the girls doesn't change. Let's calculate for each girl such moment of time *t**i*, that after it she won't move forever. Note, that for *i*-th girl *t**i* ≥ *t**i* - 1. Let's calculate *t**i* in order from left to right. Let's denote *y**i* is the position in the line where *i*-th girl will stop, ans *x**i* is her current position. Therefore it is needed *x**i* - *y**i* second for girl to reach her finish position. So if *x**i* - *y**i* > *t**i* - 1, then *t**i* = *x**i* - *y**i*. Let's manage the case when *x**i* - *y**i* ≤ *t**i*. The girl with number (*i* - 1) will be on *y**i*-th position by *t**i* - 1-th second, so *t**i* ≥ *t**i* - 1 + 1. Let's consider such moment of time *p*, when *i*-th girl stand right after (*i* - 1)-th, but not on *y**i*-th position. After that, in (*p* + 1)-th moment of time (*i* - 1)-th girl and the boy standing in front of her will swap their positions, but *i*-th girl will save her position. Then since *p* + 2-th second till *t**i* - 1 both girls will change their positions. Finally, at (*t**i* - 1 + 1) - *th* second *i*-th girl will occupy her position. Therefore, *t**i* = *t**i* - 1 + 1 in this case.
     26 
     27 [353E - Antichain](/contest/353/problem/E "Codeforces Round 205 (Div. 2)")
     28 
     29 Let's divide our graph on chains. Denote chain as the maximal sequence of the edges, which have the same direction. If there are more than 2 edges in each chain, then the answer is the number of such chains.
     30 
     31 If there is a chain containing only one edge (*u*, *v*), then brute vertex, which we will take in maximal antichain (also consider the case, when we take none of them). Let's suppose we brute the vertex *v*. After that we put aside this vertex and all vertices, which is comparable with *v*. In received graph we can find the size of the maximal antichain by uning dynamic programming with *O*(*n*) time complexity. Let's show how to do this.
     32 
     33 Write all remaining vertices in line and renumerate them from left to right by the numbers from 1 to *k*. After that we are going to calculate *d**i* — the size of the maximal antichain among vertices with numbers *j* ≥ *i*. So if *i* > *k*, then *d**i* = 0. In other case we can skip *i*-th vertex and try to update *d**i* by the value of *d**i* + 1. Also we can try to take *i*-th vertex to the answer. In this case we should skip all vertices, that are reachable from *i*-th, or the vertices, from which we can reach *i*-th, take the answer from the next vertex, add 1 to it and try to update the answer.