codeforces-scrape

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

339.md (5361B)


      1 Source: https://codeforces.com/blog/entry/8725
      2 
      3 [339A - Helpful Maths](/contest/339/problem/A "Codeforces Round 197 (Div. 2)")
      4 
      5 Tutorial by [Fefer_Ivan](/profile/Fefer_Ivan "Candidate Master Fefer_Ivan")
      6 
      7 To solve this problem we can count the number of digits 1, 2 and 3 in the input. If there are *c*1 digits 1, *c*2 digits 2 and *c*3 digits 3. Then we must print the sequence of *c*1 digits 1, *c*2 digits 2 and *c*3 digits 3. Digits must be separated by + sign.
      8 
      9 [339B - Xenia and Ringroad](/contest/339/problem/B "Codeforces Round 197 (Div. 2)")
     10 
     11 Tutorial by [Fefer_Ivan](/profile/Fefer_Ivan "Candidate Master Fefer_Ivan")
     12 
     13 To solve this problem we must learn how to calculate fast enought the time, needed to travel between houses *a* and *b*. Let's consider the case when *a* ≤ *b*. Than Xenia needs *b* - *a* seconds to get from *a* to *b*. Otherwise *a* > *b*, Xenia will have to go thought house number 1. So she will need *n* - *a* + *b* seconds.
     14 
     15 [339C - Xenia and Weights](/contest/339/problem/C "Codeforces Round 197 (Div. 2)")
     16 
     17 Tutorial by [Fefer_Ivan](/profile/Fefer_Ivan "Candidate Master Fefer_Ivan")
     18 
     19 Let's consider the definition of balance. Balance is the difference between sum of all weights on the left pan and sum of all weights on the right pan. At the beginning balance is equal to 0. Att each step Xenia puts one weight on the pan. It means she adds to or substracts from balance integer from 1 to 10. In each odd step, the integer is added and in each even step the integer is subtracted. From the statement we know, that after each step, balance must change it sign and must not be equal to 0. So if after some step the absolute value of balance is greater than 10, Xenia can not continue. Also, it is said in the statement that we can not use two equal weigths in a row. To solve the problem, let's consider a graph, where vertices are tuples of three numbers (*i*, *j*, *k*), where *i* is a current balance, *j* is a weight, used in the previous step, and *k* is the number of the current step. Arcs of the graph must correspond to Xenias actions, described in the statement. The solution of the problme is a path from vertex (0, 0, 1) to some vertex (*x*, *y*, *m*), where x, y are any numbers, and *m* is the requared number of steps.
     20 
     21 [339D - Xenia and Bit Operations](/contest/339/problem/D "Codeforces Round 197 (Div. 2)")
     22 
     23 Tutorial by [Gerald](/profile/Gerald "Master Gerald")
     24 
     25 The problem could be solved by using a typical data structure (segment tree).
     26 
     27 The leafs of the segment tree will store the values of *a**i*. At the vertices, the distance from which to the leafs is 1, we will store OR of the numbers from the leafs, which are the sons of this node in the segment tree. Similarly, vertices, the distance from which to the leafs is 2, we will store Xor of the numbers stored in their immediate sons. And so on. Then, the root of the tree will contain the required value *v*.
     28 
     29 There is no need to rebuild all the tree to perform an update operation. To do update, we should find a path from the root to the corresponding leaf and recalculate the values only at the tree vertices that are lying on that path. If everything is done correctly, then each update query will be executed in *O*(*n*) time. Also we need *O*(2*n*) memory.
     30 
     31 [339E - Three Swaps](/contest/339/problem/E "Codeforces Round 197 (Div. 2)")
     32 
     33 Tutorial by [Gerald](/profile/Gerald "Master Gerald")
     34 
     35 We will call the command *l*, *r* a reverse, also we will call the row of horses an array. Suddenly, right?
     36 
     37 The problem can be solved with clever bruteforcing all possible ways to reverse an array. To begin with, assume that the reverse with *l* = *r* is ok. Our solution can find an answer with such kind of reverses. It is clear that this thing doesn't affect the solution. Because such reverses can simply be erased from the answer.
     38 
     39 The key idea: reverses split an array into no more than seven segments of the original array. In other words, imagine that the array elements was originally glued together, and each reverse cuts a segment from the array. Then the array would be cut into not more than 7 pieces.
     40 
     41 Now you can come up with the wrong solution to the problem, and then come up with optimization that turns it into right. So, bruteforce all ways to cut array into 7 or less pieces. Then bruteforce reverse operations, but each reverse operation should contain only whole pieces. It is clear that this solution is correct, One thing it does not fit the TL.
     42 
     43 How to improve it? Note that the previous solution requires the exact partition of the array only at the very end of the bruteforce. It needed to check whether it is possible to get the given array *a*. So, let's assume that the array was originally somehow divided into 7 parts (we don't know the exact partition), the parts can be empty. Now try to bruteforce reverses as in naive solution. One thing, in the very end of bruteforce try to find such a partition of the array to get (with fixed reverses) the given array *a*.
     44 
     45 The search for such a partition can be done greedily (the reader has an opportunity to come up with it himself). Author's solution does this in time proportional to the number of parts, that is, 7 operations. However, this can be done for *O*(*n*) — this should fit in TL, if you write bruteforce carefully.