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(N2) — 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 ai and could not be found among bi (because he doesn’t stand behind for anybody). Find the second student — it is a student standing behind the first, number ai of the first student equals 0, so his number is a number in pair
Unable to parse markup [type=CF_TEX]
.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 bi in such pair where ai equals to number of penultimate found student number (that is a number in pair
Unable to parse markup [type=CF_TEX]
). 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
Unable to parse markup [type=CF_TEX]
, we can count remainder in positionUnable to parse markup [type=CF_TEX]
:Unable to parse markup [type=CF_TEX]
% a.Then we need to check suffixes.If we have remainder of division by b of suffix, which begin in position
Unable to parse markup [type=CF_TEX]
, we can count remainder of positionUnable to parse markup [type=CF_TEX]
:Unable to parse markup [type=CF_TEX]
% b, where P — it is 10^Unable to parse markup [type=CF_TEX]
module b, L — length of suffix (P we can count parallel).Now let’s check all positions
Unable to parse markup [type=CF_TEX]
— can we cut specified number C in this position. We can do it if next four conditions performed: prefix of number C, which ends inUnable to parse markup [type=CF_TEX]
is divisible by a; suffix of number C, which begin inUnable to parse markup [type=CF_TEX]
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 printUnable to parse markup [type=CF_TEX]
.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
Unable to parse markup [type=CF_TEX]
.If length of number cur less than length of number
Unable to parse markup [type=CF_TEX]
— let’s printUnable to parse markup [type=CF_TEX]
, this problem has not solution.If length of number cur more than length of number
Unable to parse markup [type=CF_TEX]
— 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
Unable to parse markup [type=CF_TEX]
, in which prefix number cur more than prefix of numberUnable to parse markup [type=CF_TEX]
. Now we need to try for this position make minimal possible number, which more thanUnable to parse markup [type=CF_TEX]
. In all positions posi, which less thanUnable to parse markup [type=CF_TEX]
, replace all ? onUnable to parse markup [type=CF_TEX]
. In all positions posi, which more thanUnable to parse markup [type=CF_TEX]
, replace all ? on digit 0. IfUnable to parse markup [type=CF_TEX]
than makeUnable to parse markup [type=CF_TEX]
.If received number less or equal to
Unable to parse markup [type=CF_TEX]
— 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 printUnable to parse markup [type=CF_TEX]
.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
Unable to parse markup [type=CF_TEX]
, the state is directed edge (u, v) in tree. ValueUnable to parse markup [type=CF_TEX]
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
Unable to parse markup [type=CF_TEX]
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 ifUnable to parse markup [type=CF_TEX]
thenUnable to parse markup [type=CF_TEX]
. The solution needsUnable to parse markup [type=CF_TEX]
time andUnable to parse markup [type=CF_TEX]
memory. The memory could be O(N) if you get indexes of directed edges without two-dimensional array.