Hello everyone!

Codeforces Round #156 will take place on Sunday, December 16th at 19:30 MSK. This is my second Codeforces round and I hope not the last.

I'd like to thank Steps09, Seyaua, sdya and Gerald for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

Problems’ point values are standart: 500-1000-1500-2000-2500.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

Contest is over, I hope it was interesting for you :)

Congratulations to div1 winners:
1). YuukaKazami
2). al13n
3). rng_58
4). Bigsophie
5). KADR

and div2 winners:
1). ShadowSong
2). ynbpdy072
3). jiaobu

You can view editorial here.

Sorry for my poor English, this blog will be corrected soon.

214A - System of Equations

Solution for this problem — just go through the possible pairs of numbers and check them for correctness. We can do that in any way.

214B - Hometask

Nuber is divisible by 2,3,5 only if sum of the digits is divisible by 3 and last digit is 0, so if we havent 0 in our set answer is -1, otherwise solution exists(we can return 0 as solution). A further solution — analysis of the cases.
Lets sort all didgits in nonincreasing order. If sum of all digits is divisible by 3 — answer is our set of digits(without spaces ofcourse :) ). If modulo equals 1 — we must delete minimum digit from out set with modulo after division by 3 equals 1, if we haven't such we must delete 2 minimal digits with modulo after division by 3 equals 2. If we have modulo equals 2 — we have identical case.
Also we must remember that we cannot use leading zeros. In case when we have more then one 0 and no another digit we must print only one zero.

213A - Game

Solution — Greedy.
Lets our computers settled on circle, and moves (1->2, 2->3, 3->1) will be steps "forward", and moves (1->3,3->2,2->1) will steps "back".

Note that "back" moves is not optimal, as we can make two moves "forward" that is identical in time. We will look over all starts. Further, we will go by circle while we not complited all game. For every level we will remember number ne[i] — count of another level that "direct" need for it. We will complited levels with ne[i]=0 and update all ne[i] that we must. It can be implemented with O(n^3) time.

213B - Numbers

Solution — dynamic programming.
Look over for length of the number that we will build. Further, we will use DP f(len,i) — how many numbers with length len we can make with digits i..9.
Recount:
- f(len,0) = sum(f(len-i,1)*C(len-1,i), i=a[0]..len);
- f(len,j) = sum(f(len-i,j+1)*C(len,i), i=a[j]..len), 0<j<9;
- f(len,9) = 1, если len>=a[9], 0 если len<a[9].
C(n,k) — binomial coefficient.

213C - Relay Race

Solution — dynamic programming.
Note, that we can make 2 pathes form cell (1,1) to cell (n,n).
Note, that after each move our cells will be located on the same diagonal.
We will solve the problem with DP f(d,i1,i2), d — diagonal number, i1 — 1st coordinate 1st path, i2 — 1st coordinate 2nd path. It is clear that we can calculate 2nd coordinate when we know number of the diagonal and 1st coordinate. Recount — obvious, we make all 4 transition, and if pathes are intersected in temporary point, we add value of the cell only one, otherwise we add both values of the cells. We can imlement this solution with O(n^2) memory if we will rewrite array of DP after increasing of diagonal number. Also we must remember that answer can be lower then 0.

213D - Stars

I present solution as few pictures:
https://get.google.com/albumarchive/pwa/115317317397602031319/Solutions131

Implementation.
We have only one difficult moment — how to count coordinates? We can calculate them from regular pentagon, all that you need, you can read there.

213E - Two Permutations

For given two permutation we will make two another by next transformation: New_A[A[i]] = i, where New_A — news permutation, A — given permutation. Lets we get two permutation A and B. Now our problem is next: how many sub-arrays of length n are equals to firs permutation. Two arrays will be equal if after swaping every element with its number in sorted array obtained arrays will be element-wise equal.
Further solution hashes, but we will use not only modulo 2^64, we will use some big modulos, but they must be smaller then 2^32-1.
Lets step[i] = 1000003^i.
Lets F(A) = num[1]*step[1] + num[2]*step[2] + ... + num[n]*step[n], where num[i] — number of the element A[i] in sorted array.
If we will compare arrays, we can use this function. But it can be very big, so we will count it by modulos.
So now our problem is to calculate F function to every subarray. Lets look what will change after adding/deleting some elent from set: some element from num array willnot change, and some will become grater after adding, and become lower after deleting. So we must use some interval-tree to recount our F function. We need to know sum of step[i] on some interval of added numbers and count of elements on some interval. Uses this information we can simply recount out function. Also we must remember that after adding element with coeficinet step[i], where i>n and deleting some previos element our function will become grater that we need. So we will multiple hash of first array by 1000003 to avoid this issue.

Hello everybody!

Welcome all to Codeforces Round #131, which will be held on Monday, 30th of July at 19:30 MSK. I am (Sergey Nagin) an author of the problems. This will be my First Codeforces round and I hope it won't be the last one :).

I would like to thank Mike Mirzayanov(MikeMirzayanov) who made this contest possible, Roman Furko(Furko) and Gerald Agapov(Gerald) for helping to prepare this round and Maria Belova(Delinur) for the translation of problem statements into English. I hope that problems will be interesting for you.

Good luck!

Problems’ point values in Division 1 are 1000-1000-1500-2000-2500. Problems’ point values in Division 2 are 500-1000-2000-2000-2500.

I strongly recommend you to read ALL the problems.

The contest is over! Congratulations' to winners!

First division:
1 place: Egor
2 place: Petr
3 place: tourist
Second division:
1 place: antimatter
2 place: c175353
3 place: takaramono

I hope, that problems were interesting for you.

You can view tutorial.

Hello!
I think it is time to create this post. If you know the team of any country(possibly preliminary), please write it in the comments.