codeforces-scrape

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

283.md (5425B)


      1 Source: https://codeforces.com/blog/entry/7037
      2 
      3 Hi Guys,
      4 
      5 Hope you enjoyed Round 174. :) I would like to add a few comments on some of the problems, beyond the [editorial.](//codeforces.com/blog/entry/7036)
      6 
      7 **div 2 A** ****
      8 
      9 If you know some math, you can actually solve this problem in ![](https://espresso.codeforces.com/e2041ab7e2abf2bcd39550e52ab52e41e79577d6.png) (!!!) You can show that the answer is φ (*p* - 1) where φ (*n*) is the number of positive integers *i* less than to *n* with *gcd*(*i*, *n*) = 1. To prove this we first show that there is always at least one primitive root ![](https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png) for all primes *p*. (This is a fairly well known result so I won’t prove it here, but you can find many proofs online) So now assume *g* is a primitive root ![](https://espresso.codeforces.com/bd9f488f8d7e5438bed614355cddc3bd0b662f87.png) Then, the set {*g*, *g*2, ... *g**p* - 1} is congruent to the set {1, 2, ... , *p* - 1}. Furthermore, its not hard to show that *g**i* is a primitive root if and only if *gcd*(*i*, *p* - 1) = 1,  (try it!) hence our formula φ (*p* - 1). φ (*n*) can be computed by getting the prime factors of *n*,  since ![](https://espresso.codeforces.com/bea62cd51adddd0ce49d8e38fd809994f2265ac1.png) so this gives us our ![](https://espresso.codeforces.com/fd3de7d1f9b01b9a2204c1bc19367f640ba96a17.png) algorithm. :)
     10 
     11 **div 1 D** ****
     12 
     13 Here is a full solution to Codeforces #174 div 1 D.
     14 
     15 Let ν2(*n*) denote the exponent of the largest power of 2 that divides *n*. For example ν2(5) = 0, ν2(96) = 5. Let *f*(*n*) denote the largest odd factor of *n*.
     16 
     17 Note the following formula for sum of arithmetic series:
     18 
     19 ![](https://espresso.codeforces.com/b0284728dd8296db7dc8d84630944f885966f029.png)
     20 
     21 I claim that the pair (*x*, *y*) is cool if and only if ![](https://espresso.codeforces.com/cf082e412900f8e982c2e615aadea481c42aa32c.png) and one of the following is true \begin{enumerate} \item ν2(*x*) + 1 = ν2(*y*) \item ν2(*y*) = 0 \end{enumerate} This can be proven by casework on the number on the parity of *y*.
     22 
     23 If *y* is odd, the average term of the arithmetic sequence is an integer, so *f*(*y*) = *y* divides *f*(*x*) and ν2(*y*) = 0.
     24 
     25 If *y* is even, the average is of the form .5·*k* where *k* is odd, so ![](https://espresso.codeforces.com/6e3343e515268095a0fbd3385ecdbf968c6b3a40.png) so it follows that *y* divides *x* so *f*(*y*) divides *f*(*x*),  and furthermore ![](https://espresso.codeforces.com/8645237ffd160404dddbf4f74b7604562008ff5e.png)
     26 
     27 From this observation it follows that for fixed *a**i*, *a**j*(*i* < *j*),  we can construct a cool sequence *a**i* = *b**i*, *b**i* + 1, ... *b**j* - 1, *b**j* = *a**j* if and only if ![](https://espresso.codeforces.com/5976c316bc44bd354902aff2835e85bf2fe02f57.png) and either ν2(*a**i*) + *j* - *i* = ν2(*a**j*) or ν2(*a**j*) ≤ *j* - *i* - 1.
     28 
     29 Now that we have this observation, we can finish the problem using dynamic programming where the *k*th state is the maximum number of *a**i* (*i* ≤ *k*) we can keep so that it is possible to make *a*1, ... *a**k* cool. Then the answer is just *n* - *max* (*dp*[1], *dp*[2], ..., *dp*[*n*]).
     30 
     31 **div 1 E** ****
     32 
     33 Here is a full solution to Codeforces 174 div 1 E. I find this problem beautiful. :)
     34 
     35 The first thing to note, is that, if you interpret the problem as a graph, you can compute the answer if you have the degrees (i.e. number of wins) of every cow. Call three cows ``unbalanced’’ if the is one cow that beats the other two. Note that every three cows is either unbalanced or balanced (there are no other configurations of three cows). Thus,
     36 
     37 ![](https://espresso.codeforces.com/74d91b7be63ae92e761b9bffb157e97bc689f2bf.png)
     38 
     39 So to count the number of balanced it suffices to count the number of unbalanced. But it is easy to show that ![](https://espresso.codeforces.com/f53be434bdaaa818b9402fcba26ff350268f1246.png) so ![](https://espresso.codeforces.com/60efc34b1da6de7b8a46d40c6394e2f3dfdc6d64.png)
     40 
     41 So now we have reduced the problem to computing the number of wins for each cow. If we do this the dumb way, this is O(MN^2), still way too slow.
     42 
     43 Sort the skill levels of the cows (the order of the *s**i* doesn’t actually matter). *s*1 is lowest skill Now consider an *n* × *n* grid where the *i*th row and *j*th column of the grid is a 1 if the match between cow *i* and cow *j* is flipped. The grid is initially all zeros and Farmer John’s query simply flips a rectangle of the form [*a*, *b*] × [*a*, *b*],  and the outdegree (#wins) of cow *i* is just (Number of 1’s in range [1,i — 1]) + (Number of 0’s in range [i + 1, N]) = (Number of 1’s in range [1,i — 1]) + (N — i — (Number of 1’s in range [i + 1, N]))
     44 
     45 We can process these queries and compute outdegrees using a sweep line with a seg tree on the interval [1,N]. The seg tree needs to handle queries of the form
     46 
     47 1. Flip all numbers (0->1, 1->0) in a range [*a*, *b*].
     48 2. Query number of 1’s in a range [*a*, *b*].
     49 
     50 Note that the seg tree needed to handle this is the same seg tree you need for problem ‘lites’ on USACO 2008 Gold <http://tjsct.wikidot.com/usaco-nov08-gold>.
     51 
     52 Once again, thanks for participating!
     53 
     54 abacadaea