codeforces-scrape

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

367.md (4277B)


      1 Source: https://codeforces.com/blog/entry/9726
      2 
      3 ### Разбор задач Codeforces Round #215
      4 
      5 #### [368A - Sereja and Coat Rack](/contest/368/problem/A "Codeforces Round 215 (Div. 2)")
      6 
      7 Each time we will go through the array and look for the minimal element which is not yet marked. If we find an item, we add it to the answer and mark it, otherwise we will subtract the penlty from answer.
      8 
      9 #### [368B - Sereja and Suffixes](/contest/368/problem/B "Codeforces Round 215 (Div. 2)")
     10 
     11 We will count value *ans**i* — number of different elements on the suffix from *i*. For calculation will walk from the end of the array, and we count *ans**i* = *ans**i* + 1 + *new**a**i*, *new**a**i* equals to 1, if element *a**i* has not yet met and 0 otherwise.
     12 
     13 #### [367A - Sereja and Algorithm](/contest/367/problem/A "Codeforces Round 215 (Div. 1)")
     14 
     15 If you look at what is written in the statment, it becomes clear that the algorithm finishes its work, if we can get a string like: *xx*, *yy*, *zz*, *zyxzyxzyx*... and all its cyclic shuffles. To check you just need to know the number of letters *x*, *y* and *z* separately. Quantities can be counted using partial sums.
     16 
     17 #### [367B - Sereja ans Anagrams](/contest/367/problem/B "Codeforces Round 215 (Div. 1)")
     18 
     19 We will divide the sequence on *min*(*n*, *p*) sequences. 1-st, (1 + *p*)-th, (1 + 2·*p*)-th, ... element will go to the first sequence, 2-nd, (2 + *p*)-th, (2 + 2·*p*)-th... will go to the second sequence and so on. Now you need to find an answer for each of them, considering that *p* = 1. This can be solved by a simple method. You can go along the sequence from left to right and count the number of occurrences of each number. If the number of occurrences of each number will match the number of occurrences of the same number in the second sequence, then everything is OK.
     20 
     21 #### [367C - Sereja and the Arrangement of Numbers](/contest/367/problem/C "Codeforces Round 215 (Div. 1)")
     22 
     23 Clear that we need to collect as many of the most expensive properties that would have been possible to build the array. Note that having *n* numbers, we have *m* = *n*·(*n* - 1) / 2 binding ties. See that this is a graph in which to do Euler path, adding as little as possible edges. For *n*%2 = 1 — everything is clear, and for *n*%2 = 0, you need to add an additional *n* / 2 - 1 rib. Why? This is your homework :)
     24 
     25 The detailed explanation can be found [here](/blog/entry/9728).
     26 
     27 #### [367D - Sereja and Sets](/contest/367/problem/D "Codeforces Round 215 (Div. 1)")
     28 
     29 Replace out sets by array, where the element — the number set to which its index belongs. Now take all the consequitive sub-arrays with lengths of *d* and find a set of elements that were not found in that sub array. Clearly, if we as a response to select a subset of such set, it does not fit us. Remember all those "bad set." As we know all of them, we can find all the "bad" subsets. Now we choose the set with maximum count of elements which is not a bad set. It is better to work here with bit masks.
     30 
     31 #### [367E - Sereja and Intervals](/contest/367/problem/E "Codeforces Round 215 (Div. 1)")
     32 
     33 We assume that the intervals are sorted, and in the end we will multiply the answer by *n*!, We can do so, as all segments are different.
     34 
     35 Consider two cases *n* > *m* and *n* ≤ *m*. It would seem that you need to write different dynamics for them, but not difficult to show that in the first case the answer is always 0 . The second case is the following dynamics : *dp**i*, *l*, *r*, *i* — how many numbers we have considered , *l*, *r* — only in this interval will be present number *i*. Also, we will need an additional dynamic *s**i*, *l*, *i* — how many numbers are considered , *l* — how many segments are already closed , and *i* does not belong to any segment . There will be 4 transfers, since every number we can not begin and end with more than one segment.
     36 
     37 Now we should add *x* to our solution, it is quite simple: just add another parameter 0 / 1 in our dynamics, if we had such a element in the beginning of some interval or not. With out dynamics, it is not difficult.
     38 
     39 #### *For more details check out any solution that passed system tests.*