codeforces-scrape

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

94.md (12529B)


      1 Source: https://codeforces.com/blog/entry/2208
      2 
      3 At first I tell about the contest at all.
      4 
      5 My problems in the contest were A-div2,  B-div2,  C-div2/A-div1,  E-div2/C-div1,  D-div1. I wanted to make only div.2 round, but then we decided to give you seven problems at both divisions. [MikeMirzayanov](../../../profile/MikeMirzayanov "Штаб, MikeMirzayanov") prepared the problem about milk pouring and [anonymous](../../../profile/anonymous "Майор anonymous") gave E-div1 problem. Also [RAD](../../../profile/RAD "Штаб, RAD") gave some advices to complicate problems Azembler and Flags a bit.  
      6 
      7 And now let's start analysis.  
      8   
      9   
     10 **Problem A (div.2) - Restoring Password**  
     11   
     12 Password was very easy to restore. You should just iterate over groups of 10 characters in the first string and over all codes. Then, if some number's code is equal to the group - print that number.  
     13   
     14 Here's the example: <http://pastebin.com/hMV0NcjN>
     15 
     16 **Problem B (div.2) - Friends**
     17 
     18 Let's construct the graph where vertices correspond to the people and edges correspond to the relationships. Then paint each edge in this way: edge will be red if the men connected by it are friends and black otherwise. Now let's think what is "three pairwise acquainted people" and "three pairwise unacquainted people". We see that they are cycles of only red and only black vertices correspondingly, and the length of these cycles is 3.
     19 
     20 Now we know the solution: write 3 "for" cycles, one cycle for one vertex, and check if the edges between these vertices are only red or only black.
     21 
     22 Here's the solution: <http://pastebin.com/gswaxGmM>
     23 
     24 Another way to solve it is to notice the answer is FAIL if and only if graph has exactly 5 edges and they all together form a cycle with a length 5. It's very funny solution, I think. Here's the code: <http://pastebin.com/09T0ixrJ>
     25 
     26 **Problem A (div.1) / C (div.2) - Frames**
     27 
     28 The problem is easy, but there were many tricky cases - and contestants show it successful :) I added almost all these cases to the pretests because I didn't want to arrange [Beta Round 60](https://codeforces.com/contest/65/standings).  
     29   
     30 So let's solve the problem. At first notice that the answer is not greater than 3 because we always can do three selections (maybe, some of them are empty): with first selection we select end of the first row, with second one - begin of the last row, and with last one - all remaining folders (they form the rectangle).  
     31 
     32 The best way is to find all cases with answer 1 and 2. Try to do it.  
     33   
     34 If the answer is 1, we can select all folders from *a* to *b* with one selection. There must be nothing hard to detect these cases:
     35 
     36 * first and last folders are in the same row (21 5 7 9);
     37 * first folder is in the first column, and the last folder - in the last column (21 5 1 15), сase *m* = 1 is included here;
     38 * first folder is in the first column, and the last folder is *n* (21 5 6 21). Case when we must select all folders is included here. I was very surprised when I saw that many contestants forgot about it.
     39 
     40 And these are the cases with answer 2:
     41 
     42 * first and last folders are in the adjacent rows (21 5 8 14);
     43 * first folder is in the first column (21 5 6 13);
     44 * last folder is in the last column (21 5 4 15);
     45 * last folder is *n* (21 5 4 21);
     46 * and another tricky case: if the column where first folder is located is just at right from the column where the last column is located (21 5 3 12).
     47 
     48 If no one of these conditions is true, answer is 3.
     49 
     50 Here's the solution: <http://pastebin.com/8QRytzzF>
     51 
     52   
     53 
     54 **Problem B (div.1) / D (div.2) - End of Exams**
     55 
     56 Greedy algorithm solves this problem. We should consecutively try to pour milk from each bottle into each available cup and in maximal possible amount.
     57 
     58 Also we always need to know, how much milk is in each bottle and each cup, for each cup - bottles from which we have poured milk, and for each bottle - cups into which we have poured milk.
     59 
     60 Writing it is not hard. But where is one special moment - if we compare real numbers, we must use EPS, or we can get WA on test 12 (50 1000 49). Some programs write NO on this test while answer is YES, because of wrong comparing of real numbers.
     61 
     62 It must be said that answer can be calculated in integers: just set the volume of milk in each bottle *mn*. And only when we will print the answer, we divide each volume by *mn* and multiply by *w*. All three jury solutions didn't think up this :)
     63 
     64 Here's the solution: <http://pastebin.com/HG5Nrxne> (be careful, it's not as beautiful as previous ones)  
     65   
     66   
     67 
     68 **Problem C (div.1) / E (div.2) - Azembler**
     69 
     70 I don't know why so few coders have solved it. Small limitations for *n* and big time limit - 5 seconds - hint that it's backtracking. Also, no need to be a soothsayer to understand that maximal answer is about 5.
     71 
     72 Solving it is clear. You should keep all current registers at the vector and call some function that goes over all current registers and calculate new values, then calls itself recursively. In that process we can also save the program itself.
     73 
     74 To avoid TLE you should not make recursive calls if the deep of recursion is larger than current answer, should not go to the states where you get a number larger than *n* or less than current biggest number. And if you reach exactly *n*, you should update answer and copy the program to the safe place.  
     75   
     76 There are some hacks to speed up this approach: for example, iterate over numbers in descending order (it works faster), but 5 seconds is such TLE that you can solve it any way. Or you can launch backtracking for the specific answer (increasing it) while the program won't be found (I don't know how this method is named in English). Also, some contestants have solved it using BFS.  
     77   
     78 Here are two solutions: standard backtracking (<http://pastebin.com/Z6ZF36st>) and backtracking for the specific answer (<http://pastebin.com/viiYF9CB>).  
     79   
     80   
     81 
     82 **Problem D (div.1) - Flags**
     83 
     84 I think my solution is not optimal, it's too long. Many solutions submitted during the contest are shorter. But I tell you about my solution.
     85 
     86 At first I solve the problem for the number of stripes equals *N* (or *L* = *R*).
     87 
     88 Let ![](https://espresso.codeforces.com/9621ef8d5edb86362dcec51e61f085a2263c9fc2.png) is the number of flags with exactly *N* stripes where symmetrical flags are not identical. Try to get the answer using this designation.  
     89   
     90 At first sight it seems that answer is ![](https://espresso.codeforces.com/ce8da7698b7b0a5d82a8c65d376451d6ca01051b.png). But it's not true for the palindromes. For example, for non-palindromes WBWB and BWBW we should count only one of them, but for the palindromes, such as WBW, it leads to mistake, because each palindrome is symmetrical to itself.  
     91 
     92 So for the flags with even number of stripes formula ![](https://espresso.codeforces.com/ce79d8f7746614d39c8b5069862ccee22830b990.png) is correct, because there are not palindromes among them. And if *N* is odd, the correct formula is ![](https://espresso.codeforces.com/d01619fb72ad092bfedf9308a1de79f0581ca6f4.png), where ![](https://espresso.codeforces.com/ea199e667c382aee7e3545af894350f7b567a147.png) is the number of palindromes with *N* stripes. Each palindrome is definited by its first ![](https://espresso.codeforces.com/63c959b21487b946201d882ef93da9adebc2d232.png) stripes, and we can write that ![](https://espresso.codeforces.com/1a883a6f692da56ac5ba073dd93ff7f43831b857.png).
     93 
     94 Now we can give an answer if we know how to calculate number of flags where symmetrical flags are not equal. Notice that if we know two last stripes of the flag, we can definitely say if we can add another stripe to its end.  
     95   
     96 Let's use dynamic programming. As a state we can take a vector ![](https://espresso.codeforces.com/295f8eac4e826d7c91037ab028edd66992db1d8e.png) with a length 8 where each its component keeps a number of flags with *N* stripes and definite two last colors (exactly 8 options). And ![](https://espresso.codeforces.com/06f03217a754789d2480c1ca2c1247555a6a5b2e.png) is total number of flags with *N* stripes.  
     97   
     98 As start state we can take vector ![](https://espresso.codeforces.com/30f303ca299c14d33d6a944b9d1193e841bf3960.png) which consists of ones (because there are 8 flags with a length 2, one flag for one possible combination of two colors). And how to calculate ![](https://espresso.codeforces.com/295f8eac4e826d7c91037ab028edd66992db1d8e.png)?  
     99   
    100 It turns out that there is some matrix *A* that ![](https://espresso.codeforces.com/146bfd72677b3dce326fc9f61acdf5b75ef73670.png). Its elements can be found even using pen and paper: for example, let's we have a combination of two last stripes WB. Then it's possible to add white or yellow stripe to the end, and the last stripes will be BW and BY correspondingly. It means that we can write 1 to the matrix where the row are BW or BY and the column is WB.  
    101   
    102 We're about the finish. It's obvious that ![](https://espresso.codeforces.com/394f57deba66448e718f367aff2a7c19c4669af2.png). Power of matrix can be calculated with a logarithmic time - that's because our problem is solved. And don't forget if *N* = 1 then answer is 4 and there's no need to do these calculations.  
    103   
    104 But it was only problem where *L* = *R*. Let's find a solution for the segment ![](https://espresso.codeforces.com/e72a6628091297fbd620239a22c552019512f9da.png).  
    105   
    106 I know two ways to do it. First way is to add a new component to the vector and new row and column to the matrix. This new component should keep the total number on the segment ![](https://espresso.codeforces.com/decd2237334dd88c5f3aa738c3d4b5a8032f29d6.png) (if *L* = 1, we can write "if" somewhere at the beginning of the program). And the matrix *A* should be changed a bit: try to do it by yourself.  
    107   
    108 I like the second way. As we did it earlier, we will find a number of flags where symmetrical ones are different, but on the segment ![](https://espresso.codeforces.com/e72a6628091297fbd620239a22c552019512f9da.png). It is equal to ![](https://espresso.codeforces.com/4ce9f3e037586b3d8c70e89bba59550655ab25d5.png). Let's learn how to calculate the sum *E* + *A* + ... + *A**N* quickly.  
    109   
    110 Let *b* is such maximal power of 2 that 2*b* - 1 ≤ *N*. We can write ![](https://espresso.codeforces.com/5b98dbd1da991b7486d1ad3f076c5ff056372a42.png).  
    111   
    112 And apply some math magic to the first part of the previous formula: ![](https://espresso.codeforces.com/e917c60b03d8556ec92f204ed0636155fb5372ab.png). And the expression in the brackets at the second part of that formula is... I think you've already understood it :)  
    113   
    114 We forgot about the palindromes, but it's very easy to calculate their number. Let's suppose that *L* and *R* are odd (if they are even, we can add one to *L* and substract one from *R*). Then ![](https://espresso.codeforces.com/2e122e1a4ffac11012deb3c6ccc4b9fb5a475a73.png).  
    115   
    116 That's all. Don't forget to apply "mod" operation after each operation and examine border cases carefully. And here's the solution: <http://pastebin.com/wHu1tPgd> (yes, "matrix" and "vector" type definitions are strange - I've totally forgotten how to write in Pascal)  
    117   
    118   
    119 **Problem E (div.1) - Lostborn**  
    120 
    121 This problem can be solved using inclusion-exclusion principle. If ![](https://espresso.codeforces.com/5cae17c3b325c06eda98c1bf8dae0f9eee9d9beb.png) is the answer, then the following formula works: ![](https://espresso.codeforces.com/8848834e791365cd3ead2cfe6b2ee15ff06d4297.png). But if you write only this recursive function, you get TLE. Many contestants got TLE and were hacked because they didn't run maximal test on their computers.
    122 
    123 And the others who sensed that something was wrong memorized the answers for small *n* and all *a**i*. For example, you can see solution by [rng_58](../../../profile/rng_58 "Полковник rng_58") who won the contest, or this solution: <http://pastebin.com/4kcfJdAi>.
    124 
    125 [anonymous](../../../profile/anonymous "Майор anonymous"), the author of this problem, wrote his thoughts about it there: [http://codeforces.com/blog/entry/2216](../2216) (but now there's only russian version). His solution works even if *n* = 1015 and it can be viewed here: [http://codeforces.com/problemset/status/93/E?order=BY_CONSUMED_TIME_ASC](https://codeforces.com/problemset/status/93/E?order=BY_CONSUMED_TIME_ASC). It seems that any solution submitted during the contest would get TLE if *n* = 1015.  
    126   
    127   
    128 Sorry for my English :)