codeforces-scrape

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

120.md (4179B)


      1 Source: https://codeforces.com/blog/entry/2892
      2 
      3 You can leave your questions, suggestions and more beautiful in comments. 
      4 
      5 ### Problem A. Elevator
      6 
      7    
      8 
      9 You can either check all four cases or notice, that if we consider front/back equal to 0/1 (b) and decrease a by 1, then a XOR b became the answer (0/1). Time and memory consumption - *O*(1).
     10 
     11   
     12    
     13  
     14 
     15 ### Problem B. Quiz League
     16 
     17    
     18 
     19 Just write one loop: while *k*th question has already been asked, increase *k* by one and if *k* > *n* let *k* = 1. Time and memory consumpiton - *O*(*n*).
     20 
     21   
     22    
     23  
     24 
     25 ### Problem C. Winnie-the-Pooh and honey
     26 
     27    
     28 
     29 One of the possible solutions is direct emulation. Winnie won't do more than 3*n* iterations (because he can use each jar more than three times). You can emulate each iteration in *O*(*n*) (just find maximum in array). Summary time - *O*(*n*2) ≈ 104 operations, memory consumption - *O*(*n*)
     30 
     31 There is another shorter solution: let's notice that order of jars doesn't matter. Let's see how much honey from each jar will be eaten by Winnie and how much will be left to Piglet. If *a**i* ≥ 3*k* then Winnie will leave *a**i* - 3*k* kg of honey to Piglet. If *a**i* < 3*k* then he'll leave only ![](https://espresso.codeforces.com/54446ac33ef52a78c6ecd6ef97c35472a71abcc6.png) kg. Now solution is one loop. Time and memory consumption is *O*(*n*).
     32 
     33   
     34    
     35  
     36 
     37 ### Problem E. Put Knight!
     38 
     39    
     40 
     41 Petya wins if *n* is odd, Gena wins if *n* is even. It's quite easy to prove - just do symmetrical turns.
     42 
     43   
     44    
     45  
     46 
     47 ### Problem F. Spiders
     48 
     49    
     50 
     51 Answer is sum of all spiders' lengths. Use depth-first-search (started at all vertexes) to calculate length of each spider.
     52 
     53   
     54    
     55  
     56 
     57 ### Problem G. Boom
     58 
     59    
     60 
     61 It's simple realization problem. All you need is two-dimensional arrays and one queue. [Code](http://pastebin.com/wW3j4HHN)
     62 
     63   
     64    
     65  
     66 
     67 ### Problem H. Brevity is Soul of Wit
     68 
     69    
     70 
     71 Notice that there are only ![](https://espresso.codeforces.com/b1db0b68b3bae5f6fa486bf128749743e951ae6c.png) different strings that have length 4 or less. Then notice that each of input strings you can change to ![](https://espresso.codeforces.com/f85950ecd5890e21b0baedfd5d2c86c4a3f8813b.png) different short words at most (|*w**i*| is length of the *i*th word).
     72 
     73 Now let's make bipartite graph. One part is all source words, the second part is all short words and there is edge if and only if we can change word from the first part to the short word from the second part. Now our task is just find perfect matching in this graph. It can be done in *O*(*n*1· *m*) ≈ 200· 200· 385 = 15.4·106 operations which is enough.
     74 
     75   
     76    
     77  
     78 
     79 ### Problem I. Luck is in Numbers
     80 
     81    
     82 
     83 Unfortunately, my solution for this problem is rather big. If someone know beautiful one share it please.
     84 
     85 The main idea is very standard: let's fix some prefix of number, which is strictly greater than such prefix of source number. If we can get known what is maximal happiness for suffix of our number then we can solve the problem by just running down values for each number in suffix and checking that we still can reach necessary value of happiness.
     86 
     87 Now solution for this subproblem is just to fill suffix with eights and calculate the answer. It's good but takes a lot of time. We need to store old values and recalculate its in *O*(1). There are very simple formulas to do it.
     88 
     89   
     90    
     91  
     92 
     93 ### Problem J. Minimum sum
     94 
     95    
     96 
     97 Firstly you need to notice that you can turn all vectors in such way that all of them have non-negative coordinates and the answer will remain the same.
     98 
     99 And now we have the following problem: find two nearest points from the given set. It's standard divide-and-conquer problem, it's described in [Wikipedia](https://en.wikipedia.org/wiki/Closest_pair_of_points_problem).
    100 
    101 Also there is simpler solution (added by [diogen](/profile/diogen "Expert diogen")): let's sort all our points by distance from a random point far-far away. It's oblivious that if some points lie near each other, distance to this far point doesn't vary a lot. And now solution is run down for each point *C* points near it in the sorted array. *C* about 200 is enough to got Accepted.