riadwaw's blog

By riadwaw, 9 years ago, translation, In English

509A - Maximum in Table

In this problem one needed to implement what was written in the statement: create matrix (two-dimensional array) using given rules and find maximal value in the table.

It is also possible to see that maximal element is always in bottom-right corner.

Easier solution with recursion also was enough to get AC:

def elem(row, col):
    if row == 1 or col == 1:
        return 1
    return elem(row - 1, col) + elem(row, col - 1)

One may see the Pascal's triangle in the given matrix and understand that answer is equal to

Prepared by: riadwaw
Author of editorial: riadwaw

509B - Painting Pebbles

Suppose there are two piles with number of pebbles differed by more than k, then there is no solution:

Now let M = max ai ≤ min ai + k = m + k.
There's a way to construct correct coloring:

  • Chose m peebles from each pile and assign first color to them.
  • In each pile assign different colors to all other pebbles (you may use first color once more) (It's possible bacause there are no more than k uncolored pebbles.

Now there are m or m + 1 pebbles of first color and 0 or 1 pebbles of any other color in each pile.

Prepared by: Kostroma
Author of editorial: riadwaw

509C - Sums of Digits

The algorithm is greedy: first, take the minimal number with sum of digits a1 — call it b1. Then, on the i-th step take bi as the minimal number with sum of digits ai, which is more than bi - 1.

It can be easily proven that this algorithm gives an optimal answer. But how to solve the subproblem: given x and y, find the minimal number with sum of digits x, which is more than y?

We use a standard approach: iterate through the digits of y from right to left, trying to increase the current digit and somehow change the digits to the right in order to reach the sum of digits equal to x. Note that if we are considering the (k + 1)-th digit from the right and increase it, we can make the sum of k least significant digits to be any number between 0 and 9k. When we find such position, that increasing a digit in it and changing the least significant digits gives us a number with sum of digits x, we stop the process and obtain the answer. Note that if k least significant digits should have sum m (where 0 ≤ m ≤ 9k), we should obtain the answer greedily, going from the right to the left and putting to the position the largest digit we can.

Let us bound the maximal length of the answer, i.e. of bn. If some bi has at least 40 digits, than we take the minimal k such that 10k ≥ bi. Than between 10k and 10k + 1 there exist numbers with any sum of digits between 1 and 9k. If k ≥ 40, than 9k ≥ 300, which is the upper bound of all bi. So, in the constraints of the problem, bi + 1 will be less than 10k + 1. Than, similarly, bi + 2 < 10k + 2 and so on. So, the length of the answer increases by no more than one after reaching the length of 40. Consequently, the maximal length of the answer can't be more than 340.

The complexity of solution is O(n·maxLen). Since n ≤ 300, maxLen ≤ 340, the solution runs much faster the time limit.

Prepared by: Endagorion
Author of editorial: Kostroma

509D - Restoring Numbers

First we note that if the sequences ai and bi are a valid solution, then so are the sequences ai - P and bi + P for any integer P. This means that we can consider a1 to be equal to 0 which allows us to recover the sequence bi by simply taking the first row of the matrix. Knowing bi we can also recover ai (for example by subtracting b1 from the first column of the matrix) At this stage we allow ai and bi to contain negative numbers, which can be later fixed by adding K a sufficient amount of times. Now we consider the “error” matrix e: .

If e consists entirely of 0s, then we’ve found our solution by taking a sufficiently large K. That is: K > maxi, j(wi, j).

Otherwise, we note that ei, j = 0(modK) which implies that K is a divisor of g = gcdi, j(ei, j). The greatest such number is g itself, so all that remains is to check if g is strictly greater than all the elements of the matrix w. If that is the case, then we’ve found our solution by setting K = g. Otherwise, there’s no solution.

Prepared by: Kostroma, riadwaw
Author of editorial: riadwaw

509E - Pretty Song

We first calculate the prefix sums of vowel(si) which allows to calculate the sum of vowel(si) on any substring in O(1) time.

For all m from 1 to , we will calculate the sum of simple pretinesses of all substrings of that length, let’s call it SPm. For that purpose, let’s calculate the number of times the i-th character of the string s is included in this sum.

For m = 1 and m = |s|, every character is included exactly 1 time. For m = 2 and m = |s| - 1, the first and the last character are included 1 time and all other characters are included 2 times. For m = 3 and m = |s| - 2 the first and the last character are included 1 time, the second and the pre-last character are included 2 times and all others are included 3 times, and so on.

In general, the i-th character is included min(m, |s| - m + 1, i, |s| — i + 1) times. Note that when moving from substrings of length m to substrings of length m + 1, there are 2 ways in which the sum SP can change:

  1. If m > |s| - m + 1, then SP is decreased by the number of vowel occurrences in the substring from |s| - m + 1 to m.
  2. Otherwise, SP is increased by the number of vowel occurrences in the substring from m to |s| - m + 1.

This way we can easily recalculate SPm + 1 using SPm by adding (subtracting) the number of vowel occurrences on a substring (which is done in O(1) time). The complexity of this solution is O(N).

Prepared by: zemen
Author of editorial: zemen

509F - Progress Monitoring

Consider a tree with n vertices rooted at vertex 1 and let b be the pseudocode’s (DFS) resulting sequence. Then b[lv..lv + sizev - 1], represents vertex v’s subtree, where lv is the index of v in b and sizev is the size of $v$’s subtree.

Let’s solve the problem using this fact and Dynamic Programming. Let e[l, r] be the number of trees consisting of vertices a[l], a[l + 1], …, a[r] such that running DFS starting from a[l] will result in a sequence with vertices in the same order as their order in a.

The base case is when l = r and e[l, r] = 1. Otherwise, where the sum is taken over all partitions of the segment [l + 1, r], that is, over all k;pos1, ..., posk + 1, such that l + 1 = pos1 < pos2 < ... < posk + 1 = r, 1 ≤ k ≤ r - l, a[pos1] < a[pos2] < ... < a[posk]. Each such partition represents a different way to distribute the vertices among a[l]’s children’s subtrees. A solution using this formula for calculating e[l, r] will have an exponential running time.

The final idea is to introduce d[l, r]:  = e[l - 1, r], 2 ≤ l ≤ r ≤ n. It follows that: d[l, r] = ([statement] is equal to 1 if the statement is true, 0 otherwise) and e[l, r] = d[l + 1, r]. This way d[l, r] and e[l, r] can be calculated in linear time for any segment [l, r]. The answer to the problem is e[1, n]. Overall complexity is O(n3).

Prepared by: DPR-pavlin
Author of editorial: DPR-pavlin

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

| Write comment?
»
9 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Problem E can also be solved using DP as follows — The required answer is where . Define dp[i] to represent ls[i]. Then, dp[i+1] = dp[i] + h[n-i-1] — h[i+1], dp[0] = h[s.size()] where h[i] is the ith harmonic number. Link to my solution.

»
9 years ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Problem E: "If m > |s| - m + 1, then SP is decreased by the number of vowel occurrences in the substring from |s| - m + 1 to m." Shouldn't it be "from |s| - m + 1 to m — 1"? Consider the first example, IEAIAIO. For m = 4 the numbers of times characters are included form this sequence: 1, 2, 3, 4, 3, 2, 1. For m = 5 the sequence is as follows: 1, 2, 3, 3, 3, 2, 1. So SP decreased only by vowel from position 4, i.e. by vowels from |s| — m + 1 to m — 1. Second A is still included in 3 substrings.

PS "the numbers of times characters are included form this sequence" — did I write it correctly? If not, how should I write it in English? :)

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    You're correct. The proper indices should be from |s| - m - 1 to m when decreasing and from m to |s| - m - 1 when increasing (assuming the indices are 0-based).

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

      Actually "increasing" indices are correct, I think :)

      Example: IEAIAIO.

      For m = 1 you have: 1, 1, 1, 1, 1, 1, 1.

      And for m = 2: 1, 2, 2, 2, 2, 2, 1. So position |s| — m + 1 = 7 — 2 + 1 = 6 is also increased.

      Proof by example, my favourite type of "proof" ;)

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 4   Vote: I like it +3 Vote: I do not like it

        Edited 2: All right, I was thinking in different index bases, that explains it all. Okay so here's the deal: In the editorial we're moving from m to m + 1 and using the old m to calculcate the indices, while you're using m + 1. The editorial still needs correction, but you get the idea :)

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

