When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Gerald's blog

By Gerald, 12 years ago, translation, In English

152A - Marks

In this problem you should do exactly what is written in the statement. Here is rough code of solution:

for (int i = 0; i < n; ++i){   
    bool wasBest = false;
    for(int j = 0; j < m; ++j){
        bool isBest = true;
        for(int k = 0; k < n; ++k)
            if(a[k][j] > a[i][j])
                isBest = false;
        if(isBest)        
            wasBest = true;
    }
    if(wasBest)
        ans++;
}      

152B - Steps

Let's find a formula for the position (x, y) and vector (dx, dy), how many steps to stop the boy can do. You should use "almost" binary search, for example, see the code written by RAD.

for (long long cof = 1100000000; cof; cof /= 2)
    while (onField(xc + cof * dx, yc + cof * dy)) {
        xc = xc + cof * dx;
        yc = yc + cof * dy;
        ans += cof;
    }      

152C - Pocket Book

In this task, it was necessary to understand that in position 1 Vasya can get any name of a special form. More exactly, it's the name of form s = s1 s2 s3 s4 ... sm, where s1 — the first letter of any of the names, s2 — the second letter of any of the names, ... smm-th letter of any of the names. Then the answer to the problem is the product of cnti (1 ≤ i ≤ m), where cnti is a number of different letters in the names placed in position i.

152D - Frames

It was necessary to understand if there are two borders or not.

Let's distinguish those x — and y-coordinates, in which there are at least 3 consecutive symbols '#', becouse the length of each border is no less then 3. It is clear that the coordinates of the corners of borders should be chosen only from those selected x and y. In general, the various selected x no more then 4 and various selected y no more then 4.

Except that case when the height or width of the first border is 3, and length of the second side of this border is more than 3, and one side of the second border fills a part of the inside first at least.

For example:

#######
#######
#######
#.....#
#######

The first border:

#######
#.....#
#######
.......
.......

The second border:

.......
#######
#.....#
#.....#
#######

There are 7 different y-coordinates in the example.

Carefully processed these cases separately, it is quite simple. (Let's choose 4 y-coordinates: minimum, maximum, second minimum and second maximum).

Otherwise, if the amount selected x — and y-coordinates no more then 4, then let's choose opposite corners of the first and second borders and verify that the selected borders — the correct borders and there are no other characters '#'. Checking is carried out at O(n + m) or O(1) (using partial sums).

152E - Garden

The solution of this problem is based on dynamic programming. dp[mask][v] — the value of the minimum correct concrete cover, if we consider as important elements only elements of the mask mask, and there are additionally covered the vertex v = (i, j) of the field.

There are two types of transfers.

First of all we can, as if to cut coverage on the vertex v. Then you need to go through subpattern of vertex submask, which will go to the left coverage and make an optimizing transfer. Update dp[mask][v] with the value dp[submask][v] + dp[mask ^ submask][v] - cost(v).

Second, perhaps in the vertex v in the optimal coverage mask mask, which covers the vertex v, you can not make the cut separating the set of vertices. In this case, this vertex forms something a kind of <>. And there a vertex u exists, on which we can make the cut, with the whole shortest path from a vertex u to v belongs to the optimal coverage. Let's precalculate the shortest paths between all pairs of cells. Now to make this transition, we should count the value of dynamics dp[mask][v] for all vertices v only on the basis of the first transition. Now you can make the second transition. For all u, dp[mask][v], update the value of dp[mask][u] + dist(v, u) - cost(u).

Let's process separately state in which exactly one bit in the mask, and the vertex which corresponding to this bit is equal to v. In this case the answer is equal to cost(v), of course.

Thus, each solution is obtained for the O(min(3k·n·m, 2k·(n·m)2)).

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

| Write comment?
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I was wondering if this idea is correct for task E ( I passed pretest in the competition but received WA10 at system test ). For each field of the matrix I run Dijkstra's algorithm with that field as source where cost ( u, v ) = Field[v] ( u and v are pairs of integers ). Then I reconstruct each paths from each of K important nodes to source and check if I have min path. Can you give me an example for which my idea fails or send me test #10. Thank you. :)

»
12 years ago, # |
  Vote: I like it +5 Vote: I do not like it

First time to write Dijkstra for task E, but it seems not the correct solution. Overall solution is not necessary to be shortest path for each pair.

»
12 years ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

I also have a solution similar to what they mentioned but a little different.
I try the following for each of the k! permutations of important nodes:

S={1stnode}
foreach i=2:k
1) Get shortest path between i and any of the nodes in S
2) Add cost of that path to total cost
3) Add nodes in that path to S
Minimize over all permutations.
It fails at test case 19 which is pretty large so I can even see fully. Can someone tell me what's wrong with the solution?

  • »
    »
    12 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    This is a simple 3*3 example(1 are important squares):

    2 1 2

    1 6 1

    2 1 2

    The answer is:

    10

    .X.

    XXX

    .X.

    Your solution's ans:

    12

    XXX

    X.X

    XXX

    Some nodes are useless if there are only 2 important squares(Only nodes in the shortest path is useful),but useful if there are many important squares. (Just think the square 6 above.It isn't in the shortest path of any pair important squares,but it's benefit for all the important squares.) So considering only one node each time is incorrect.

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I see your point. Thanks a lot :)

    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I tried this approach of minimization over all permutations of the k important nodes by doing the following:

      for each permutation

      i from 1:K-1:

      calculate the sortest path from i to i+1

      all grid positions along the shortest path are reseted to 0

      reset the grid to original after each permutation

      gets WA on test case 10. I wonder if this idea is simply wrong. By the way, it works for the sample given by coolingging.

»
12 years ago, # |
Rev. 12   Vote: I like it +7 Vote: I do not like it

I must confess I was a bit surprised at the "almost binary search" suggestion for problem B. You can just do straight divisions to check the maximum amount of steps possible!

if(dx > 0) ans = (n-xc)/dx;
if(dx < 0) ans = (xc-1)/-dx;
if(dy > 0) ans = min(ans, (m-yc)/dy);
if(dy < 0) ans = min(ans, (yc-1)/-dy);
xc += dx*ans;
yc += dy*ans;
»
12 years ago, # |
Rev. 2   Vote: I like it +24 Vote: I do not like it

Problem E is a good problem. I feel that i learned a lot.

»
12 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I think that E is a very good state of the compressed DP problem,and It is very similar with the 2008 Chinese Informatics Olympiad winter camp's test of trip ( tour plan ).I think tha they are all good.

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone tell what's the meaning of "name number 1" in problem statement C -> Link

I will be grateful.

Thanks.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also can't get the idea!! Since we are swapping prefix and i & j should be >=1 & <=n. thats a problem for me!! Is this possible that, After swapping I've got a new word then I can also perform swap operation on this??

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes!! I've got it in my manner. Suppose, you have ABC & DEF .. then the possible different names are ABC,DEF,AEF,DBF,ABF,DEC,AEC,DBC=8 . Go with some example in paper.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could anyone please give a more elaborate explanation of the solution of problem E.

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody plz explain what does v represent in dp[mask][v] as explained in the editorial of Question E Garden

»
18 months ago, # |
  Vote: I like it +9 Vote: I do not like it

In the complexity analysis of problem E, you forgot to account for all pairs' shortest paths precomputation. Usually one would use Floyd-Warshall for APSP with a complexity of $$$O((n \cdot m)^3)$$$. However, the graph in this problem is sparse with $$$|E| \le 4 |V|$$$, making a series of $$$O(|V|)$$$ Dijkstras another viable solution with the overall complexity of $$$O((n \cdot m)^2 \log (n \cdot m))$$$.