Hi Codeforces community. In this post I wan to tell about problem div2C/div1A. I waited for this round for a very long time, I sent my purposal 20th December. Approval came only 2 weeks ago, but some problems should be changed. Then I created a new problem (div2B), but I was unable to find something good about div1A. Then I remembered about my problem which was ready and was hidden in SPOJ. However, I today knew, that it was hidden, however problem could be found by link. I apologize to community and hope that you learned something or had fun solving other my problems.

735A - Ostap and Grasshopper

Problem on programming technique. You have to find at which positions are grasshoper and insect. If k does not divide the difference of position, then answer is NO. Otherwise we have to check positions pos+k, pos+2k, ..., where pos is the minimal poisiton of grasshoper and insect. If somewhere is an obstacle, then answer is NO, otherwise the answer is YES.

735B - Urbanization

First of all, note that n1+n2 chosen ones should be people with top (n1+n2) coeficients. Secondly, if the person with intelegence C will be in the first city then he will contribute to our overall IQ with C/n1 points. So, if n1<n2, then top-n1 ratings should be in the small city and the top-n2 from others — in the big city.

736A - Tennis Championship

Let us solve the inverse problem: at least how many competitors should be, if the champion will have n matches. Then there's obvious reccurrent formula: f(n+1)=f(n)+f(n-1) (Let us make the draw in a way, where the champion will play n matches to advance to finals and the runner-up played (n-1) matches to advance the final). So, we have to find the index of maximal fibunacci number which is no more that number in the input.

736B - Taxes

The first obvious fact is that the answer for prime numbers is 1. If the number is not prime, then the answer is at least 2. When is it possible? It is possible in 2 cases; when it is sum of 2 primes of its maximal divisor is 2. If 2 divides n, then so does integer n/2. n/2<=2=>n<=4=>n=4, where n is prime. According to Goldbach's conjecture, which is checked for all numbers no more than 10^9, every number is a sum of two prime numbers. Odd number can be sum of two primes, if (n-2) is prime (the only even prime number is 2). Otherwise, the answer is 3 — n=3+(n-3), (n-3) is sum of 2 primes, because it is even.

736C - Ostap and Tree

First of all, thanks to albert96 and GlebsHP for their help with the tutorial of this problem. Secondly, sorry for being late.

Problem can be solved by the method of dynamic programming. Let dp[v][i][j] be the number of possibilities to color subtree of vertex v in such a way that the closest black vertex is on depth i, and the closest white vertex — on depth j (we also store dp[v][-1][j] and dp[v][i][-1] in the cases where there are no black and white vertexes in diapason k of v respectively). In order to connect two subtrees, we can check all pairs (i,j) in both subtrees (by brute-force algorithm). Then let we have pair (a,c) in the first subtree and pair (b,d) in the second one. If min(a,c)+max(b,d)<=k, then we update value of current vertex.

Complexity of the algorithm O(n*k^4), which is acceptable for this particular problem (n — the number of vertexes, k^4 brute force search of pairs (a,b); (c,d)).

736D - Permutations

