codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

490.md (5910B)


      1 Source: https://codeforces.com/blog/entry/14849
      2 
      3 ### [490A - Team Olympiad](/contest/490/problem/A "Codeforces Round 279 (Div. 2)")
      4 
      5 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*2) — every iteration find new three children for new team.
      6 
      7 ### [490B - Queue](/contest/490/problem/B "Codeforces Round 279 (Div. 2)")
      8 
      9 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*].
     10 
     11 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.
     12 
     13 ### [490C - Hacking Cypher](/contest/490/problem/C "Codeforces Round 279 (Div. 2)")
     14 
     15 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*.
     16 
     17 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).
     18 
     19 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*.
     20 
     21 ### [490D - Chocolate](/contest/490/problem/D "Codeforces Round 279 (Div. 2)")
     22 
     23 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.
     24 
     25 ### [490E - Restoring Increasing Sequence](/contest/490/problem/E "Codeforces Round 279 (Div. 2)")
     26 
     27 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*.
     28 
     29 If length of number *cur* less than length of number *prev* — let’s print *NO*, this problem has not solution.
     30 
     31 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.
     32 
     33 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).
     34 
     35 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*.
     36 
     37 ### [490F - Treeland Tour](/contest/490/problem/F "Codeforces Round 279 (Div. 2)")
     38 
     39 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.
     40 
     41 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*2) time and *O*(*N*2) memory. The memory could be *O*(*N*) if you get indexes of directed edges without two-dimensional array.