

Serega's blog

By Serega, 8 years ago, translation, In English,

Problem A. Epic Game.

Author's solution:

It's enough just to model the described game to solve this problem. You can search a greatest common divisor in any reasonable way.

Problem B. Before Exam.

Author's solution:

Let's consider solution of the task for maximum level of profience (for minimum level solution is similar). It's clear that maximum level can be reached either in a card that has fallen one somebody's lot already or in a card about that we know nothing. In the first case we can just calculate levels of profiency for all cards from input and choose maximal level. The second case is more tricky. Let's sort all the theorems that weren't mentioned in cards from input in order of non-increasing of profiency's level. It's obvious that sought-for card consists of first theorems in sorted list. This case is possible if the number of different cards mentioned in input is stictly less than k. For example, in the test

3 2
1 2 3

we can't consider a card containing third theorem because both examination cards are already known.

Problem C. Education Reform

Author's solution:

This problem can be solved by dynamic programming. Let's sort all subjects in order of complexity's non-increasing. Let d <  / span > [ < spanstyle = "" > i <  / span > ][ < spanstyle = "" > j <  / span > ][ < spanstyle = "" > z <  / span > ] is the greatest summary number of exercises, that can be given, if timetable contains exactly z subjects from among of first i subjects (in order of sort), involves ith subject and number of exercises in ith subject is equal to ai + j. Recurrent correlations are based on search of subject that will occupy ( < spanstyle = "" > z <  / span >  - 1)th day in timetable.

For restoration of answer you should save source numbers of subjects.

Asymptotic complexity is O(m2·n·max(bi - ai)).

Problem D. String Transformation

Author's solution:

If lengths of input strings aren't equal, we can at once output "-1 -1" and complete execution of a program. Otherwise let number n is equal to the length of input strings.

Let's iterate through the number i. We should
find (in O(1)) the such smallest number j, that substing b[0... n - i - 1] can be represented as a[i + 1... j - 1] + r(a[j... n - 1]). In order to do that, let's calculate the prefix function (p[i]) for string s1 = r(a) + ' 0' + b and z-function (z[i]) for string s2 = b + ' 0' + a. It's clear that for fixed i value of j is equal to n - p[2n - i - 1], and substrings a[i + 1... j - 1], b[0... j - i] must coincide at that (1). The last condition can be easily verified through using of calculated z-function. You can also trivial prove the next statement: if the property (1) is not satisfied by fixed i for the chosen j, then it will not meet for bigger j.

Asymptotic complexity is O(n).

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

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

Although this is a unreated round .. I am also get experience in this round ..
PS: I think Problem D is a good problem and it will have many many different solution.

8 years ago, # |

what's the meaning of the z-function?
is it same with prefix function?

  • 8 years ago, # ^ |
    No, prefix function tells you the length of the prefix that matches with where you are up to, that means that the last character in prefix will coincide with the character you are on.
    p[i] ->   s[0...p[i]] = s[i-p[i]....i]   

    The z function looks at the prefix too, but it searches forward, in other words, z[i] is going to tell you the length of the prefix that matches the substring starting at s[i] .
    z[i] ->   s[0..z[i]] = s[i....i+z[i]]
3 years ago, # |

Getting 'Denial of Judgement' error on my submission of Education Reform problem.

Any suggestions?

P.S. Code is a bit long