490A - Team Olympiad

The teams could be formed using greedy algorithm. We can choose any three children with different skills who are not participants of any team yet and form a new team using them. After some time we could not form any team, so the answer to the problem is minimum of the number of ones, twos and threes in given array. We can get O(N) solution if we add children with different skills into three different arrays. Also the problem could be solved in O(N²) — every iteration find new three children for new team.

490B - Queue

This problem can be solved constructively. Find the first student — it is a student with such number which can be found among a_i and could not be found among b_i (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number a_i of the first student equals 0, so his number is a number in pair [0, b_i].

After that we will find numbers of all other students beginning from the third. It can be easily done using penultimate found number. The number of the next student is a number b_i in such pair where a_i equals to number of penultimate found student number (that is a number in pair [ans[i - 2], b_i]). Look at the sample to understand the solution better.

490C - Hacking Cypher

At first, let’s check all prefixes of specified number — do they have remainder 0 when divided by the a? It can be done with asymptotic behavior O(N), where N -length of specified number C. If we have remainder of division by a of prefix, which ends in position pos, we can count remainder in position pos + 1: rema[pos + 1] = (rema[pos] * 10 + C[pos + 1]) % a.

Then we need to check suffixes.If we have remainder of division by b of suffix, which begin in position pos, we can count remainder of position pos - 1: remb[pos - 1] = (C[pos - 1] * P + remb[pos]) % b, where P — it is 10^(L - 1) module b, L — length of suffix (P we can count parallel).

Now let’s check all positions pos — can we cut specified number C in this position. We can do it if next four conditions performed: prefix of number C, which ends in pos is divisible by a; suffix of number C, which begin in pos + 1 is divisible by b; length of prefix and suffix more than 0; first digit of suffix is different from 0. If all four conditions performed we found answer. If we did not find any such positions, than print NO.

490D - Chocolate

We can change the numbers by dividing their by two or by dividing their by three and multiply two. Firstly remove all 2 and 3 from factorization of chocolate and determine equals their square or not. If their squares are not equals answer doesn’t exists. Otherwise calculate of difference between number of three in factorization, we should remove this amount of threes from the some chocolate, it depends from the sign, and recalculate difference between number of two in factorization and do the same.

490E - Restoring Increasing Sequence

Let’s iterate on specified numbers and try to make from current number minimal possible, which value more than value of previous number. Let’s current number is cur, previous number is prev.

If length of number cur less than length of number prev — let’s print NO, this problem has not solution.

If length of number cur more than length of number prev — replace all signs ? in number cur to digit 0, except case, when sign ? in first position — replace him on digit 1, because numbers in answer must be without leading zeroes.

Another case when lengths of numbers a and b are equal. Let’s iterate on positions pos, in which prefix number cur more than prefix of number prev. Now we need to try for this position make minimal possible number, which more than prev. In all positions pos_i, which less than pos, replace all ? on prev[pos_i]. In all positions pos_i, which more than pos, replace all ? on digit 0. If cur[pos] =  = ? than make cur[pos] = max(prev[pos] + 1, 9).

If received number less or equal to prev — this position is bad. From all good positions choose minimal number, received with operations above and assign him number cur and will continue iteration. If count of such positions is 0 we need to print NO.

490F - Treeland Tour

The problem is generalization of finding maximal increasing subsequence in array, so it probably can be solved using dynamic programming. We will calс dynamic d[(u, v)], the state is directed edge (u, v) in tree. Value d[(u, v)] means the maximum number of vertices where the band will have concerts on some simple path ended in vertex v going through vertex u. Also the concert in vertex v must be certainly.

To calc d(u, v) we should consider all such edges (x, y) that there is simple path started in x, going through y, u and ended in v. These edges can be found using dfs from vertex u which is not going through vertex v. All edges used by dfs should be reoriented. So if r[y] < r[v] then d[(u, v)] = max(d[(u, v)], d[(x, y)] + 1). The solution needs O(N²) time and O(N²) memory. The memory could be O(N) if you get indexes of directed edges without two-dimensional array.