ArtDitel's blog

Codeforces Beta Round #18(Div. 2) Tutorial
By ArtDitel, 11 years ago, translation, In English

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 = (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

 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (23)
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
In problem B you can also make the first m steps, and if after them the grasshopper didn't fall, it means that he'll fall only after all n platforms
→ Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Solution of problem E is not fast enough to pass it .I've tried to solve it by this alg. but still got TLE.
Anyone has a faster alg ?
→ Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    It was mentioned that it passes in C++, but not Java.
    → Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I faced the same issue. Estimated the complexity is about 40M, I did not implement the DP algo but tried another pre-mature greedy way. Failed. After the contest, I tried the DP implementation and got TLE.

    Second time to meet such issue when using java. Probably we could use smaller constraints for all of the players.
    → Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Thanks a lot. I am reading your solution.
      → Reply
    • 11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      Actually, dumb solution passes with pretty easy optimisation for java - for each step we will count number of recolorings needed for given color to be on odd position and same for even. This leads O(nm * 26^2 + n * 26^4) "dumb" solution to be O(nm * 26 + n * 26^4) which passes. See my solution for implimentation
      → Reply
      • 11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I have solution with this asymptotic, and it got TL. Unfortynately, I haven't find your solution, maybe something wrong with my eyes =)
        → Reply
      • 11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I did the optimization and got TLE. After I changed the most inner code from:
                            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.
        → Reply
    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      why so complex?
      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,
      → Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    I determine all possible checkerings of the the the previous row, and then sort them by non-decreasing cost. Then, for every checkering in the next row, just find the one with lowest cost that is compatible from the row above. This ends up being about O(n^2 log n) where n is ~650 = 26*25. This is less than 4,000,000.

    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.
    → Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could you help me with WA on test 25 problem D?
→ Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
think you!
→ Reply
  • 11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    That reminds me of:
    -SOS! We are sinking!
    -What are you thinking about?
    → Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem D: problem statement says that
"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
5
win 10
win 5
sell 5
win 1
sell 10
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.
→ Reply
  • 11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    He sold 2^5 to the 1st customer, but now he wants to know what was the optimal way to sell memory sticks, and for that he should have kept 2^10.
    → Reply
    • 11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      thank you for explaining ....
      i completely misunderstood during contest...
      → Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem D : wrong ans  Help ..
Is there any way to know the input because i have got WA so many times...
→ Reply
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem D : wrong ans  Help ..
someone please look at my code (71593 ) and tell me error i have tried lot to find out.
→ Reply
»
3 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C is too easy ..

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it -8 Vote: I do not like it

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

→ Reply