codeforces-scrape

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

625.md (5428B)


      1 Source: https://codeforces.com/blog/entry/23342
      2 
      3 ## [625A - Guest From the Past](/contest/625/problem/A "Codeforces Round 342 (Div. 2)")
      4 
      5 Idea author: collaboration, preparation: [feldsherov](/profile/feldsherov "Expert feldsherov").
      6 
      7 If we have at least *b* money then cost of one glass bottle is *b* - *c*. This means that if *a* ≤ *b* - *c* then we don't need to buy glass bottles, only plastic ones, and the answer will be ![](https://espresso.codeforces.com/e3b68d5863f079987693a72eab08dc42517850f5.png). Otherwise we need to buy glass bottles while we can. So, if we have at least *b* money, then we will buy ![](https://espresso.codeforces.com/e66d3171e28a8700a393c4d820b0c9a1e8a1ff71.png) glass bottles and then spend rest of the money on plastic ones. This is simple *O*(1) solution.
      8 
      9 ## [625B - War of the Corporations](/contest/625/problem/B "Codeforces Round 342 (Div. 2)")
     10 
     11 Idea author: [gustokashin](/profile/gustokashin "Expert gustokashin"), preparation: [thefacetakt](/profile/thefacetakt "Candidate Master thefacetakt").
     12 
     13 Lets find leftmost occurrence of the second word in the first one. We need to add # to remove this occurrence, so where we would like to put it? Instead of the last symbol of this occurrence to remove as many others as we can. After that we will continue this operation after the new # symbol. Simplest implementation of this idea works in *O*(|*S*|·|*T*|), but with the power of string algorithms (for example, Knuth–Morris–Pratt algorithm) we can do it in *O*(|*S*| + |*T*|) time.
     14 
     15 Hint/Bug/Feature: in Python language there is already function that does exactly what we need:
     16 
     17 ```
     18 print(input().count(input()))
     19 ```
     20 
     21 ## [625C - K-special Tables](/contest/625/problem/C "Codeforces Round 342 (Div. 2)")
     22 
     23 Idea author: Elena Andreeva, preparation: [wilwell](/profile/wilwell "Expert wilwell").
     24 
     25 Lets fill our table row by row greedily. We want to have maximal possible number on k-th place in the first row. After it we need at least *n* - *k* numbers greater than ours, so its maximum value is *n*2 - (*n* - *k*). If we select it then we are fixing all numbers after column *k* in the first row from *n*2 - (*n* - *k*) to *n*2. On the first *k* - 1 lets put smallest possible numbers 1,  2,  ... ,  *k* - 1. If we do the same thing in the second row then in the beginning it will have numbers from *k* to 2(*k* - 1), and from *k*-th position maximum possible values from *n*2 - (*n* - *k*) - (*n* - *k* + 1) to *n*2 - (*n* - *k* + 1). And so on we will fill all rows. With careful implementation we don't need to store whole matrix and we need only *O*(1) memory. Our algorithm works in *O*(*n*2) time.
     26 
     27 ## [625D - Finals in arithmetic](/contest/625/problem/D "Codeforces Round 342 (Div. 2)")
     28 
     29 Idea author: [Sender](/profile/Sender "Expert Sender"), preparation: [Sender](/profile/Sender "Expert Sender").
     30 
     31 Lets say that input has length of *n* digits, then size of answer can be *n* if we didn't carry 1 to the left out of addition, and *n* - 1 otherwise. Lets fix length *m* of our answer and denote *i*-th number in the representation as *a**i*. Then we know ![](https://espresso.codeforces.com/4178d4406e2e874ed18addab30249e52997558ea.png) from the rightmost digit of the sum. Lets figure out what does ![](https://espresso.codeforces.com/c2b0c489641e4748a608dce4eb1761a49645752c.png) equals to. If the remainder is 9, it means that ![](https://espresso.codeforces.com/0d5167c0d3eaef3ca21008a5b7e7dd79c548b2d7.png), because we can't get 19 out of the sum of two digits. Otherwise the result is defined uniquely by the fact that there was carrying 1 in the leftmost digit of the result or not. So after this we know *a*1 + *a**m*. It doesn't matter how we divide sum by two digits, because the result will be the same. After this we can uniquely identify the fact of carrying after the first digit of the result and before the last digit. Repeating this *m* / 2 times we will get candidate for the answer. In the end we will have *O*(*n*) solution.
     32 
     33 If you've missed the fact that every step is uniquely defined, then you could've wrote basically the same solution, but with dynamic programming.
     34 
     35 ## [625E - Frog Fights](/contest/625/problem/E "Codeforces Round 342 (Div. 2)")
     36 
     37 Idea author: Elena Andreeva, preparation: [iskhakovt](/profile/iskhakovt "Candidate Master iskhakovt").
     38 
     39 We want to efficiently simulate the process from the problem statement. Lets have a data structure with times of key events that could've happened during simulation (some frog removed other frog from the board). Lets remove earliest event from our data structure and apply it to the board, make a critical jump. After that the speed of the first frog will decrease and we will be forced to recount times of collision of this frog this its 2 neighbors. This data structure could be set from C++, TreeSet from Java or self-written Segment Tree. To quickly find out who are we gonna remove from the board after the jump lets store double-linked list of all frogs sorted by their positions. Technical part is to calculate time of the collision, but it can be easily done with the simple notion of linear movement of two points on a line. There could be at max *n* - 1 collisions, so whole solution will be ![](https://espresso.codeforces.com/5e7dae7c1838af7ba7570bdf02ff61029b043be6.png).