Contest discussion

Problem А. Triangle

Pythagorean theorem, brute force

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.

You should use squared distances instead of taking roots to overcome problems related to precision errors.

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:

for (int i = 0; i < 4; i ++)

{

int x = dx[i] + px;

int y = dy[i] + py;

}

Problem B. Platforms

Simulation

Illustrative picture:

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.
To avoid TLE one should "move" the grasshoper along a platform in O(1) time (not in the cycle). The grasshoper will do j = (right_i-x)/d jumps along platform "i", where x is the grasshoper's coordinate (he's standing at the platform), and right_i is a right coordinate of the platform. So we can move the grasshoper on j*d to the right at once.

Problem C. Stripe

Brute force

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.

Problem D. Seller Bob

Greedy, long arithmetics

In this problem we need big integers because the number 2²⁰⁰⁰ doesn't fit in int64.
We are given an assertion that for every memory stick there will be at most one potential customer. Since 2^x > 2^x-1 + 2^x-2 + ... 2⁰, 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.

Probelm E. Flag 2

Dynamic programming

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...

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.

Estimate the run time of our program: O(N*26*26*(M+26*26)), this value is smaller than 4*10⁸

Great thanks to Ilya Akolzin for his help in  translation