For problem D:

Let M be the maximum number in W

If K > 2 * M, the modulus will change by some constant. So we can assume that: 2 * M >= K > M.

Of course the trial and error approach wouldn't pass. We can first assume that k = M + 1 (or any other value larger than this). If this caused any error we can then change K only one time to (2 * M minus current element that caused the error in W). If it caused another error then the answer must be "NO".

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

I set maxLen 300 in Problem C... I accepted after I changed it to 340

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

In the tutorial of C Problem. The last two paragraph, 'than' equals to 'then'?... Why not maxlength is 34, cause 34 * 9 = 306 > 300?

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

    Consider the following data: 300 300 1 1 ... 1 The length is 333.

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

Can someone write more detailed idea or pseudo-code of problem C solution, when you need to find next least number with same sum of digits?

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

    Look at each suffix of previous number, from left to right. If suffix begins with diggit c and has n digits, then c+1<=sum<=9n We are checking this condition, while its right. Let's pretend its false for suffix with N digits. Then we are changing digit on (N+1)-th place from c+1 to 9, trying to get number with fixed sum. If we can't do this, then we changing (N+2)-th digit, and go on and on, while we don't get required number

    Example: If we have number 391, and number with sum 10 to find, then suffix 391, sum is 10: we can get sum from 4 to 27. Go to next suffix

    suffix 91, sum is 7: we can get sum from 10 to 18 (yes, we cannot get sum 10, but this is not important). Condition is false. Go to previous suffix to increase third digit

    4??, sum is 6, we can do this with number 406.

    This algorithm can be realise with recurtion.

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

Now all editorial are available.

We are sorry for a delay.

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

Dirty Vasya didn't clean the table in a year :D

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

hmm....it is not important but my submission for 509C got accepted while it actually fails with a simple test case:

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

can someone please explain me the tutorial of pretty song in a more detailed way....I am unable to get what is written here!! :(

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

56 97 96 81 39 97 2 75 85 17 9 90 2 31 32 10 42 87 71 100 39 81 2 38 90 81 96 7 57 23 2 25 5 62 22 61 47 94 63 83 91 51 8 93 33 65 38 50 5 64 76 57 96 19 13 100 56 39 This test case is not satisfied by using the above approach for question B, can someone help me with it?