Greetings Codeforces Community! We invite you to experience the monthly CodeChef Lunchtime for December. The 3-hour contest will offer 5 challenging problems to solve. It will be a great way to close this year on a happy note with your increased ratings!

The problem statements of the contest will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas.

I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

Setters: Nguyen Ngoc Trung (chemthan), Rami Alssadaqa (i_love_islam), Hasan Jaddouh (kingofnumbers)
Tester: Roman Bilyi (RomaWhite)
Statement Verifier: Jakub Safin (Xellos)
Mandarin Translator: Gedi Zheng (gediiiiiii)
Vietnamese Translator: Team VNOI (Songuku95)
Russian Translator: Fedor Korobeinikov (Mediocrity)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)

Contest Details:

• Start Date & Time: 28th December 2019 (1730 hrs) to 28th December 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
• Contest link: www.codechef.com/LTIME79
• Registration: You just need to have a CodeChef handle to participate. For all those who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.

Good Luck!
Hope to see you participating!!
Happy Programming!!

Greetings Codeforces Community!

CodeChef presents July Lunchtime contest! The 3-hour long contest is jam-packed with engrossing problems that is sure to be an absolute treat for you. So, get ready to code and compete!

Further, if you have some engaging problem ideas and want them to be used in CodeChef's contests, you can share them with our admins here: www.codechef.com/problemsetting/new-ideas

Expecting to see you join your fellow coders and participate in the contest in large numbers. Joining me on the problem setting panel are:

• Setters: kingofnumbers (Hasan Jaddouh), Erfan.aa (Erfan Alimohammadi)
• Tester: RomaWhite (Roman Bilyi)
• Editorialist: vijju123 (Abhishek Pandey)
• Statement Verifier: Xellos (Jakub Safin)
• Mandarin Translator: gediiiiiii (Gedi Zheng)
• Vietnamese Translator: Team VNOI
• Russian Translator: Mediocrity (Fedor Korobeinikov)
• Bengali Translator: solaimanope (Mohammad Solaiman)

• Hindi Translator: Akash Shrivastava

  Contest Details:

• Start Date & Time: 27th July 2019 (1930 hrs) to 27th July 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
• Contest link: https://www.codechef.com/LTIME74
• Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
• Prizes: Top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://discuss.codechef.com/t/how-do-i-win-a-codechef-goodie/7344. (For those who have not yet got their previous winning, please send an email to winners@codechef.com) Good Luck!
  Hope to see you participating!!
  Happy Programming!!

Hello Codeforces!

I would like to invite you to participate in HackerEarth October Circuits. It's a long contest that will start on October 14, 21:00 IST. Contest will run for 8 days.

The problem set consists of 7 traditional algorithmic tasks and 1 approximate problem. For traditional algorithmic tasks, you will receive points for every test case your solution passes — so you can get some points with partial solutions as well. For the approximation task, your score depends on the best solution in the contest so far. Check contest page for more details about in-contest schedule and rules.

Xsquare, rivudas and I are the testers of the problem set you'll have to work on — thanks to satyaki3794, gamer12, harshil, tanmayc25 and PrinceOfPersia for preparing these tasks.

The contest will be rated. There will be some cool prizes for the top 5 competitors:
1. $100 Amazon gift card + HE t-shirt.
2. $75 Amazon gift card + HE t-shirt.
3. $50 Amazon gift card + HE t-shirt.
4. HE t-shirt.
5. HE t-shirt.

361A - Levko and Table

Matrix,in which all diagonal elements equal k and other elements equal 0, satisfied all conditions.

For example, if n = 4 and k = 7, our matrix will be

7 0 0 0

0 7 0 0

0 0 7 0

0 0 0 7

361B - Levko and Permutation

gcd(1, m) = 1, so if n = k, there is no suitable permutation.

It is well known that gcd(m, m - 1) = 1. Lets construct following permutation. It has exactly k good elements.

n - k  1  2  3  ...   n - k - 1  n - k + 1  n - k + 2  ...   n

360A - Levko and Array Recovery

Let's find such value b[i] that a[i] ≤ b[i] for all indeces i. Let's simulate all operations and diff[i] will be the difference between current value of i-th element and its initial value. If we have operation of first type, we change values of diff[i]. If we have operation of second type, we know that a[i] + diff[i] ≤ m[i], so a[i] ≤ m[i] - diff[i]. We will get array b when we union all this inequalities.

