1738A - Упоротая слава

Author: Milesian

1738B - Упоротые префиксные суммы

Author: liouzhou_101

1738C - Упоротые четные числа

Author: liouzhou_101

1738D - Упоротые перестановки

Author: Milesian

1738E - Упоротый баланс

Author: Milesian

1738F - Упоротая связность

Author: liouzhou_101

1738G - Упоротое противодействие увеличению

Author: antontrygubO_o

1738H - Упоротые палиндромы

Author: liouzhou_101

Hello, Codeforces Addicts!

On 30.09.2022 17:35 (Московское время) we will host Codeforces Global Round 22.

Codeforces Global Round 22 is the $$${\textbf{2}} \cdot {\textbf{2}} = 4$$$-th round of a 2022 series of Codeforces Global Rounds. The rounds are open and rated for everybody.

The prizes for this round:

• 30 best participants get a t-shirt.
• 20 t-shirts are randomly distributed among those with ranks between 31 and 500, inclusive.

The prizes for the 6-round series in 2022:

• In each round top-100 participants get points according to the table.
• The final result for each participant is equal to the sum of points he gets in the four rounds he placed the highest.
• The best 20 participants over all series get sweatshirts and place certificates.

Thanks to XTX, which in 2022 supported the global rounds initiative!

The problems were written and prepared by antontrygubO_o, Milesian and me.

We are extremely grateful to the following people who made this round possible:

• Aleks5d as well as KAN for great coordination.
• lucifer1004 for discussion and being the first tester as this round grows.
• 4qqqq, Akulyat, alexX512, arvindf232, BucketPotato, BurnedChicken, choutii, FairyWinx, Sugar_fan, lucifer1004, lyuankai, mejiamejia, nnv-nick, okwedook, p_b_p_b, Potassium, TomiokapEace, Um_nik, yyt16384, and zjq2863974342 for testing the round and their feedback.
• MikeMirzayanov for creating great platforms Codeforces and Polygon.

Round Information:

• Duration: 2 hours and 30 minutes
• Number of problems: $$${\textbf{2}} \cdot {\textbf{2}} \cdot {\textbf{2}} = 8$$$
• Score distribution: 500 — 1000 — 1500 — 2000 — 2500 — 2750 — 3000 — 4000

Kind Tips:

• Always get ready for interactive problems no matter whether they will exist or not, please see the guide of interactive problems if you are not familiar with it.

We are looking forward to your participation!

UPD. Editorial

Congratulations to the winners!

1. cnnfls_csy

2. ksun48

3. maroonrk

4. orzdevinwang

5. ko_osaga

6. tourist

7. jiangly

8. noimi

9. peti1234

10. Maksim1744

And for the winner of each problem:

A. tourist

B. tourist

C. wind_cross

D. tourist

E. tourist

F. 300iq

G. ksun48

H. rainboy

UPD: Solutions are added.

1480A - Yet Another String Game

1480B - The Great Hero

1479A - Searching Local Minimum

1479B1 - Painting the Array I

1479B2 - Painting the Array II

1479C - Continuous City

1479D - Odd Mineral Resource

1479E - School Clubs

Hello, Codeforces!

I'm very glad to invite you to my contest Codeforces Round 700 (Div. 1) and Codeforces Round 700 (Div. 2), which will be held on Feb/07/2021 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours 15 minutes to solve them. One of these problems is interactive, please see the guide of interactive problems if you are not familiar with it.

I would like to thank:

• antontrygubO_o for rejecting problems his amazing coordination and discussion.

• zjq2863974342 for all his rejected problems becoming the protagonist "Homer" in our problems in honor of his contribution.

• lavender730 for all her rejected problems sharing problem ideas and selecting the date of this round.

• choutii for discussion and being the first tester of this round (even before the testing phase).

• 300iq, Retired_cherry, Aditya_Mittal_31, dorijanlendvaj, gamegame, coderz189, Sugar_fan, HIS_GRACE, Invincible06, jiangshibiao, JOHNKRAM, littlefriend, lucifer1004, lyuankai, Milesian, mohammedehab2002, moreD, p_b_p_b and kalki411 for testing and their invaluable feedback.

• MikeMirzayanov for the great Codeforces and Polygon!

I have tried my best to write clear problem statements and make strong pretests. I hope you like the problems and enjoy the round.

