codeforces-scrape

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

374.md (4397B)


      1 Source: https://codeforces.com/blog/entry/10018
      2 
      3 [374A — Inna and the pink pony](https://codeforces.com/contest/374/problem/A)
      4 
      5 Lets find a solution for shifting a candy from the position (*x*1, *y*1) into position (*x*2, *y*2). On each step we shift (increase or decrease) *x*1 by *a* and *y*1 by *b*.
      6 
      7 It is not difficult to understand that if |*x*2 - *x*1| is not divisible by *a* and |*y*2 - *y*1| is divisible by *b* answer doesn't exist.
      8 
      9 We should also note that |*x*2 - *x*1| / *a* and |*y*2 - *y*1| / *b* Should be both even or odd as shifting is performed at a time for both values.
     10 
     11 We should also look up for a corner case when step dropes us out from the board.
     12 
     13 Now we can determine the way from (*x*1, *y*1) to (*x*2, *y*2) as *max*(|*x*1 - *x*2| / *a*, |*y*1 - *y*2| / *b*).
     14 
     15 Lets calculate it for all corners and choose minimum or determine that the answer doesn't exist.
     16 
     17 [374B — Инна и девять](https://codeforces.com/contest/374/problem/B)
     18 
     19 We can divide the task into subtasks because if two adjacent digits have sum none-9 the number transformation doesn't depends on other side relatively to the position between this two digits. It means we should divide our task into subtasks of kind: *x* or *xyxyxyx*...*xyxy* where *x* + *y* = 9. We should multiply all such answers because we are looking for the whole number of variants.
     20 
     21 For *x* answer is 1. What should we do for *xyxyxy*? Let its length is *s*. Then if *s* is even we simply receive *s* / 2 nines. If *s* is odd one digit (any of them) will stay. Thus each sequence *xyxyxyxyx*...*xyxyxy* with odd length *s* increases the answer IN *s* times.
     22 
     23 [374C — Inna and Dima](https://codeforces.com/contest/374/problem/C)
     24 
     25 Our task is tranformed to the task of finding cycle or maximal way, but lets solve it without any graphs.
     26 
     27 Lets run dfs from each digit *D*, memorizing all already calculated tasks. If we come into the cell we have already been (in one of the previous *D*) than we should simply add the maximal way length to our current length. Way length is increased not in each cell but only when we come into *A*. If we come into the cell we have already been on current step (in our dfs running) this is the cycle and we should stop the algorithm. Don't forget to change the color of cell after droping from recursiong because you will receive "false cycle". Simply set the colour to current when come into the cell but decrease it before end of recursion for this cell.
     28 
     29 [374D — Inna and sequence](https://codeforces.com/contest/374/problem/D)
     30 
     31 Lets note that not more than *n* numbers, thus it will be not more than *n* dropings. We will run this process using data structure Segment Tree (you can use another structures). Lets calculate the number of numbers in current segment. When the number is added we should simply go down from the root to the leaf and increase value for each segment on the way by 1. Deletetion — vice versa. If there is enough numbers in the left subtree we should go into the right one, othervise — into the left one. Don't forget to shift the *a**i* position by decreasing on *i* as all numbers are droped immidiately. And don't forget to break the cycle as soon as you reach first *a**i* such that there is no number to be droped out from it.
     32 
     33 [374E — Inna and babies](https://codeforces.com/contest/374/problem/E)
     34 
     35 We will make the binary search to find the answer. For each time let's generate our segments and rotate them to transform them into horizontal and verticle. We can use transformation (*x*, *y*) to (*x* + *y*, *x* - *y*). Don't forget to make the union of all segments which were at the one diagonal and have an intersection. You should sort all segments of one type and iterate through them updating the size of the segment. Now we should only determine if there is at least one rectangle. For example we can iterate each verticle segment updating the set of all horizontal which begin not later than our verticle. For each verticle (the left one) we should iterate the right verticle and now calculate the set of horizontal which not only begin not later than the left verticle but also don't end earlier than the right one. Now we should only determine is ther is two or more horizontal segments from the set which satisfy also y-conditions for current vertical.