Let's prove that either b satisfied all conditions or there is no such array. It can be two cases, why b does not suit:

1. — it's impossible due to construction of array b.

2. — b[i] is a maximal possible value of a[i], so can't be bigger.

360B - Levko and Array

Let's solve this problem using binary search. We need to check whether we can achieve an array, when c(a) will be at most x. Lets make dp. dp[i] means minimal number of elements with indeces less than i, which we need to change, but we don't change i-th element. Let's iterate next element j, which we don't change. Then we know that we can change all elements between i and j. It is equivalent to such condition

|a_j - a_i| ≤ (j - i)·x

Difference between neighboring elements can be at most x. The maximal possible difference increases by x exactly j - i times between elements i and j, so this inequality is correct.

360C - Levko and Strings

Let's count amount of such substrings of t that are bigger than corresponding substring of s and begin at the position i.

1. If t[i] < s[i], this amount equals 0.

2. If t[i] > s[i], this amount equals n - i.

3. If t[i] = s[i], then let's find such nearest position j,  j > i , that t[j] ≠ s[j]. If t[j] > s[j], needed amount of substrings will be n - j. If t[j] < s[j], needed amount of substrings will be 0.

We can rephrase this: If t[i] > s[i], it will be (1 + pref)·(n - i) new substrings, where pref means how many last elements in s and t is equal.

Let's make dp. dp[i][sum] means that we viewed i positions, have sum needed substrings and s[i] ≠ t[i]. Lets iterate their common prefix pref.

If t[i] < s[i], dp[i][sum] +  = dp[i - pref - 1][sum]·(s[i] - 'a') — we can count this value using partial sums.

If t[i] > s[i], dp[i][sum] +  = dp[i - pref - 1][sum - (1 + pref)·(n - i)]·('z' - s[i]). Let's iterate pref.

Let's note that sum - pref·(n - i) ≥ 0, so pref ≤ sum / (n - i) and pref ≤ k / (n - i). This means that third cycle will make at most k / (n - i) iterations when we find value of dp[i][sum]. Let's count total number of iterations:

 =   <  k·(n + k·log  k).

360D - Levko and Sets