This problem consists of 3 ideas. Idea 1: remainder modulo 2 of the number of permutation is equal to the remainder modulo 2 of the determinant of the matrix whose entries are 1 if (ai,bi) is in our list and 0 otherwise. Idea 2: If we cahnge 1 by 0, then the determinant will differ by algebraic compliment. That is, if we count inverse matrix, than it will reflect reminders modulo 2 (B(m,n)=A'(m,n)/detA, detA is odd). Idea 3: Inverse matrix can be counted for O((n/32)^3) time. However, we can work is field of integers modulo 2. The summation can be replaced by XOR. So if we store in one "int" not a single but 32 numbers, then we can reduce our assymptocy to O(n^3/32), which is OK.

736E - Chess Championship

Suppose set (a1,a2,...,am). Then the list is valid if set {2m-2, 2m-4, 2m-6, ..., 0} majorizes the set {a1,a2,...,am}. Let us prove it! Part 1: Suppose n<=m. Top n players will play n(n-1)/2 games with each other and n(m-n) games with low-ranked contestants. In these games they will collect 2*n(n-1)/2 points (in each game there is exactly 2 points) for sure and at most 2*n*(m-n) points in games with others. So they will have at most 2*(n*(n-1)/2+n*(m-n))=2*((m-1)+(m-2)+...+(m-n)) points. Now construction: Let's construct results of participant with most points and then use recursion. Suppose the winner has even number of points (2*(m-n) for some n). Then we consider that he lost against contestants holding 2,3,4,...,n places and won against others. If champion had odd number of points (2*(m-n)-1 for some n), then we will construct the same results supposing that he draw with (n+1)th player instead of winning agianst him. It is easy to check that majorization is invariant, so in the end we will have to deal with 1 men competition, when set of scores {a1} is majorized by set {0}. So a1=0, and there is obvious construction for this case. So we have such an algorithm: we search for a compiment set which is majorized by {2m-2,2m-4,...,0}. If there is no such set answer is NO. Otherwise answer is YES and we construct our table as shown above. Assymptosy is O(m^2logm) (calling recursion m times, sorting the array (we can lose non-decreasing order because of poor results) and then passing on it linearly.

Hi Codeforces community! I am glad to announce that at 27 November 16:35 (GMT time) will take place Codeforces Round #382 for participants of both divisions.

Author of this round is me (albertg). I am from Armenia and the only Armenian author of any Codeforces round yet. (Sorry Edvard). This round is my second round and I hope this is not the last one! :) it is the last one. As usual, I'm thankful to the coordinator of Codeforces Gleb Evstropov (GlebsHP) for helping to prepare this round and Mike Mirzayanov (MikeMirzayanov) for wonderful platforms Codeforces and Polygon. Also special thanks to super_azbuka for an idea of a problem.

As usual, contestants will have 5 problems and 2 hours to solve the problems. In this round you should help Ostap Ibrahim Bender to reach Rio-de-Janeiro. Good luck and have fun!

UPD1: Scoring: div1 750-750-1500-2000-2500, div2 500-1000-1750-1750-2500.

UPD2: Editorial is posted.

UPD3: If somebody has question(s) about solutions of problems, please write me a personal message.

UPD4: Please read this.

UPD5: Editorial of problem div2E/div1C is posted.

493A - Vasya and Football

We need 2 arrays — for the first and second team, in which we must save "status" of the player — is he "clear", yellow carded or sent off. Then while inputing we must output the players name if he wasn't sent off, and after the event he must be sent off.

493B - Vasya and Wrestling

We need to vectors in which we will save points of first and second wrestlers, and two int-s, where we will save who made the last technique and what is the sum of all the numbers in the input. If the sum is not zero, we know the answer. Else we pass by the vectors, checking are there respective elements which are not equal. If yes — then we know the answer, else everything depends on who made the last technique.

493C - Vasya and Basketball

We need an array of pairs — in each pair we save the distance and the number of team. Then we sort the array. Then we assume that all the throws bring 3 points. Then we pass by the array and one of our numbers we decrease on 1 (which one — it depends on the second element of array). Then we compare it with our answer. In the end — we print our answer.

493D - Vasya and Chess

If n is odd, then black can win white doing all the moves symetric by the central line. Else white can win putting his queen on (1,2) (which is the lexicographicly smallest place) and play symetricly — never using the first row.

493E - Vasya and Polynomial

Let's discuss 2 case. 1) t!=1 и 2) t=1.

1) If our function is not constant (n>=1) than a is greater all the coefficients, so the only polynom can be the number b — in the a-ary counting system. We must only check that one and constant function.

2)if t=1 must be careful:

in case 1 1 1: the answer is inf,

in case 1 1 n: the answer is 0

in case 1 а а^x(x-integer, x>0): the answer is 1

in the other cases P(1) is greater than other coefficients.

Hi!

On 3rd December, 18:00 at Moscow will be Codeforces Round #281 (Div. 2). As usual Div. 1 contestants can take part out of contest.

This is my first Codeforces Round and I hope that this isn't the last one :)

Thanks to Maksim Akhmedov (Zlobober) for the help in making contest and MikeMirzayanov for Codeforces and Polygon platforms.

UPD1: The scoring will be dynamic.

UPD2: Contest is over. Thank to all participants. I hope you liked my contest.

UPD3: Editorial

UPD4 Top-5 contestants, congrats

1. ShiXingxing15

2. ganar27

3. Tim_LinYd

4. coolwyj

5. gaoyihan

Also congrats to gaoyihan, who solved problem E.

UPD5 Hack stats by kostka.