codeforces-scrape

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

342.md (3053B)


      1 Source: https://codeforces.com/blog/entry/8800
      2 
      3 [342A - Xenia and Divisors](/contest/342/problem/A "Codeforces Round 199 (Div. 2)")
      4 
      5 In this problem you should guess that exists only three valid groups of three
      6 
      7 1) 1, 2, 4
      8 
      9 2) 1, 2, 6
     10 
     11 3) 1, 3, 6
     12 
     13 (You can see that integers 5 and 7 are bad).
     14 
     15 So, we will greedy take these groups of three. If some integers will be not used, the answer is -1. In other case, print found answer.
     16 
     17 [342B - Xenia and Spies](/contest/342/problem/B "Codeforces Round 199 (Div. 2)")
     18 
     19 The problem is solved by greedy algorithm. We will pass the note only in correct direction. Also, if we can pass the note at the current moment of time, we do it. In other case, we will hold it and don't give it to neighbors (we can make this action at any moment of time). Obviously this algorithm is correct. You should only implement it carefully.
     20 
     21 [342C - Cupboard and Balloons](/contest/342/problem/C "Codeforces Round 199 (Div. 2)")
     22 
     23 In the problem you should carefully get formula. The optimal solution put marbles by two in a row. And then put one marble upon others if it possible. The most difficulties were to deal with this last phase.
     24 
     25 In comments to the post were given formulas how to put the last marble (exactly in the middle). And there was a good beautiful illustration, which describes the situation.
     26 
     27 [342D - Xenia and Dominoes](/contest/342/problem/D "Codeforces Round 199 (Div. 2)")
     28 
     29 In the problem you can count number of correct puzzles or substract number of incorrect puzzles from number of all puzzles. In any case you should count DP, where the state is (*j*, *mask*) — *j* — number of the last full column, *mask* — mask of the last column. This problem is equivalent to the well known problem about domino tiling or the problem about parquet.
     30 
     31 To get the solution of the whole problem I did the following. I try to attach one domino to each of 4 directions, then paint all three cells in black and count the number of correct puzzles. But in this case you will count some solutions several number of times. So you need to use inclusion exclusion formula for these 4 directions.
     32 
     33 [342E - Xenia and Tree](/contest/342/problem/E "Codeforces Round 199 (Div. 2)")
     34 
     35 The problem can be solved in different ways. The most easy idea is sqrt-optimization. Split all queries into *sqrt*(*m*) blocks. Each block we will process separately. Before processing each block, we should calculate minimum distances from every node to the closest red node using bfs. To answer the query we should update this value by shortest distances to red nodes in current block.
     36 
     37 The solution becomes simple. Every *sqrt*(*m*) queries we make simple bfs and for every node *v* WE calculate value *d*[*v*] — the shortest distance to some red node from node *v*. Then to answer the query of type 2 you should calculate *min*(*d*[*v*], *dist*(*v*, *u*)), where *u* — every red node, which becomes red in current block of length *sqrt*(*m*).
     38 
     39 Distance between two nodes *dist*(*u*, *v*) can be got using preprocessing for lca.