p is prime, so there exist primitive root g modulo p(We don't need to find it, but we know that it exists). We can write a_i = g^r_i. Note, that i-th set consists of all numbers , where c_j ≥ 0, or we can write it as .

By Fermat's little theorem a^p - 1 = 1 mod p we have that a^k mod p = a^{k mod (p - 1)} mod p. So can be equal to all values k·t modulo p - 1, where t = gcd(b₁, b₂, ... , b_m, p - 1). Note that t doesn't depend on r_i, so we can assign g = g^t. Then all elements of i-th set will be g^r_i·k, where k ≥ 0. Now we can replace b_i by q_i, where q_i = gcd(r_i, p - 1), as we do with b_i at the beginning. Then all elements of i-th set will be g^q_i·k, where k ≥ 0. This means that if we write all values g⁰, g¹, ..., g^p - 2 in a line, i-th set will contain every q_i-th element.

Now we need to find union of this sets.Let's do it using inclusion-exclusion principle. All our numbers are divisors of p - 1. Let's dp_i be the coefficient near i in inclusion-exclusion principle(i is a divisor of p - 1) and we can find this values, adding all q_i alternatively.

Also we need to find q_i. Let's find volume of the i-th set. It is equal to . From the other side it is equal to such minimal number d_i, that a_i^d_i = 1 mod p (d_i is a cycle). From a_i^p - 1 = 1 mod p we have that p - 1 is divisible by d_i. So we can find d_i as a divisor of p - 1. And .

360E - Levko and Game

Algorithm:

Firstly we will solve problem if first player can win.

Let's make all roads that we can change equal to r[i] and do two Dijkstra's algorithms from vertices s₁ and s₂. Let's d1[i] be the distance from s₁ to i, d2[i] be the distance from s₂ to i. Consider a road, that we can change, from a to b. If d1[a] < d2[a], we will set length of such road equal to l[i] and do two Dijkstra's algorithms again. We run such process until any road changes its length.

If d1[f] < d2[f] after all changes then first player wins.

If we replace condition d1[a] < d2[a] by d1[a] ≤ d2[a], we can check if Levko can end this game with a draw.

Proof:

Let's call "edges" only roads which Levko can change. When we do Dijkstra's algorithm we use all roads, not only edges.

1. Let's prove that if there exist such edges values that first player wins, there exist values of edges such that first player wins and all this values equal either l[i] or r[i]. Consider shortest pathes of both players.
   If only first player goes on edge from a to b, we can set its value l[i]. Proof: there must hold d1[a] < d2[a] because first player goes on it and wins. This condition holds after change of value of this edge. If second player goes on this edge, he loses because d1[f] ≤ d1[a] + d(a, b) + d(b, f) < d2[a] + d(a, b) + d(b, F) = d2[f]. If second player doesn't go on this edge, he loses because shortest path of first player became smaller(d(x, y) — shortest path from x to y).
   If only second player goes on edge from a to b, we can set its value r[i]. Proof: Shortest path of the first player doesn't change and shortest path of second player can only become larger.
   If no player go on edge, we can set its value r[i]. Proof: Shortest pathes of both players doesn't change.
   If both players go on edge from a to b, we can set its value l[i]. Proof: Shortest pathes of both players decrease by (initial value of this edge — l[i]).
   After every such operation first player wins again and all edges become either l[i] or r[i].

2. Consider result of our algorithm. Let's call edge "good" if its value is equal to l[i] and "bad" if its value equals r[i].
   (a) Let's prove that after performing all operations we will have d1[a] < d2[a] for all good edges (a, b). If we have d1[a1] < d2[a1] for edge (a1, b1) and after changing value of (a2, b2) this condition doesn't hold. We have d1[a1] >  = d2[a1], d1[a2] < d2[a2]. We change only one edge and shortest path from s2 to f become shorter so edge (a2, b2) lies on this path.
   d2[a1] = d2[a2] + d(a2, b2) + d(b2, a1) > d1[a2] + d(a2, b2) + d(b2, a1) ≥ d1[a1]. Contradiction. (b) Let's prove that after performing all operations we will have d1[a] ≥ d2[a] for all bad edges. We can continue our procces otherwise.
   (c) Let's prove that if condition d1[a] < d2[a] holds for some edge but we doesn't change it on this iteration, this continion holds after this iteration. Proof is same as in (a).
   (d) Let's prove that if any subset of good edges is equal to l[i] and d1[a] < d2[a], ift also holds when we make all good edges equal l[i]. Let's simulate all procces and use (c).

3. Lets prove that for all edges values(not necessary only l[i] or r[i]), d1[a] ≥ d2[a] for all bad edges (a, b).
   Assume that we have such edge. Consider shortest path of first player to its beginning. If there exist bad edges (a1, b1) on this path, there must holds inequality d1[a1] < d2[a1]. Consider first of this bad edges (a, b). Then shortest path of first player to a doesn't consist any bad edge. Consider problem,m which is equivalent to our problem but finish is in vertex a. good and bad edges will be same. Let's change all value of edges as we do in item 1. Note? that all bad edges will be equal to r[i]. So only subset of good edges can be equal to l[i] and d1[a1] < d2[a1]. By (d) we have that we can set all good edges l[i] and condition d1[a1] < d2[a1] will be satisfied. So we have contradiction thst this edge is bad.

4. This means that if first player goes on any bad edge, he loses. So we can set r[i] to all this edges. So we can set l[i] to some subset of good edges. By (d) we have that if we have d1[f] < d2[f] for some subset of good edges, this condition will be true if we set all good edges l[i].

5. Note that proof will be same if we want to check whether Levko can end a game with a draw.

Hello!

Codeforces Round #210 will take place on November 10 at 21.00 MSK and I am the author of the problems.

This is my first round on Codeforces and I hope everything will be well. I would like to thank Gerald Agapov(Gerald) and Vitalii Aksenov(Aksenov239) for helping me to prepare the round.

Good luck!

UPD.

Score distribution in first division: 500-1000-1500-1500-2000.

Score distribution in second division: 500-1000-1500-2000-2500.

UPD.

Congratulations to the winners!

First division:

1. Egor

2. PavelKunyavskiy

3. scott_wu

4. Dmitry_Egorov

5. mmaxio

6. enot110

7. sevenkplus

Second division:

1. _ZigZig_

2. budalnik

3. Ilya_Yakovlev

4. Neodym

UPD.

Editorial