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 = (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.
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 22000 doesn't fit in int64.
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.
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*108
Great thanks to Ilya Akolzin for his help in translation
Anyone has a faster alg ?
If you use Java for this problem, "dumb" solution (with constraint 26^4 for DP step) will get TLE. I wrote more complicated solution, where we count minimal value of recolorings in previous line, with which we can go to specified coloring of current line). This way we can get smaller constraint, cause we can sort values, and check only two of them.
If you want, you can check my solution (submission 70276), where I've implemented this algorithm.
I solved it easily . I save position had minimum value in previous step , it's POS1 , POS2 , DP[level,POS1,POS2] is minimum . In the next step , DP(level, A, B) = DP(level-1, POS1, POS2) + D if (POS1<>A) and (POS2 <> B)
Else DP(level, A, B) = min(DP(level-1, i, j)) + D , i = 0..25, j = 0..25,
After doing a few rounds of this competition though, I'm tired of solutions working in C and not Java :( Slower languages should be given more time (even like, 25% more, though it should probably be closer to 50%), or the time limit should just be larger. The ACM-ICPC does this.
"A customer came to Bob and asked to sell him a 2x MB memory stick. If Bob had such a stick, he sold it and got 2x berllars. "
I am unable to understand this.. suppose for example
in this bob should sell 2^5 to 1st customer because he have memory of that size..
or he will not sell to that customer and keep 2^10 memory to sell 2nd customer.
i completely misunderstood during contest...
Is there any way to know the input because i have got WA so many times...
someone please look at my code (71593 ) and tell me error i have tried lot to find out.