"It's been a long time since I came here, and I've really been through a lot." Koxia muses as she chatted idly with Mahiru.

Now that the Winter Festival is approaching. Among the flash of fireworks, in the chimes of the New Year, what is waiting for them to encounter?

Armed with girlish courage, they stepped onwards.

Hello Codeforces!

We (Nanako, m_99, huangxiaohua, SteamTurbine, triple__a, Nezzar) are very pleasured to invite you to take part in Good Bye 2022: 2023 is NEAR, which will take place in Dec/30/2022 17:35 (Moscow time)!

This round consists of **8 tasks** waiting for you to solve in **150 minutes**, and will be rated for everyone!

On behalf of the author team, please allow me to express our sincere thanks to:

- errorgorn, for useful guidance and brilliant advice during the coordination!
- KAN, for rechecking and translating the round!
- ak2006, tallbee23, Tlatoani, gisp_zjz, Roundgod, Kaibad, xzm2023, Frozencode, woruo27, ayhan23, compute, muoshuo, conqueror_of_tourist, googol_S0, zengminghao, valeriu, manish.17, cuzperf, tibinyte, JuanPabloAmezcua, for providing valuable and constructive feedback during testing!
- 1tTx__, for the exquisite illustration!
- MikeMirzayanov, for great platforms Codeforces and Polygon!
- you and everyone, for participating and making this round have extraordinary significance!

This round is supported by NEAR. The participants in the top 2047 places will receive prizes as follows:

- Ⓝ 1024 for the first place
- Ⓝ 512 for the 2-3 places
- Ⓝ 256 for the 4-7 places
- ...
- Ⓝ 1 for the 1024-2047 places

Score distribution will be announced soon.

Besides the regular editorial, materials to be public after the round will also include the Chinese statement and the Chinese editorial.

We hope you enjoy our problems and say Goodbye to your 2022 happily!

**UPD1**: Score distribution is **500 — 750 — 1250 — 1500 — 2000 — 2500 — 3250 — 4000**.

**UPD2**: Congratulations to the winners!

Thanks all for joining!

**UPD3**: The editorial is available.

**UPD4**: The Chinese statement and the Chinese editorial have been added into the contest attachments.

EXcited to participate the ending of 2022 contest :") Good luck everyone..hoping for positive deltas :)

Thanks. I think this round will be great and I hope everyone will have a great result. Let's hope that only good memories remain from the year 2022

@tester(done) https://codeforces.com/blog/entry/110638 you may start the contribution farm

As a tester, I spammed my message here so as to not clutter

As a tester, I give you respect

As a tester, thanks for reminding!

As a tester, the problems are very interesting!

As a tester, I wish you a happy new year! :D

As a tester, I tested the round.

From my perspective, the problems are really interesting and I strongly recommend everyone to take a chance to participate!

As a non-tester, hope i get a chance to be tester someday

As a tester, I can say it will be a very good round for you~

Goodbye 2022 and happy new year~

As a tester, mark. Happy new year :)

I guess everyone who upvoted the blog regrets now.

Receiving 1 near nowadays is the same as getting 0

As a writer, I think the little cartoon girls in the picture are cute.

As a participant, I think the little cartoon girl in your profile picture is cute.

nice profile picture

I would participate instead of testing if I knew there was a prize LOL , anyways the quality of the contest is really high and good luck to all of the participants :D

The girls are so cute (,,>﹏<,,) I wish I could participate ૮₍ ˃ ⤙ ˂ ₎ა

Wrong account

I graduated from a famous school in mainland Mehedinti, at least I am not stupid. My account is not high because I don’t have much time to train. If I spend a lot of time training, I should be able to train to Master, but I really don’t have that time.

I think you misunderstood the joke

No, I did not.

MarinushMarinush is epic

As a returning geezer participant, I ask you young uns to take it easy on us.

Goodbye,2022!

As a tester, I can say it will be a very good round for you~

Beautiful BG, another step to the Animeforces :3

Me and my bois calculating the monetary value of 1 NEAR.

1 NEAR Protocol~=1.3 USD

