codeforces-scrape

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

1715.md (7110B)


      1 Source: https://codeforces.com/blog/entry/104261
      2 
      3 Hello, Сodeforces!
      4 
      5 We are very grateful for Your participation in our round.
      6 
      7 Thanks to [Qwerty1232](/profile/Qwerty1232 "Master Qwerty1232") for the help with this editorial.
      8 
      9 [1715A - Crossmarket](/contest/1715/problem/A "Codeforces Round 816 (Div. 2)")
     10 
     11 **Advice #0**
     12 
     13 *Just to it. The testing system is here for the testing. Send your solution.*
     14 
     15 **Hint #1**
     16 
     17 If $(n; m) \neq (1; 1)$, then: - Stanley should teleport at most once - Megan shouldn't use portals at all
     18 
     19 **Hint #2**
     20 
     21 Stanley and Megan gonna move only toward their destinations (Stanley will increase $x$ and $y$, Megan will decrease $x$ and increase $y$.
     22 
     23 **Hint #3**
     24 
     25 Megan can move along one route, which is the same regardless of board size.
     26 
     27 **Solution**
     28 
     29 ### [1715A - Crossmarket](/contest/1715/problem/A "Codeforces Round 816 (Div. 2)")
     30 
     31 *For convenience let's define going upward as decreasing $x$ coordinate, downward — increasing $x$, left — decreasing $y$, right — increasing y.*
     32 
     33 One of the optimal solutions is the following:
     34 
     35 * Megan goes upward to Stanley, she spends $(n - 1)$ units of energy for that. Then she goes right to her final destination by spending $(m - 1)$ more units of energy.
     36 * Stanley now has a choice: he obviously has to teleport from his starting position either all the way down, or right. He chooses what will save him the most energy, so he teleports along the greater wall of the shop for the 1 unit of power.
     37 * Then Stanley has to finish his route: he walks along the smaller side and spends $min(n, m) - 1$ more energy.
     38 
     39 If at least one of the dimensions is not $1$, then the answer is $(n - 1) + (m - 1) + 1 + (min(n, m) - 1) = min(n, m) + n + m - 2$. In case where $(n, m) = (1, 1)$ answer is $0$.
     40 
     41 **Normal proof**
     42 
     43 ### [1715A - Crossmarket](/contest/1715/problem/A "Codeforces Round 816 (Div. 2)")
     44 
     45 Obviously, except for 1 case, it is always beneficial for Stanley to use teleportation. Let the first portal he visited be $A$, and the last is $B$. It is also obvious, that teleporting for more than 1 time makes no sense, so that's why we consider, that he always teleports from $A$ to $B$ and that's it.
     46 
     47 For the sake of convenience let's define manhattan distance between two points as $dist(P_1, P_2) = |{P_1}_x - {P_2}_x| + |{P_1}_y - {P_2}_y|$.
     48 
     49 Consider the next few cases for the relative position of those two portals:
     50 
     51 1. $A_x \le B_x$ and $Ay \gt By$
     52 
     53 Megan must make at least $(n-1) + (m-1)$ moves. The portal does not help Stanley in the $y$ direction, so he must make at least $(m-1)$ moves.
     54 
     55 1. $A_x \gt B_x$ and $A_y \le B_y$
     56 
     57 Megan must make at least $(n-1) + (m-1)$ moves. The portal does not help Stanley in the $x$ direction, so he must make at least $(n-1)$ moves.
     58 
     59 1. $A_x \le Bx$ and $Ay \le By$
     60 
     61 Megan must make at least $dist(A,B)$ moves between $A$ and $B$. Going between A and B either undoes Megan's progress in the $x$ direction or $y$ direction (depending on which is visited first), so she must make at least an additional $(n-1) or (m-1)$ moves. Stanley must make at least $(n-1) + (m-1) - dist(A,B)$ moves.
     62 
     63 1. $Ax \gt Bx$ and $Ay \gt By$
     64 
     65 Megan must make at least $(n-1) + (m-1)$ moves. Using the portal undoes Stanley's progress in both the x and y directions, so he must make at least $(n-1) + (m-1)$ moves.
     66 
     67 In all cases, the total number of moves is at least (n-1) + (m-1) + min(n-1, m-1).
     68 
     69 **Proof, director's cut (or how you should not do)**
     70 
     71 In a while, after I came up with an idea for this task, I got excited to proof it formally. I was very happy with the result — A's proof was longer than a regular editorial for Fdiv2, or even Fdiv1. A couple of days before the round [Monogon](/profile/Monogon "Grandmaster Monogon") told us that there is a solution much easier to understand, for which I am very grateful! But I would like to save the original version as an example, of how you should not prove the easiest task in your contest.
     72 
     73 Tutorial is loading...
     74 
     75 * С++ code: [169161824](/contest/1715/submission/169161824 "Submission 169161824 by ilyakrasnovv")
     76 * Python code: [169161508](/contest/1715/submission/169161508 "Submission 169161508 by ilyakrasnovv")
     77 * Kotlin code: [169161674](/contest/1715/submission/169161674 "Submission 169161674 by ilyakrasnovv")
     78 
     79 [1715B - Beautiful Array](/contest/1715/problem/B "Codeforces Round 816 (Div. 2)")
     80 
     81 **Hint #1**
     82 
     83 Greedy.
     84 
     85 **Hint #2**
     86 
     87 * What are the limits of $s$ with all else being the same?
     88 * What is the number, which we can always add to a divisible by $x$, to keep the answer the same?
     89 
     90 **Hint #3**
     91 
     92 * $s$ is at least $x \cdot s$
     93 * maximum reminder mod $x$ is $x - 1$.
     94 
     95 **Solution**
     96 
     97 Tutorial is loading...
     98 
     99 * С++ code: [169162178](/contest/1715/submission/169162178 "Submission 169162178 by ilyakrasnovv")
    100 * Python code: [169161968](/contest/1715/submission/169161968 "Submission 169161968 by ilyakrasnovv")
    101 
    102 [1715C - Monoblock](/contest/1715/problem/C "Codeforces Round 816 (Div. 2)")
    103 
    104 **Hint #1**
    105 
    106 Look from the perspective of joints between blocks
    107 
    108 **Hint #2**
    109 
    110 For each pair of adjacent different numbers, calculate how many subsegments contain them.
    111 
    112 **Hint #3**
    113 
    114 To apply the changes, neighboring numbers and the position of the changing number are all we need to know.
    115 
    116 **Solution**
    117 
    118 Tutorial is loading...
    119 
    120 * С++ сode: [169162300](/contest/1715/submission/169162300 "Submission 169162300 by ilyakrasnovv")
    121 
    122 [1715D - 2+ doors](/contest/1715/problem/D "Codeforces Round 816 (Div. 2)")
    123 
    124 **Hint #1**
    125 
    126 We can solve the task separately by bits.
    127 
    128 **Hint #2**
    129 
    130 What are the most useful conditions? Those, that state that bitwise or of some bits in $i$-th and $j$-th numbers is $0$ because we can null both of these bits for sure.
    131 
    132 **Hint #3**
    133 
    134 Solve the task separately by bits. Firstly, satisfy conditions from the second hint, then try to null the bits from the beginning.
    135 
    136 **Solution**
    137 
    138 Tutorial is loading...
    139 
    140 * С++ сode: [169162393](/contest/1715/submission/169162393 "Submission 169162393 by ilyakrasnovv")
    141 
    142 [1715E - Long Way Home](/contest/1715/problem/E "Codeforces Round 816 (Div. 2)")
    143 
    144 **Hint 1**
    145 
    146 For every $i$ from $1$ to $n$ find the shortest path from $1$ to $i$, ending with an air trip.
    147 
    148 **Hint 2**
    149 
    150 Can you solve the problem for $k = 1$?
    151 
    152 **Hint 3**
    153 
    154 If you have somehow solved the problem for $k = i$, how can you solve it for $k = i + 1$?
    155 
    156 **Solution**
    157 
    158 Tutorial is loading...
    159 
    160 * С++ сode: [169162508](/contest/1715/submission/169162508 "Submission 169162508 by ilyakrasnovv")
    161 
    162 [1715F - Crop Squares](/contest/1715/problem/F "Codeforces Round 816 (Div. 2)")
    163 
    164 **Advice #0**
    165 
    166 There is a lot of freedom, but there exists a very simple solution. If You think of something complicated such as advanced geometry, You are probably doing something wrong.
    167 
    168 **Hint #1**
    169 
    170 Try to think about sawtooth-like figures.
    171 
    172 **Hint #2**
    173 
    174 You can use only 2 queries.
    175 
    176 **Hint #3**
    177 
    178 The figure is periodic. Both of those queries use the same figure, but in one query it is rotated by $90^\circ$.
    179 
    180 **Solution**
    181 
    182 Tutorial is loading...
    183 
    184 * С++ сode: [169162576](/contest/1715/submission/169162576 "Submission 169162576 by ilyakrasnovv")