"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 30.12.2022 17:35 (Московское время)!
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, tolbi, Tlatoani, gisp_zjz, Roundgod, Kaibad, xzm2024, 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.net/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.
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.
Marinush
Marinush 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
As a tester, the problems are very good! I hope you will have fun in this round!
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 Answer was not Happy New Year :)
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!!! :)
lol
Everyone Best of Luck Good Bye 2022 Happy New Year Everyone
This contest will be in my Heart. Good bye 2022. Welcome 2023. 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.
qwexd is too ORZ
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.net/blog/entry/110404?#comment-985599
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 >_<
Do anyone know which country is 'Ⓝ' belong to?And what's the value?Thanks.
Virtual currency offered by sponsor NEAR
https://codeforces.net/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 not shinzanmono
Oops, you are a participant instead of a tester. As for rating stuff plz read the announcement carefully.
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!
Authors, please, read this: https://codeforces.net/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.
This year I will focus more on learning and skills than on rating
Last chance to see myself as CANDIDATE MASTER Adarsh8409 on NEW YEAR EVE.
As a participant, i wish you a happy new year! and hope all everybody high rating in 2023 :>
Good luck to everyone
Excited for this!
Hope I’ll become a pupil this round
You can, even right now
Hope for good results!
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! :)
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");
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!
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
Think about it... which number should you replace with B_j ? The smallest number, of course. Now just implement this with a
set<>orpriority_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]withb[j]Kinda ruined my birthday ＞︿＜
Happy birthday, Nayra!❤❤
Is problem a harder than usual or am just that bad?
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 C was 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 1700 rated 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 essentially bad contest?
No they weren't. But this C is 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
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.
Предлагаю сделать раунд нерейтинговым из-за того, что задачи не новогодние
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
you 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
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
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 you share your code please
check my submissions
Is there a theory or mathematical prove for this solution ??
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...
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.
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. :(
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
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.
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
Actually, I did it in a different way, but it took me infinity :(
goodbye to 2022 and goodbye to lots of my ratings :)
This round was tough.
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 $$$
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
solveby 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) XD
B. 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. XD
D. 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.net/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.
I thought of the exact same solution and it got accepted. But how can we prove it's correctness?
how to do problem c??
don't solve just watch anime and sleep
It is Russian language. Посмотрите на то, есть ли одинаковые числа. Посмотрите на то, есть ли такое число, у которого каждый остаток встречается по хотя бы два раза И так и так ответ Нет.
Not my best contest performance-wise, but several of the problems were excellent--F may well be my favorite problem of the year. Thanks to the authors!
D was very very similar to https://codeforces.net/gym/103149/problem/D. Both are very good problems in my opinion! But yeah, unfortunately the idea was not very fresh...
Why so many downvotes and hateful comments? IMO, the problems are very good (at least A-D), thanks to the authors, despite my terrible performance.
can u explain C pls?
This was my approach https://codeforces.net/contest/1770/submission/187361827
The answer is NO for this test case.
Try to generalize your solution. Checking only remainders of division by 2 isn't enough. In this test there are >= 2 numbers for each remainder modulo 3.
can someone please tell in which test case it got stuck? 187372015 and why this one got accepted 187372786
The $$$m$$$ operations should be performed in order. However this is not mentioned in the statement.
Ok. Here, goes how I approached A-D today.
Discussion for D:
First, the 1st player cannot give the 2nd player any chance to choose from 2 different numbers, because when you change any number of a permutation you will break it.
Therefore for any i, {ai,bi,ci} must contain <=2 different elements. If ai==bi, no matter what ci is, pi (the ith number of the final permutation) will be equal to ai, else pi=ci where ci==ai || ci=bi.
Then we construct a graph with vertex number 1-n and add edge ai--bi for each i. We must assign a vertex for each edge and each vertex assigned must be distinct. We consider for each connected component. If there is a component where vertexs are less than edges, there are not enough vertexs to be assigned in this component. Because in the whole graph there are n vertexs and n edges, there must be equal numbers of vertexs and edges in each component.
Then in each component with k vertexs and k edges, because a graph with k vertexs and k-1 edges is a tree, this component must contain exactly 1 cycle. If length of cycle >1, we have 2 different ways to assign vertexs for edges on this cycle (accroding to 2 directions of the cycle), and each other edges in this components has only 1 vertex can be assigned (in each step we assign a leaf vertex to the only edge connected with it, then delete the vertex). if the length of cycle ==1, which is a selfloop, we can choose any number for ci.
Therefore, ans=product(c has different number of vertexs and edges? 0 : c has a selfloop ? n :2), where c iterate among every component of the graph.
Sir can you please tell what prerequisites should I know before going to this problem?
Basic graph theory
Did anyone solve D using recursion?
I figured that the number of recursive calls will be atmost equal to the number of connected components in the graph approach
However it is giving me MLE
When you use a vector as a parameter of a function, it will be copied into the next function call. When the recursion is too deep it will cause MLE.
Also coping a vector consumes much time. Use dosomething(vector &v,…) instead if possible.
(By the way in java you always transfer an object by reference, and you must copy an object explicitly)
You wrote
void help(vector<int> x,int i,int ans), and this will use $$$(recursion \ depth)\times(the \ size \ of \ x)$$$ memories. Tryvoid help(vector<int> &x,int i,int ans)instead.This contest was harder than usual. No idea how I didn't lose rating.
A had me freaking out for 30 minutes lol.
Can problem c be solved by using binary search?
Thanks for green, finally in the end of the year and begin the new year with another plan to cyan.
Update: Is it forbidden to say "Finally I've become CM" on codeforces?
My vengeance explodes!
In this round there are about 100 accounts that are using the same code. The logic of these codes are exactly the same. Only some words have been replaced. And these accounts get almost the same score in every problem. Please check it.
Someone posted a blog about this issue .
I hope that all those accounts banned from codeforces.
2022 ended with dark memory,i felt the contest.
This contest boosted me to purple, orz.
Congrats to my friend prvocislo, who promoted to Grandmaster with a rating change of +1.
revision: the rating change has been adjusted to +2.
Thank you! q(≧▽≦q) What a nice way to end this year!
Thank you for this nice round and fast editorial. I had fun participating today. I have a question though, I didn't understand the prizes. What is N?
Virtual currency offered by sponsor NEAR
https://codeforces.net/blog/entry/110638?#comment-986079
Thanks
Thanks for keeping such a wonderful contest. It ended my big negative delta streak from past 7 contests.
It was a good contest to lose all the rating I gained in 2022
So finally I can celebrate this new year with my maximum rating.Thanks for this nice round. :)
Really frustrating year, gave 60+ contests and solved 700+ problems with a rating greater than mine, still not able to cross 1300, reached a pupil in may who was still not able to be consistent on that also, after every contest feels like defeated and came and doubt on my existence. Will work on my weakness and will give it every single contest with full energy next year as well! Thank you 2022 and welcome to 2023!
ArtAlex has OK on D, but he has O(n^2) solution(Kuhn's algorithm)
Does anyone know what is test 165 of pretest 2 at problem D?
Why I cant open the tutorial page, it shows me: " You are not allowed". How can I fix this ?
Same problem here, any ideas how to fix?
Edit: I can see now, thanks!
I tried too many times. I think they forgot to unlock us
It's by a misoperation and fixed now. Sorry for the inconvenience.
Всем привет! Когда будут отправленi Нiары?
Can somebody help me...why this submission of mine got runtime error. It passed all the pretests but got runtime error on test case 4. Thank you in advance for your time and effort.
https://codeforces.net/contest/1770/submission/187326346
Your code doesn't handle the n=1 case. Since in n=1, you are accessing arr[1] and all[1], its showing RTE. Handle it separately and it will pass.
A little question: where is the Chinese editorial?
It's available now, sorry for being late.
Why BenQ uses Rust for solving H in Goodbye 2022 contest? Is there any benefits over C++?
In this contest Prize of Ⓝ 1 is for contestants ranking between 1024-2047 places What is Ⓝ 1 actually
It is crypto. Just see coinmarketcap. ! N is around 1.3$
When shall we get that crypto... is is via mail or something else
I think y will get a message. Just check every day.
From starting off as a newbie this year to becoming an expert in the last contest of 2022...it was totally worth all the efforts...! Loved yesterday's contest....Thank you for the contest!
I passed problem D at 02:24 of the contest after 3 wrong submissions. Though I got only 664 points in D, my rank rose for a lot. My rating also rose more than $$$2^7$$$. I am very glad on the last day of 2022.
2023 is near. Hope us can get higher rating!
Most importantly, happy new year!
What anime is this?
Good problem. It's about a Vtuber project instead of an anime.
Hey MikeMirzayanov Nanako , I got these 1 messages 2 hours ago.
Attention! Your solution 187313065 for the problem 1770A significantly coincides with solutions Rakesh_898/187313065, rk0145906/187325506, Krtrk_007/187361450. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I haven't used any online IDE or compiler, nor did I copy the solution from anywhere. I even don't know any of these persons, not in real life nor on Codeforces. The questions were pretty simple & so there's a very high chance that the logic might be same for two different individuals.As you also can see that i submited the code at 18:24 and other two submitted the code at 18:44 and 19:51. my logic is same as that of editorial, that doesn't mean I got access to editorial beforehand. It's just a coincidence that the logic matched. I don't know what else can I give as a proof. Please look into the issue, hoping for a resolution.
I feel sorry but I have no access to deal with this sort of issues.
Someone goofed up
when we will be able to obtain the near coins ?
Any updates on receiving the near coin prizes?
Why the answer of problem F is zero when n is an even number?
How do you create PDF?
I type in Typora and export it as PDF.
when will the ratings for problems get updated, it has been more than a week since the completion of contest, but problem ratings are not yet updated.