How to receive these gifts?

Waiting for an answer,too

Had you got it's answer? If yes please help me to get that too

Happy new year!

Hope I can become candidate master!

I want to know the difficulty of this game, div1 or div2 or else？

Div.1 + Div.2

Thanks for your response（

As a tester, the problems are very good! I hope you will have fun in this round!

Every tester says the same thing. It means something is there. I'm waiting for tomorrow. It's time to turn the table

I would like to see Santa Claus or a Christmas tree on the announcement

OK I surrender no more downvote plz

all high rating in 2023!!!

I wonder if instead of "Accepted" we will see "Happy New Year"

Only that instead of

Wrong Answerwas notHappy New Year:)we will see *Bye Bye 2022".

Am I only one who feels that the girl on right is staring at us.

You are too tall. She is probably staring at everyone except you.

This year was awesome, wish everyone all the best!!! :)excited for my 21st round.. will try to be more consistent in codeforces rounds in 2023

lol

Everyone Best of Luck Good Bye 2022 Happy New Year Everyone

This contest will be in my Heart. Good bye

2022. Welcome2023. Wishing the new year will be good one for everyone.I hope I can get a good result this time and get off to a good start for the New Year!

Will this be div1 or div2?

It's a combined round like Div.1 + Div.2.

I wish you all the best, more ratings to everyone! :)

Let's go !

All the best everyone for the last contest of 2022 and Advance Happy New Year.

mister is too ORZ

Thank you for your work!

Delete this immediately.

Marinush[Deleted] :(Really excited for participating in last contest of this year . Started journey on CF this year and learnt alot :)

https://codeforces.com/blog/entry/110404?#comment-985599

solved too much easy problems.

I'm Nanako_fan!

:blobheart:

One NEAR Ⓝ is about $1.3. Hope I can get NEAR in this contest.

This is my last chance to become Master before New Year's Eve. Wish myself the best of luck!

As a participant, I wish all participants have a great time and get positive deltas! Good bye 2022!

Koxia and Mahiru >>>>

;_;

the picture is nice!:)

EXcited to participate the ending of 2022 contest :") Good luck everyone..hoping for positive deltas :)

Chinese Editorial! Good job!

Thanks >_<

As a tester, thanks for reminding!

Do anyone know which country is 'Ⓝ' belong to?And what's the value?Thanks.

Virtual currency offered by sponsor NEAR

https://codeforces.com/blog/entry/110638?#comment-986079

So is it possible to exchange NEAR for cash or is it only a voucher?

I guess exchanging into cash means many procedures but I'm not really sure ;_; maybe you could ask for participants of Goodbye 2021.

it is possible using crypto exchanges like Binance and Huobi

As a participant, i wish you a happy new year! :)

As a tester, I may ask whether the test is reted or notshinzanmonoOops, you are a participant instead of a tester. As for rating stuff plz read the announcement carefully.

hope to become blue from orange!

Hoping to enjoy a great contest at the end of 2022 :)

I will be ranked #1 in this contest. I am feeling it

Feeling it too please post an update after the contest!

Sure, Good Luck!!

Went as planned. Just 8198 ranks away from what I was feeling xD

Counts as #1 to me, amazing job!

girlish power ??? what the **** is that ?

Authors, please, read this: https://codeforces.com/blog/entry/56119

Oops, thanks for the reminder. Although this round is themed, I'm an opponent of long statements so they will be literally very short and with only necessary pictures.

As for the announcement, I have checked with the coordinator and the admin before posting, so I guess it's in a reasonable range. If you don't like it, I personally feel sorry for you, but don't blame other authors cuz it's my personal decision to add it. ;_;

No, that's kinda cute, that was just a reminder that someones internet connection might be not that fast :)

Is it rated?

Read the announcement carefully and it's a yes.

sorry if the answer has appeared before, but why this contest currently unrated?

It looks like a temporary rollback for excluding cheaters or something.

okay, thanks for the information

i am so excited

OMG! a "Good Bye" contest.

Why so many pfps of animated girls here?

