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.
dp[i][a][b] = 6666666;
for (int c=0; c<26; c++) if (c != a)
for (int d=0; d<26; d++)
if (d != b && c != d && dp[i-1][c][d] + rec[i-1][a][b] < dp[i][a][b]) {
dp[i][a][b] = dp[i-1][c][d] + rec[i-1][a][b];
w[i][a][b][0] = c;
w[i][a][b][1] = d;
}
to:
...
int best = 66666666;
for (int c = 0; c < 26; c++)
if (c != a) {
for (int d = 0; d < 26; d++)
if (d != b && c != d
&& dp[i - 1][c][d] < best) {
best = dp[i - 1][c][d];
w[i][a][b][0] = c;
w[i][a][b][1] = d;
}
}
dp[i][a][b] = best + rec[i-1][a][b];
...
I passed all the tests. The new version eliminates N*M*26*26*26*26*2 plus operations.
This is a nice lesson. Players using Java need keep one eye on the optimization.
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.
For Problem B One solution is you apply brute force i.e. you keep moving your grasshopper d distance right and update the platform and see if it voilates and doesn't lie on any of it print it .. but that would give a TLE on test cases because your solution is O(number of jumps possible ) which can be very large for the input link to sol
http://codeforces.com/contest/18/submission/31035456
a better approach is .. we iterate over the number of platforms and for each platform find how many jumps are required to reach current platform last point i.e. ((k -1 ) * m + l ) /d and so the grasshopper would be at distance ( ( ( k -1 ) * m + l) /d +1 ) * d for the next jump if this value is less than the starting distance of the next platform it will voilate the condition and bob is out of game since we're iterating over the number of platforms so it's O(n) solution and doesn't gives a TLE ..
link to the solution
http://codeforces.com/contest/18/submission/31036646
problem C is too easy ..
what is the meaning of first level rows in problem E .
The last row will be ABABA.... how ?
do we have to calculate the value of D only for the first row or for each row ?
can anyone explain 18E in more detail !!