codeforces-scrape

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

363.md (3530B)


      1 Source: https://codeforces.com/blog/entry/9537
      2 
      3 #### [363A - Soroban](/contest/363/problem/A "Codeforces Round 211 (Div. 2)")
      4 
      5 Not so much to say about this problem. You need to extract the digits of the given number (read it as string or repeteadly divide by 10 and take the remainders). Then carefully do the mapping of digits to its' representation.
      6 
      7 #### [363B - Fence](/contest/363/problem/B "Codeforces Round 211 (Div. 2)")
      8 
      9 Another easy problem. We need to calculate the sum of every consequtive segment of *k* planks. One way to do this is to calculate partial prefix sums: ![](https://espresso.codeforces.com/3e8013e18d9492d17d96a38800c1f26add0f6a80.png). Then the sum of heights of the planks *i*, *i* + 1, ..., *i* + *k* - 1 is *s**i* + *k* - 1 - *s**i* - 1. The other approach is to calculate the sum of the first *k* planks: *h*1 + *h*2 + ... + *h**k*. By subtracting *h*1 and adding *h**k* + 1 we get sum of *k* planks starting from the second plank. Then, by subtracting *h*2 and adding *h**k* + 2 we get sum of *k* planks starting from the third plank, and so on.
     10 
     11 #### [363C - Fixing Typos](/contest/363/problem/C "Codeforces Round 211 (Div. 2)")
     12 
     13 The general idea of the solution is the following: while there are three consequtive equal characters, remove any one of them. After that we can only have typos of the second type. So, if we have one couple of equal characters immediately after another couple of equal characters (*xxyy*), we need to decide which character to remove, *x* or *y*? Let's find the leftmost typo of the second type in the string. It is easy to see that we can always remove the character from the second couple.
     14 
     15 All these can be done in a single pass. Go through the characters of the given string and build the resulting string *ans*. Let's denote the current character as *ch*. If *ch* is equal to the last two characters of *ans*, skip *ch*. If *ch* is equal to the last character of *ans* and *ans*[*length*(*ans*) - 2] = *ans*[*length*(*ans*) - 3] (assume that *ans* is 1-indexed), skip *ch*. Otherwise, append *ch* to *ans*.
     16 
     17 #### [363D - Renting Bikes](/contest/363/problem/D "Codeforces Round 211 (Div. 2)")
     18 
     19 Let's do a binary search over the number of boys that can rent a bike. So let's say that we want to check whether it possible for *k* boys to rent bikes. If some *k* boys can rent a bike, then the *k* "richest" boys (with the most amount of personal money) also can do that. It is easy to see that if they can rent bikes, they can rent *k* cheapest bikes (if we first sort the bikes in increasing order of price, it will be just the first *k* bikes).
     20 
     21 So, take *k* richest boys and try to match them with *k* cheapest bikes, spending as much common budget as possible. The following algorithm works (try to understand and prove it before asking questions): take the boy with least number of money (of course, among the considered *k* richest) and try to give him the cheapest bike. If the boy has ehough personal money to rent this bike, use his money to do this. Otherwise, use all his money and take some money from the common budget. Continue this process with the second cheapest bike and the second "poorest among the richest" boys. This process can end in two ways: we will either run out of budget and fail to rent *k* bikes, or we will successfully rent these bikes.
     22 
     23 #### [363E - Two Circles](/contest/363/problem/E "Codeforces Round 211 (Div. 2)")
     24 
     25 Correct solution will be published later.