This year I will focus more on learning and skills than on rating

I thought rating reflects these. Thanks for enlighten us all that rating is calculated from out of blue

Ah I meant just blindly giving contests instead of upsolving.It is true that even rating will decrease in that case

i hope it will be a great contest

Last chance to see myself as CANDIDATE MASTER Adarsh8409 on NEW YEAR EVE.

can we move the contest to tmr? i would like to participate from 31/12 straight to 01/01

As a participant, i wish you a happy new year! and hope all everybody high rating in 2023 :>

Good luck to everyone

have fun!

As a Desi_Boy from village. Today I'll do my best. I hope one day I'll become good problem solver

Excited for this!

Very excited to participate!

The comment is not hidden because of too positive feedback, click here to view it

Happy New Year to all coder in the codeforces.

Hope I’ll become a pupil this round

You can, even right now

Nice!

haha, good joke

Hope for good results!

I will give back my 1Ⓝ for 1 more picture

How many problems I should solve to reach 1900 rating?

Just try your best

Good luck everyone..hoping for positive deltas :)

Leaving behind my Christman celebrations. Leaving behind my institute's Cultural fest. Leaving behind a dinner party.

Just won't miss 2022's last contest ^o^

To all the participants, good luck in the final contest of 2022, and happy new year! may 2023 be a year of great achievements for all of us! :)

Am very sad Because due to travelling i am not able to attend it *_*

Hope to perform better

As a participant, I wish you a very Happy New Year(:

As a member of ABC squad, I was surprised m_99 is on the writer's list. I surely succeed in the game!

Skibididop dop dop oh yes yes yes Shibididip dip Shkibidop ShkibidiW W W.cout<<(("Good luck")?"DOP":"DIP");

Hoping for positive rating deltas!!! may everyone a happy new year

I don't want to miss out the last contest of 2022 more than I don't want to lose rating

Last chance for me to be an expert ( + 154 ) before 2023 [ fingers crossed ].

oops. forget about expert, became pupil again :(

I can feel you bruh

As a participant i am wondering if there are XOR problems

is it rated?@2021_yes

Good luck to you in the last contest of the year 2022 and happy new year!

Good luck everyone! Happy New Year everyone:)

Damn..

Just realized I wasn't registered and to wait 10 extra minutes for registration pushed me to don't join and wait for virtual, sad.

I can't solve the 1st problem (⓿_⓿)

Every solution gives me WA on pretest 2 XDXD

first time, huh

I got 5 WA (crying in corner)

Me too , I got 5 wrongs but still can't solve it!!(-_-)

Think about it... which number should you replace with B_j ? The smallest number, of course. Now just implement this with a

`set<>`

or`priority_queue`

. I missed this easy solution and went for the guessing ride.You don't even need to use a set or priority queue actually. Since the constraints are very loose $$$(n, m \le 100)$$$, one can simply sort the array $$$a$$$ after every replacement of $$$a$$$'s smallest number, i.e.,

`a[0]`

with`b[j]`

I did that but wrong answer on pretest 2 , maybe I missed something so I sm gonna write the code again ✍(◔◡◔)

I see that you have sorted the array $$$b$$$ too. You can't really do that because the order of elements in $$$b$$$ is important. The operations are happening in sequential order.

My bad!◑﹏◐

Thanks for your help ❤

why can not we sort array b. Is it mentioned in the question

In the $$$j$$$-th operation, we are changing a number on the whiteboard to $$$b_j$$$. This implies that the ordering of the array $$$b$$$ is significant and plays a role in the problem. Hence, you cannot change the order.

only set might give you wrong answer. you should use

multisetin that caseKinda ruined my birthday ＞︿＜

Happy birthday, Nayra!❤❤

Thanks Sweetie, wishing all the best to u :)❤️

