codeforces-scrape

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

242.md (3678B)


      1 Source: https://codeforces.com/blog/entry/5837
      2 
      3 ## [242A - Heads or Tails](/contest/242/problem/A "Codeforces Round 149 (Div. 2)")
      4 
      5 This problem was very easy, we should only use two cycles with *i* and with *j* (*a* ≤ *i* ≤ *x*, *b* ≤ *j* ≤ *y*), iterate all possible outcomes of the game and print such in that *i* > *j*. The time is *O*(*x*·*y*).
      6 
      7 ## [242B - Big Segment](/contest/242/problem/B "Codeforces Round 149 (Div. 2)")
      8 
      9 At first, we must note that the answer is always unique, because if segment *i* covers segment *j*, that segment *j* can't cover segment *i*. It possible if and only if there are coincide segments in the set, but it's not permissible by the statement. Let's pay attention the answer covers the most left point of all segments and the most right point of all points too. Now then we should found *L* = *min*(*l**i*) and *R* = *max*(*r**i*) and print index of segment [*L*, *R*], or  - 1 if there is no such segment in the set. The time is *O*(*n*).
     10 
     11 ## [242C - King's Path](/contest/242/problem/C "Codeforces Round 149 (Div. 2)")
     12 
     13 The most important thing for accepted solution is that it is guaranteed that the total length of all given segments doesn't exceed 105. We should use this feature, let's number allowed cells and found shortest path by BFS. It's easiest to use associative array such as map in C++ for numbering. The time is *O*(*n*·*log*(*n*)).
     14 
     15 ## [242D - Dispute](/contest/242/problem/D "Codeforces Round 149 (Div. 2)")
     16 
     17 Denote current value of counter number *i* as *b**i*. Let's describe an algorithm. It takes any counter *i* such that *b**i* = *a**i* and presses its button. The algorithm finishes if there is no such *i*.
     18 
     19 Let's proof correctness of the algorithm:
     20 
     21 1. Why does Valera win the game? Because there is no such counter which has *b**i* = *a**i* else we must press the button.
     22 2. Why doesn't algorithm press some button multiple times? Because it presses button number *i* only if *b**i* = *a**i*, and after this pressing the value *b**i* is increased and the equation will be true never.
     23 3. Why is the algorithm fast? Because of paragraph 2 it does no more *n* pressings which produces no more *n* + 2·*m* increases of the counters. We should use queue for fast seaching counters which has *b**i* = *a**i* like this: every time we change value of the counter numbered *i* we check equation *b**i* = *a**i* and if it's true then we push value *i* to the queue. It's easy to understand that all indexes *i* will be in queue no more one time.
     24 
     25 Also these paragraphs proof that the answer always exists. You must print  - 1 never. The time is *O*(*n* + *m*).
     26 
     27 ## [242E - XOR on Segment](/contest/242/problem/E "Codeforces Round 149 (Div. 2)")
     28 
     29 Let's write numbers *a*1, *a*2, ..., *a**n* as a table which has size *n* × 20, and *b**i*, *j* is *j*th bit in *a**i*. Then sum of numbers on segment [*l*, *r*] equals ![](https://espresso.codeforces.com/1205951a3534dc7b9fd810393cae798cfed6de87.png). The last notation helps us to process queries.
     30 
     31 For fast implementation we should use 20 binary trees like cartesian trees or range trees. Every tree matchs one of bits (and matchs one of the columns of the table *b**i*, *j*).
     32 
     33 1. calculation of sum is equal to counting 1-s from *l*-th to *r*-th.
     34 2. operation "xor" equals reversing all bits from *l*-th to *r*-th (i.e. 0 changes to 1, 1 changes to 0).
     35 
     36 The first operation executes for all bit numbers, the second executes only for bits in which input number *x**i* has ones.
     37 
     38 These operations may be easy implemented with binary trees. The time is *O*(*m*·*log*(*n*)·20).