The anti-traditional score distribution (yes, very early, that's why we call it anti-traditional; I love early score distributions!) is given as follows:

• Div. 1: $$$500 - (750 + 750) - 1500 - 2250 - 4000$$$

• Div. 2: $$$500 - 1000 - 1500 - (1500 + 1500) - 3000$$$

UPD: Editorial is out.

UPD1: We are sorry for the issue with the problem D2B and for D2C=D1A turning out to be well-known. Constraints for D2B were changed from $$$10^9$$$ to $$$10^6$$$ and all submissions which didn't get AC during the contest were rejudged.

We apologize once again and thank you for your participation.

UPD2 Congratulations to the winners:

Div 1:

1. Petr

2. A.K.E.E.

3. ko_osaga

4. Isonan

5. Benq

Also congratulations to hos.lyric (the only contestant who solved E during contest time!)

Div 2:

1. 5002ryx

2. AlanChen

3. whx1003

4. zkou

5. Ritos__

DFS is commonly used in those problems about trees and graphs. However, an unpopular guy — STACK OVERFLOW — often appears.

The issue about the size of the stack is discussed here. However, only a few languages have been discussed there. For example, in CodeForces platform, the stack size of C/C++ is 256MB, while, that of JAVA is poorly 64MB. MikeMirzayanov said he would change it but it seems he forgot it (or at least the stack overflow issue is not resolved for every language). Fortunately, at least there is a solution for JAVA with threads. Why threads? It seems there is the only way to set stack size at the code (against compile) level in JAVA. Moreover, thanks to CodeForces that threads (in JAVA) have not been banned so far.

The Kotlin Heroes Episode will be held in a few days. While I am using Kotlin, the STACK OVERFLOW issue comes out. It seems there is no blog that talks about this issue at least at this moment. I have struggled for it for days and fortunately resolve it finally. I'd like to share the solution with you, and hope it will help for you.

I first noticed that Kotlin could use JAVA libraries in Petr's code in Kotlin Heroes Episode 1. I combine Kotlin code with the previous solution to stack size for JAVA, and then find that it really works. Since there is still a little difference between Kotlin and JAVA, it is necessary to post the Kotlin code below.

import java.util.*
import java.io.*

fun main()
{
    Thread(null, Main(), "whatever", 1 shl 28).start()
}

class Main : Runnable
{
    override fun run()
    {
        // Treat this function as main function and do whatever you want
        // Say goodbye to STACK OVERFLOW
    }
}

I'd like to note that the constant 1 shl 28 indicates the size of stack being 256MB.

I am not very familiar to Kotlin. If there is a better way to do this, please share with us.

311A — The Closest Pair

P.S. I feel really guilty that I've made an awful mistake on the checker.

We read the pseudo code carefully. If we ignore "break", tot will be up to .

Consider whether we can make such inequality d ≤ p[j].x - p[i].x is always false. The obvious way is to make all points' x coordinates the same. And we can just choose n distinct numbers to be all points' y coordinate.

Thus the problem is solved.

311D — Interval Cubing

Consider a number x. If we apply an assignment x = x³, x becomes x³. If we apply such assignment once more, we will get (x³)³ = x³². If we apply such assignment k times, we will get x^3k.

Thus, we can get such a sequence a₀ = x, a₁ = x³, a₂ = x³², ..., a_k = x^3k, ....

Consider a prime p. From Fermat's Little Theorem, we can get x^p - 1 = 1(mod p). Further more, we can get x^y = x^{ymod(p - 1)}(mod p), here a mod b means the remainder of a divided by b.

Fortunately, 3⁴⁸ = 1(mod (95542721 - 1)), thus, x^3k = x^3kmod48(mod p). In other words, a_k = a_k + 48, which means the cycle of the sequence is T = 48.

Let's come back to the topic. Each time we run a 1-type query, for every i in the range [l, r], we apply such an assignment a_i = a_i³. At any moment some i has been applied 48 times such assignments, we can consider this i hasn't been applied any assignments before.

We can use segment tree to solve this problem. Every node of the segment tree maintains some information: the times that we applied assignments in the node's whole range(it's a lazy tag), current sum of the node's corresponding range and the sum of the node's range after we applied assignments k(1 ≤ k < 48) times.

In such a way, we can solve the problem in O(n·T + q·T·logn) time.

If you do not realize how to maintain the segment tree clearly, you can view the code 3782263.