18.md (3560B)
1 Source: https://codeforces.com/blog/entry/463 2 3 [Contest discussion](https://codeforces.com/blog/entry/462) 4 5 ### Problem А. Triangle 6 7 Pythagorean theorem, brute force 8 9 In this problem you should implement a function, which takes three points and checks whether they form a right-angled triangle. There are a lot of ways to do so, but the simplest one is using a Pythagorean theorem. 10 11 You should use squared distances instead of taking roots to overcome problems related to precision errors. 12 13 To examine a triangle on almost-rightness, you can try to move each point in each of four possible directions and check the new triangle using our function. It's good and easy to use two arrays: dx={-1,0,1,0} and dy={0,1,0,-1} for moving. Then we can get the new coordinates of shifted point simply using the following code: 14 15 > for (int i = 0; i < 4; i ++) 16 17 > { 18 19 > > int x = dx[i] + px; 20 21 > > int y = dy[i] + py; 22 23 > } 24 25 ### Problem B. Platforms 26 27 Simulation 28 29 Illustrative picture: 30 31  32 33 In this problem you were to determine a coordinate where the grasshoper would fall down. To do so, let's keep the position of grasshoper at a certain moment of time. 34 To avoid TLE one should "move" the grasshoper along a platform in *O(1)* time (not in the cycle). The grasshoper will do *j = (righti-x)/d* jumps along platform "*i*", where *x* is the grasshoper's coordinate (he's standing at the platform), and *righti* is a right coordinate of the platform. So we can move the grasshoper on *j*d* to the right at once. 35 36 ### Problem C. Stripe 37 38 Brute force 39 40 One should keep two sums S1 ans S2, where S1 is the sum of all numbers on the left part of the stripe, and S2 is the sum of the right one. At the beginning S1 = 0 and S2 equals to the sum of all numbers of the stripe. Then we move the border of the parts within a cycle from left to right recalculating the values of S1 and S2 each iteration and increasing the answer when it's necessary. 41 42 ### Problem D. Seller Bob 43 44 Greedy, long arithmetics 45 46 In this problem we need big integers because the number 22000 doesn't fit in int64. 47 We are given an assertion that for every memory stick there will be at most one potential customer. Since 2x> 2x-1 + 2x-2 + ... 20, the earnings of selling the most expensive stick will be greater than the earnings of selling all other sticks. So we first try to sell the most expensive stick, then the second one and so on. So one should try to sell sticks in descending order of their costs. 48 49 ### Probelm E. Flag 2 50 51 Dynamic programming 52 53 In this problem one should use dynamic programming. Consider the function *DP(level, A, B)* (where *A* and *B* are the numbers of colors, from 0 to 25), which returns the minimal number of repaintings required to repaint the first level rows. The last row will be like *ABABAB...* 54 55 Consider recalculating of this function. First, calculate the number of repaintings required for row *level* to be like *ABABAB...* (let *D* will be this number). Obviously, the row can be painted so if the color of the first element of the previous row is not "*A*" and the second one - not "*B*" (it's a condition of adjacent cells not to have the same color) or it should be the first row. So *DP(level, A, B) = min(DP(level-1, i, j)) + D , i = 0..25, j = 0..25, i != j, i != B, j != A.* 56 57 Estimate the run time of our program: *O(N*26*26*(M+26*26))*, this value is smaller than *4*108* 58 59 **Great t****hanks to [Ilya Akolzin](https://codeforces.com/profile/OBepkJIokEP) for his help in translation**