Happy birthday, Nayra!!(❁´◡`❁)

Aww Thank u ,may u reach all ur beloved goals ❤️

Is problem a harder than usual or am just that bad?

it's just a very bad question(

Nope , You are right !

It is a very hard round ◑﹏◐

Why such a bad round in New Year ?

Why such a bad comment in New Year? To be more precise, what's bad with this contest? I disagree that the contest is bad.

Problem C was ugly. Did you look at scoreboard? In a Div.1+2 round, only 3k managed to solve C, while there were 12k participants. Does this problem seem appropriate for position "C"?

YES.

Of course. For higher rated participants the order/difficulty of easier problems doesn't matter, right?. They're gonna solve it anyways, why would they even care ?

Except that, solution for

Cwas uploaded on youtube during contest. For most of Div.2 people, this will cause something called,Rating Inflation.The scoreboard and predictor says the rating of C would be about *1600/*1700. This difficulty is really not strange and there are a lot of problem C with this rating.

About solution leakage, unfortunately I didn't heard about that, but even if that is true, what does that have to do with the competition being bad? Just that behavior is bad, right?

For

1700rated problem, that amount of ACs is low.Behavior is bad. But the contest Will be Bad too. Its more like, who googles first, that wins. No?

Well, there were some contests which suffered such behavior. But were these contests regarded as

essentiallybad contest?No they weren't. But this

Cis not 1700 rated (harder than that). Which means this contest is not suited for most Div.2 people.But it depends on how you solved it. By guessing? [Hell yeah, free 1000 points. Such a good problem!]

Now it got *1700 rating tag.

I thought that last contest of 2022 will be easy but It says me goodbye from pupil rating

Man, problems are kinda difficult. Please include problems of Graphs, DP and Trees in A,B,C and D's'. I am only able to solve these but these are usually adhoc and there are no concepts of DSA used in these problems. It doesnt gives the satisifaction to solve these adhoc problems.

Yeah but you can go for weekly and biweekly on LC

Yeah, I give them but I want to enjoy cf rounds too. Dont get me wrong, they might be perfect for other users but not for me as I am not that good.

I think Extended Euclid theorem is kinda standard basic stuff. They can be ok for Div2 ABC

Agreed

Read this blog. My thoughts are roughly the same.

Also funny that you mention D, because D is actually a graph problem after you get some observations.

Actually, I didnt read D for this contest as I was stuck in C. I was not particularly pointing to this contest but all cf rounds in general.

Adhoc = Math ?

As i've expected, Good Bye Expert: Newbie is NEAR! Kinda thrown this one

Problem A could've been framed better imo

how did u solved it

Solutionyou just need to replace the smallest element of array A one after another with elements of array B and at the end the total sum is the ans

did the same thing but getting wrong answer on pretest 2

PS: i did not sort the second array B

did you first sort A? like without any operations first sort A and then m times swap and sort?

Or you can use priority queue too

i first sort A then just swapped m times

if m>=n then basically take all the greater elements of B else we will have to take all the elements of B + remaining largest n-m elements of A

I dis this...

You'll actually have to swap the smallest element everytime. Let's say A = 1, 3, 7, 8 and B = 3,5,2 Then after 1st swap A should like: 3, 3,7,8 2nd swap 3,5,7,8 3rd swap 2,5,7,8 So it is optimal to pick the lowest element from A everytime and swap it

oh i forgot that after swapping from B that element itself may be smaller than those in A so I must keep on sorting

Thanks got it

well this isn't optimal way cause let's suppose there are my first array is 3 4 and second array is 1 8 6 now there can be three operation's done so if I only take maximum values of second array and swap them with first array values then after three operations my first array will be 4 8 and second array will be 1 3 6 however if we pass on 1 first then we can make our first array equal to 8 and 6.

The thing is that, you need to swap values from array B one after another, 1st element then 2nd and so on That is why I mentioned it could've been framed better

just used a priority_queue

Today's contest was a perfect embodiment of my 2022.

Disappointing and making me doubt my very existence.

I hope 2023 is better :)

OK finally I got it,from Master to Expert.

I found problem D amazingly beautiful. what a problem and process of solving it was really good

How to solve problem E?

Who else made at least one WA on A because they sorted the array b (or equivalent) before performing the operations ?

us

Wow.. That was the reason I couldn't get AC. I thought I could choose the order of operations.

same...ACed at 2:16

why sorting leads to WA ?

If you read the problem statements carefully, you will see that you cannot take any element from array

barbitrarily; you should always maintain the sequence. That's why you shouldn't sort the array. Also, you always need to replace the smallest element of array '**a**' with '**b[j]**'.Was problem C related to check if the solution to the congruence equations created by each pair exists or not?

just to give a hint. if you have 2 odd numbers and 2 even numbers the answer is NO ! now think about 3 an so on

i tried this method like if we have both (odd,odd) & (even,even) pair then ans is NO otherwise YES.

this is what i did but its failing testcase-4.

187368333

that is what i meant by so on ! now what if you have 2 numbers that have reminder of 1 with divided by 3 and 2 numbers that have reminder of 2 when divided by 3 and 2 numbers that have reminder 0 ?

can u elaborate on C?

This was my approach https://codeforces.com/contest/1770/submission/187361827

can you share your code please

check my submissions

Is there a theory or mathematical prove for this solution ??

i tried it using brute force which i think should have worked

by adding i=1 to i=100 and then checking th gcd

I too have the same doubt, thinking the same

A disaster -_-

Are these accounts bots? They sent correct solutions all at the same time. There are more of them with the same timing.

I guess somebody wants to steal some NEAR tokens...

Definitely not the ending I hoped for

I... don't even have the will to make the obvious "anime girl on internet == trap" joke. Happy new year, everyone...!

Misread A for 20 minutes and skipped the x is positive part(even it is highlighted) in C. Feels bad.

I think the record of difficulty of A in div 2 is broken today

Problem E was a great problem. (Hint for people who haven’t solved E: the tree edge e_i divides the tree into two disjoint sets)

I've noticed it but I don't know how to calculate number of successful moves along each edges

Problem A is such a nightmare.

for me also bro , 6 wrong submissions, can anyone explain problem A

The solution is simple: iterate over array b and switch element in array b with the smallest element in array a. do this for every element in array b.

Before this contest I thought after this contest I might become candidate master and have a very happy New Year. After this giving contest I am depressed and sad on the new year. Hopefully the next year will be better.

Master next year, sir!

There were gaps between BC and EF but the problems are very interesting! Thanks for the amazing round in the last of 2022! One regret thing is I can't proof my solution for C during the contest.

Thank you for your endorsement! The proof of C is given in the editorial.

How to solve E? It's sufficient to calculate numbers of successful moves of each directions on each edges, but how can we calculate it

For each edge u--v, we cut this edge to get 2 subtrees, and let b(u)=number of butterflies start on the subtree which contains u, similarly b(v)

Then if m1= number of successful moves from u to v, m2= number of successful moves from v to u, then the contribution of edge u--v is m1(b(u)-1)(b(v)+1)+m2(b(v)-1)(b(u)+1)+(2^(n-1)-m1-m2)b(u)b(v)

So how to calculate m1 and m2?

Consider the dp(u, i), the probability of after i iterations, the vertex u is covered with a butterfly. Clearly, dp(u, i)= dp(u, i-1) if the other edge doesn’t include u. And the probability of u and v, where e_i = (u, v) should be calculated fairly simply, so we can calculate dp(u, n — 1) for all u in O(N) as all values except two changes between iteration. So using the probability array, we can calculate the probability when there is a movement between the two disjoint trees divided by the ith edge, and thus the contribution of the ith edge to the answer.

But what if probabilities of u and v are not independent

Update: Now I know probabilities of u and v are independent. Because each edge would be moved only once, and before being moved, moves of u-subtree and v-subtree don't intervene each other.

goodbyes are harsh

Ending the year with -100 ig :)

Oh sh here we go again

same

Oh man, you lost CM after so very work, much harsh!

thank you for understanding)) I'm actually not that upset, since it's only a title and nothing more. Maybe it's still a little bit too early for me, yes, but at some point i'll get there. So i try to be positive and think of it as a useful experience!

same x)

can someone pls explain logic for problem c?

Thank you.

lets look at prime number p and every pair of 2 elements in the array (a[i] and a[j]). if a[i]%p!=a[j]%p, we can choose every x and independent on x%p gcd(a[i]+x, a[j]+x)%p!=0. if a[i]%p==a[j]%p we can't choose x%p==p-a[i]%p. considering n<=100, we should look at small primes* (and for every prime we have to decide — is there a "good" x%p — if not, there is no solution) *because for big primes there are not so many pairs

Oh no!

How to do D?

My idea is to convert it into a forest, and then find the rings. If it is the self ring, answer times n, otherwise the answer is multiplied by 2. But I got the WA on test 2.

my submission

And how to do C...... I am not good at gcd.

Literally me. Did the same thing in D, got 998244353 WAs on pretest 2

Hold up, doesn't that mean you got 0 WAs?

I had the same idea, but in the end i realized that there might not be cycles:

5 1 1 1 1 1 1 2 3 4 5

C is (good imo) an observation problem.

your idea was correct for D. however there are some twists. think about these 1 : 2 self rings in a component (or any two rings in a component tbh) 2 : a tree in the forest

both of these can be handled with a simple if ! if the number of edges in a component is not equal to the number of nodes then simply print 0.

Your solution is correct when the answer is not $$$0$$$. For every connected component, the number of vertices and the number of edges must be the same, otherwise there will be same numbers appearing in $$$d$$$.

I suggest to make the round unrated because the problems are not New Year's)

I had a sol for E for a version where the butterflies could go to another node even if there was already another butterfly. Spent 1 hour coding that and noticed it was wrong after finishing.

Certainly one of the ways to end the year.

Please explain C hope u did

Oh no. Haven't noticed this before reading your comment.

Good bye, ratings. :(

Deadliest Contest Goodbye 2022 :\

Why is this code showing error for 2nd pretest in 1st q? Please help me

You shouldn't sort the B array.

You cannot sort array b. Have to perform operations in order. I took forever to fix my mistake on this too

Oh nooo ;( I wasted much time on this... and didnt do the other questions....

in the question it is given you have to perform operation but doesn't that in the order

The last element of $$$b$$$ must be used.

All I can say after the contest, is the name of the contest itself ("Goodbye 2022" XD). Hope 2023 turns out to be better overall for everyone!

I did a weird solution in C that passed the pretests, could someone explain why is it correct or incorrect ? 187365787

It seems that everyone solved C like this.

The solution is posted on tg, during the contest.

Can you elaborate your thought process for writing this solution? It would make understanding your code easier.

For any number k, if the array has two or more occurrences of all of the values from 0 to k-1 modulo k, then that means for any x we choose we can always have two number in the array giving gcd as 1. Let's say x%k=p then we already have two numbers in the array which give the value modulo k as (k-p) so k will always be the gcd in such situation.

And also k has to be smaller than 50 if it exists.

This is one situation, it can be concluded that if such k exists then there is always an x, but I cannot prove that if x exists then there is always such k.

Your solution is always correct. I have an intuitive understanding of why, but I can't give a formal proof.

It's enough to check all primes $$$p \le 50$$$ since if the array is bad for some composite number, it is also bad for all of its prime factors. And now if it was good for every prime, there exists a set of congruencies you need to solve to get $$$x$$$:

$$$x \equiv a\ (mod\ 2)$$$

$$$x \equiv b\ (mod\ 3)$$$

$$$x \equiv c\ (mod\ 5)$$$

$$$\cdots$$$

$$$x \equiv o\ (mod\ 47)$$$

Becase all of the modulos are prime, they are also all coprime with each other, which means that there exists some $$$x$$$ which satisfies all of the congruences based on the chinese remainder theorem.

UPD: I realised that the set of congruences up to $$$p \le 50$$$ aren't enough to gurantee that the specific $$$x$$$ works. We would need to add a lot more congruences for larger primes. But we know that there always must exist a valid congruence for each larger prime, which means we can still apply the Chinese remainder theorem to calculate $$$x$$$.

Hey, was the problem C really more difficult than standard Div2 C or was I panicking for nothing??

Nope, it was in fact harder. It was a bit more math intensive.

Ending with still Pupil :(

Fuck Bye 2022.

The statement for problem A is quite unclear

It doesn't clarify the fact that you have to use the numbers in array b in the same order they're given.

It just says that you have to perform all m operations... Spent 90% of the contest's time trying to figure it out and lost a lot of points :(

i also thought the same and demotivate since it is A problem and not able to solve Question language was very unclear

The j-th operation is to choose one of the whiteboards and change the integer written on it to bj.I think you misread the problem. Happens with me too many times.

How to solve Problem C. Could Someone Help

For any $$$i$$$ and $$$j$$$, if $$$a_i \equiv a_j \ \mathrm{(mod\ m)}$$$ for some $$$m > 1$$$, then $$$x$$$ must meet the condition: $$$x + a_i \not\equiv 0 \ \mathrm{(mod\ m)}$$$. Otherwise, the $$$\mathrm{gcd}(a_i + x, a_j + x)$$$ will be a multiplication of $$$m$$$.

Generally, for any prime $$$p$$$, $$$x \not\equiv a_i \ \mathrm{(mod\ p)}$$$ for any $$$i$$$ and $$$j$$$ such that $$$a_i \equiv a_j \ \mathrm{(mod\ p)}$$$. Also, if there are two or more $$$a_i$$$ such that $$$a_i \equiv r \ \mathrm{(mod\ p)}$$$ for every $$$0 \le r < p$$$, we can't find $$$x$$$ since there will be a pair of $$$a_i$$$ and $$$a_j$$$ which are multiplication of $$$p$$$ for any $$$x$$$. And otherwise, $$$x$$$ always exists. (can be shown by Chinese reminder theorem)

So the solution is to check whether $$$r$$$ exists such that there are at most one $$$a_i$$$ which meet $$$a_i \equiv r \ \mathrm{(mod\ p)}$$$ for any $$$p$$$. Here, we don't have to check for $$$p > n$$$ since $$$r$$$ will always exists such that no $$$a_i \equiv r \ \mathrm{(mod\ p)}$$$ due to the Pigeonhole principle.

Iterate for every prime $$$p < 100$$$, and iterate over $$$i$$$ in each $$$p$$$. Count $$$a_i\ \mathrm{mod}\ p$$$ in $$$p$$$-length array and check if 0 or 1 exists. If not, print NO.

Actually, you only need to iterate over every prime $$$p \le 50$$$ since due to the pigeon hole principle for every $$$p > 50$$$ there must exist at least one $$$r$$$ such that $$$a_i \equiv r\ (mod\ p)$$$ appears at most once.

I think C>E>D.

C was basically noticing that we only have to check primes under 100 as for primes above 100, by Pigeonhole principle, there would be always a free residue which x can take. I guess the hard part was thinking this as a CRT/prime problem

Omg shit shit... How it clicked man?

Solving a degenerate amount of number theory problems for MO

Can u tell it in more detail? I haven't gotten the idea, why can we always find x > 100 to fit that ?

Because n is bounded to 100, the number of residue classes that are forbidden is strictly less than the total number of residence classes

As n <= 100, at max we can make 50 pairs right?, so isn't 51 enough. Just couldn't wrap my head around this.

Edit: It got Accepted, now someone should confirm whether my assumption is True or Tests are weak

Oh yeah for each prime, if there is a residue class with less than 2 elements, the prime is good

goodbye to 2022 and goodbye to lots of my ratings :)

This round was tough.

I was literally only seconds late from finishing C. Fuck this shit!!!

At the last minute!

can you explain your solution please??

I was waiting for it to pass system tests. Now, as it passed, I can explain it

`You can say NO only if you proved that all positive numbers till ∞ will cause a problem for at least two numbers.`

## Now consider the divisor 3

suppose you have two numbers in the array that if you added 1 to them, they will be divisible by 3,

suppose the same thing for adding 2 and adding 3.

Now, if you added 1, the first two numbers will not work. If you added 2, the second two numbers will not work. If you added 3, the third two numbers will not work. And lastly if you added 4, it is the same thing as you adding 1 (by taking mod 3).

And the same will happen for 5 and 6 and so all other positiver numbers, so there is no solution.

This explanation is for 3 only, you need to check this also for all other numbers $$$ ≤ n/2 $$$

Greedy came to mind when I looked at problem A, but it was quite a simple one. It seems like a trap to me.

contest is hard

Did only I struggle..

Edit: (Mistake) Sorry I am soo exhausted rn.. It was in Problem A

Goodbye 2022! Goodbye my rating!

I think that problems are interesting but a little too difficult QAQ

time to downvote

2022 hasn't been a good year for me and this contest is just the confirmation , thanks

I fucking hate this round

Clarificaton: because it was too good,

This Is Probably The Toughest Contest I've Ever Appeared On CF :(

Goodbye 2022. Goodbye mom of authors :))

Problem G

Problem G but harder

What does that mean, are they same like problem G in today's contest?

Not exactly the same, G is reduced to this problem, but the reduction is very simple.

can you explain how to reduce it? I watched your screencast, where you coded the function

`solve`

by hand instead of copying from the old submission. Is it because the reduction is not exactly the same as the original one?I'm just stupid. The original code was written before I wrote fft library for myself, and I was afraid that it might have been too slow for this problem (the new code is also very slow smh), so I decided to write it in the new style.

As in the editorial, we'll solve for ) and ( independently. Focus on (. Let's say that the minimum balance is $$$-m$$$, then we have to remove $$$m$$$ brackets before the first occurrence of the minimum balance, and we have to make sure that after removals all the balances are non-negative. It's the same as saying that we have to remove at least $$$k$$$ brackets before the first occurrence of balance $$$-k$$$. Let's build a Young diagram corresponding to these limitations. Each move will mean the next bracket, if we move up, we remove it, if we move right, we don't. So we are interested in the number of paths from the lower-left corner to the upper-right corner, but some cells are forbidden, as we know that we have to move up at least $$$k$$$ times before the first occurrence of balance $$$-k$$$. It is easy to see that these limitations describe a Young diagram.

Example:

$$$ ( \color{green}{)} \color{red}{)} \color{red}{)} ( ( \color{green}{)} ( \color{green}{)} \color{green}{)} \color{red}{)} ( \color{green}{)} \color{red}{)} $$$

Just curious, how do you keep track of similar problems like these? Or do you just remember bits of problem statement and use that to Google them.

This one is just a very natural-sounding problem (count the number of paths in Young tableau) and I was very proud when I was able to come up with the solution in training, so I remembered the circumstances when I solved it (it was a training with my ICPC team, somewhere in 2019, the contest was in CF Gym), so I was able to search the trainings we participated in that period of time. The actual process from my screencast.

Good problems stay in your memory, what can I say.

Brain Limit Exceeded.

Thanks for the round! Regardless of my performance, I think the problems are nice, especially D and E. This is my short comment for the problems.

A.Normal problem. I used priority queue in D2A for the first time(although naive works) XDB.Constructive problem. It requires some observation(and maybe some intuition?), normal problem.C.It requires some intuition again :P, but good problem. I got WA on last pretest because I mistook the limit of n as 50. XDD.Nice problem. Graph modeling and following observations are good. I heard the implementation can be hard according to approach, but easy implementation exists.E.Nice problem. The idea is hard, but clear. How to create such problem?F.I read it, but currently has no idea.G,H. Not read.My performance in Good Bye 20xx contest has many ups and downs, this time my performance went up, maybe I can reach GM for the first time?

can u explain C pls?

This was my approach https://codeforces.com/contest/1770/submission/187361827

We have to see all prime numbers less than or equal to n/2. For some prime number p, get the remainder of each element divided by p, and if every number between 0 and p-1 appears twice or more, the answer is NO. If no such prime number exists, the answer is YES. Consider this case,

#1 6 5 7 9 11 13 12

whatever the value of x is, there should be always 2 multiple of 3, so the answer is NO. Your code print YES in this case.