codeforces-scrape

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

53.md (4339B)


      1 Source: https://codeforces.com/blog/entry/1065
      2 
      3 Let's go.  
      4   
      5 
      6 A. Autocomplete
      7 
      8   
      9 
     10 In this problem you should read the statement and solve in any way. One of the most simple solutions is read string and last visited pages, sort (even bubble source - 1003 isn't a lot, 3rd power because we need 100 operations to compare two strings), and rundown pages. When we find good string, we should write it and exit.  
     11 If there are no such one, write source string. 'Goodness' of string is checking with one *if* (to check lengths and avoid *RTE*) and *for*.  
     12    
     13   
     14 
     15 C. Froggy (Little Frog)
     16 
     17 IMHO it's the second difficulty problem. If you cannot see solution just after you saw the statement, you can write brute-force solution (rundown all permutation and check), run it for *n=10* and see beautiful answer.  
     18 Answer is *1 n 2 (n-1) 3 (n-2) 4 (n-3) ...* Let's define two pointers - *l* and *r*.Inthe beginning, the first one will point to 1, and the second one - to n. On odd positions write down *l* (and increase it), on even - *r* (and decrease it). Do it while *l <= r*.  
     19 Proof is rather easy: every jump is shorter than the previous one.  
     20   
     21 
     22 D. Physical education
     23 
     24   
     25 
     26 This problem is also very easy. The first thing we should learn is moving element from position *x* to position *y (y < x)*. Let's move *x* to position *x - 1* with one oblivious swap. Then to position *x -2*. And so on.  
     27 Now we want to make *a1=b1*. Find in *b* element, that equals *a1* and move it to the first position. Similarly we can make *a2=b2*. So, we have *n* steps and at every step we do *n - 1* swaps at the most. *n<=300*, so *n(n-1)<=89700<106*.  
     28   
     29 
     30 B. Blog photo
     31 
     32   
     33 
     34 Due to [bug in GCC](https://codeforces.com/blog/entry/1059) I've lost 25 minutes solving this problem. In the end I've used MSVC++.  
     35 But it was digression, now let's think.  
     36 The first thing we need to do is fix one side (which are power of two). Because there are two sides and copy-paste is great place for bugs it'll be better to make one more *for* from 1 to 2 and on the 2nd step swap *w* and *h*. It decreases amount of code.  
     37 Now we know that *h=2x*. We need to find such *w*, that *0.8 <= h/w <= 1.25.* Solve inequalities for *w*: *h/1.25 <= w <= h/0.8.* Because *w* is integer, it can take any value from *ceil(h/1.25)* to *floor(h/0.8)* inclusive. We need to maximize square and *h* is fixed, so our target is maximize *w*. We need to let *w=floor(h/0.8)* and check that it fit borders. If so - relax the answer.  
     38 It's *O(log2 h)* solution.  
     39 Possible bugs are:  
     40 
     41 * You calculate square in 32-bit type or like this: *int w = ..., h = ...; long long s = w * h;* In this case compiler calculate *w * h* **in 32-bit type first**, and then convert it to *long long*. Solution is *long long s = (long long)w * h*
     42 * *floor(0.9999999999)=0.* The *floor* function does not correspond with inaccuracy of floating point types. It can be solved either with adding something *eps* to number before calling *floor*, or with additional check that difference between *floor*'s result and source value is not greater than *1 - eps*.
     43 * p.s. The *floor* function is up to **8-9 times** slower that conversion to *int*.
     44 
     45   
     46 
     47 E. Dead ends
     48 
     49   
     50 
     51 The first thing you should notice -  - *n <= 10*. It means, that we have exponential solution and we can rundown some subsets.  
     52   
     53 Solution is dynamic programming *d[m][subm]* - number of ways to make connected tree from subgraph *m* (it's a bit mask) with dead ends *subm* (it's also a bit mask). Answer is sum of *d[2n-1][x]*, where *|x|=k* (size of *x* as a subset is *k*).  
     54 Recalculating isn't really hard. For empty subset and subset of two vertexes (either 0 or 1) answer is oblivious. Also you should know that there is no tree with exactly one dead end (it's easy to prove). Now for greater subsets: rundown *i* from *subm* - one of dead ends. Cut it off from tree along some edge to *b* (*b* shouldn't be a dead end, otherwise we got unconnected graph). Now we have tree with lower count of vertexes and either decreased 1 number of dead ends or with changed *i* to *b* (if *b* had exactly two neighbors). Answer for this tree we know already. In the end of summarizing we should divide answer by *k* - each tree has been taken as many times, as it has dead ends (*k*).
     55 
     56 p.s. I'll be glad if you tell me my mistakes in English.