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")