Furko's blog

By Furko, 11 years ago, translation, In English

313A - Ilya and Bank Account

This problem is the easiest one. You need to use only div and mod functions. If n>0, then answer is n, else you need to delete one of two digits.

For better understanding you can look at solution.

313B - Ilya and Queries

Precalculate some array Ai, that Ai = 1, if si = si + 1, else Ai = 0. Now for any query (l, r), you need to find sum of Ai, that (l ≤ i < r). It is standart problem. For solving this problem you can precalcutate some another array Sum, where Sumi = A1 + A2 + ... + Ai. Then sum of interval (l, r) is Sum_r — Sum_{l-1}.

For better understanding you can look at solution.

313C - Ilya and Matrix

At the start sort array. Let Ci — number of times of entering the number in Aі optimal placement. Answer is sum of Ai * Ci for all i (1 ≤ i ≤ 4n). If we look at the array C, we can see that for maximal element C = n + 1 (for array with size 4n), then for second, third and fourth maximum elements C = n. On this basis we can see, that for array with non-increasing order answer calculate like Sum(1, 1) + Sum(1, 4) + Sum(1, 16) + ... + Sum(1, 4n). So, for solve this problem you have to know only sort.

For better understanding you can look at solution

313D - Ilya and Roads

To solve this problem you need to use dynamic programming. Let Fulli, j — minimal cost of covering interval (i, j). Fix left border and move right. You can solve this subtask with complexity O(nm) or O(nmlogn). Now we need to solve the standart problem of dynamic programming. Cover K points with intervals that have not intersect. This problem with square dynamic. dpi, j — minimal cost of covering j-points, if you look some prefix length i. Answer for all problem is minimal integer from dpi, j, (k ≤ j ≤ n).
To solve second part:

1) dpi + 1, j = min(dpi + 1, j, dpi, j) — skip point with number i + 1

2) dpk, j + len = min(dpk, j + len, dpi, j + Cost); Cost — cost of interval with length len, that ending at point k. We precalculate Cost at first part of solution.

For better understanding you can look at solution

313E - Ilya and Two Numbers

Author solution is harder than that which is offered by MrDindows. It is solution of MrDindows.

1) Get the number of our sequences in sorted by frequencies. Thus from the first sequence (hereinafter — the first type) — in a direct order from the second — to the contrary.

2) These numbers are put on the stack, where if, recording onto the stack of the second type, we find the number at the top of the first type, then this pair of extract and add to the answer.

3) At the end, obviously the stack we can find a number of properties of the second type and the first bottom — on. Then their grouping in response pairs with the start and end.

For better understanding you can look at solution.

Sorry for waiting.

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

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

thanks and great contest

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

Will the English editorial public?

»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

I still don't get problem D's explanation.

This editorial looks like it is written for those whom have already solved the problems, not for those who struggled with some.

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

    Me too. Please explain it clearly. DP[i,j] is explained really confusing.

    Thanks. GL & HF!

    • »
      »
      »
      11 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I will try to explain.

      First, lets define cost[i,j] as the minimum cost to fix interval [i,j]. This can be achieved by doing the following for each of the M companies that fixes the holes of the interval [a,b] with cost C: cost[a,l] = min(cost[a,l], C), a <= l <= b.

      Once cost[i,j] is defined lets define dp[i,j]. dp[i,j] stores the minimum cost to fix J holes using the interval [1,i]. With this definition our answer lies in dp[N,k] (N as defined by the problem statement, length of the road/amount of holes).

      Now lets look at the transitions of this state. To compute dp[i,j] I have to take into account:

      • a) not fixing any hole, or in other words, dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < i (with this I'm querying every interval [1,k] that is smaller than [1,i] that has already fixed J holes);

      • b) to fix k holes. The holes that we'are going to fix are the ones at the end ([i-k,i], 1 <= k <= i). So we will query the states dp[i,j] = min(dp[i,j], dp[i-k][j-k]+cost[i-k][i]) [1].

      This works because a) the problem statements says to "fix at LEAST k holes" b) it will not add the cost of a company more than one time (if you can't see this stare a bit longer at the code).

      [1] the indexes are not quite correct, take a look at my code: http://codeforces.com/contest/313/submission/3812990

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

        nice.

        but no need to calculate dp[i,j] = min(dp[i,j], dp[k,j], 1 <= k < i because these values do not change when you go to new "i". enough of this:dp[i][j] = min(dp[i][j], dp[i-1][j]);

        sorry for my english.

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

in problem C, i can't seem to understand why the sorting worked here. i was thinking of this to recursively divide the matrix at each step and then find the maximum of such submatrices and the maximum of whole matrix and then add them and then so on.

i don't understand how magically you sorted them and did those things mentioned above and it did what exactly is mentioned in the problem i.e dividing the matrix into submatrices.

can you make this problem C little clear to me especially WHY THIS SORTING ?

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

    Your largest matrix will have 4^N integers. At first, you will pick the largest number from it, right? Next, you break this largest matrix, into four smaller matrices. You will be picking four integers out of them, such that your overall beauty is maximised. That is only possible if these four matrices have the four largest numbers out of the 4^N integers in them. On next step, you get 16 smaller matrices, and you want them to have the largest 16 integers in them in order to maximise overall beauty. And so on...

    I hope you get the idea behind sorting now.

»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

wonder to know the harder "author solution" since the correctness of "MrDindows" is not that obvious.

can you explain more clearly?

thanks in advanced.

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

This is my idea but my code wasn't right for samples: First I define dp[i][j][k] = minimum cost to fix at least k holes in j first holes using first i companies. while companies are sorted by their right points. And the update: dp[i][j][k] = min (dp[i — 1][j][k], dp[i — 1][j — (j — company[i].left + 1)][k — (j — company[i].left)] + company[i].cost) I saw that the difference between second and third dimensions of dp is always the same, so I omitted third dimension. And so this dp is my solution: dp[i][j] = minimum cost to fix at least j — n + k holes in first j holes using first i companies while companies are sorted. Is this solution right ? :-?

  • »
    »
    11 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Your intervals are not intersect. Is it right? If its true, then its wrong, because your intervals may intersect. For example: 10 2 5 1 4 1 2 5 1

    You need to take 2 intervals, that covers 5 points. Is it clear now?

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

      I don't get why my solution doesn't satisfy this condition. :-?

      • »
        »
        »
        »
        11 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        You solution dont use intervals if they are intersect.

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

Div2 C Illya and Matrix can be solved using BFS by constructing a tree of maximum element in a submatrix (a tree very similar to Quad Tree/2D Segment Tree) also. You can refer following solution.

Implementation using Queue

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

    @divyank1 The main solution provided in the editorial is also very similar too. Thanks

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

313C gives a TLE on test 48 when submitted on GNU C++14, but the same code gets ACed when submitted on GNU C++.

Why is that the case?