Hello, Codeforces!

I am happy to invite you to our Good Bye 2023, which will be held at Dec/30/2023 17:50 (Moscow time). **The round will be rated for all the participants.**

The tasks were created and prepared by 74TrAkToR, zwezdinv, OR_LOVe, marzipan, platelet.

We would like to thank everyone who helped us a lot with round preparation:

- 74TrAkToR for excellent coordination and useful advice.
- Testers operasfantom, i_love_penguins, IzhtskiyTimofey, __Foam, a_ok, bibikov1, Kihihihi, ace5, kostylevGO, Pavarishko, Alex239, alex.kudryashov, htetgm, katzi, dasha..zhilina, green_gold_dog, RomkaRS, Mangooste, _IVON_, EJIC_B_KEDAX, maks_matiupatenko, plagues, platelet, Golovanov399, Endagorion, KbltQaQ for high-quality testing and valuable advice.
- errorgorn, azureglow for the idea one of the tasks and helping with its preparation.
- MikeMirzayanov for amazing Codeforces and Polygon platforms.

During the round you will need to solve **8 problems**. You will have **2 hours** to solve them.

Score distribution: **250—750—1250—1500—2000—2750—3750—(2750+1750)**

We wish you good luck and high rating!!!

i hope for a very good contest before 2024

i hope to end the year with cyan rating.....:)

same

I hope to keep it :)

same

PFP ;);)

congratulations!

thanks man .....

They are changing the system or something, they are already moving it twice

so a year can go by hahaha

I was wrong...

wdym this is best round ever

i hate newbies

Someone went on my computer and trolled me. Unfortunately I cannot delete the comment.

you hate newbies

someone trolled me, i don't actually hate newbies

yeah i know, the previous comment is a joke anyway

he does

he actually does hate newbies. I was with him when he typed the message.

they hate newbies

I hate my rating (newbie, 805) too

Me too.

As a tester, I wish you have fun (and do not rage at the end of the year) Good luck!

Dyrachio as a TESTER POGGIES

this is some new trend in cf

Now(After contest) I know Why you said that :(

As a tester, I will not write any more rounds this year

As a tester do you write rounds?

As a participant , it will gonna be my last contest this year

does this contest have some dev-4 level problems?

This contest easy as fuck bro don't worry

haha until the shit gets real !! :)

If it gets real I'll just start crying not that deep

it got real

Famous last words .

haahah

Thank you

Lets hope aliens attack in 2024 and teach us how to P = NP before destroying us

I think they would give us a quantum computer instead

Why depend on aliens do it yourself instead of posting sh*t online

Let's hope aliens attack in 2024 and give us a better round than this one before destroying us

Good Bye 2K23 and Welcome 2K24! Hope that the last round of this year will be more enjoyable :)

It turn out shit.

Hoping to finally cross 2200!

With your current color(NY magic) it sounds hilarious. (-200)

placement season preparation going hard.

I hope it will be my last nice and impressive round in this year

Wish everyone a happy new year 2024!!!

goodbye 2023

Hopefully 2024 will be good lol

The contest name is so excellent that I simply couldn't resist participating in it:)

So the final contest for the year 2023, hope for everyone to get positive delta

Good Bye 2023..!! Wishing everyone a

Happy New Year. and hope for a very good contest before 2024.`Happy Coding.`

After bad performance on the last div 4, I hope to reach pupil in this contest

Never =))

Just because this round is trash

hi, MAGICAL International Grandmaster :)

I hope that this round will be lucky for all of us!!!

bye 2023 , hi 2024 !

I hope that this round will be lucky for all of us!!!

Any idea about the difficulty of the contest ?? Like similar to div2 div3

Div. 1+Div. 2 ?

= Div3 ?

Why so many downvotes?

Did u practiced on some other platform before as i can See u were already good starting with your first contest

as a tester, i can wish you only good luck

Div 2??

Looking at the previous year contest it looks like it will be a Div 2

Hoping to reach cyan before year end :)

What will be the score distribution?

Hi 2024 good bye almost prime 2023.

What's the overall difficulty of the tasks?

good bye! <3

is the difficulty of the tasks similar to Div 2?

No it'll be div.1 + div.2

The first 6 problems are like Div.2 A-F. The last two are harder problems, like Div. 1 E and F.

Goodbye 2023 and Hello 2024... I hope that this year will be an end to all your problems and difficulties and that this year will be a year full of joy and happiness for everyone. Happy New Year everyone 2024.

looking forward to it

hope to have fun at the last contest of the year

i hope, i'll reach cyan in this contest

same

Happy New Year everyone! Wishing happiness and joy for everyone in 2024, hope everyone gets positive delta in the last contest of the year!

Hoping to end the year with + delta

Wow so E is hard. Gotta lock in

also why only 2 hours

Relatively easy problems? That would be my guess

I hope it will be a good end to this year. Good luck to everyone

I am expecting to reach the pupil! Let's see what happens in the last contest of 2023!

Same! I am at 1120 hoping to cross pupil

I promised last week that I won't play CF anymore before my final-exam. But...Hey guys,that's the last time in this year...

Hope to have a better time in 2024!

I need +70 or I lose the bet to pk_27. :(

I need +70 or I lose the bet to plAtEaUpUs

wow so many problems but i only wish to reach pupil after this round

I hope to achieve a score of 1600 in the new year.

marzipan did the score distribution for problem E and G changed ?

hope i can solve 2 of this:(

this will be hard :skull:

Hoping for a doable D

bye 2023!

I don't have courage to participate good bye and hello contest as I lost 200 rating last time.

Based on the score distribution, can we expect that H1 is approximately as hard as F?

Looks like a math-force.

74TrAkToR for excellent coordination and usefulBro, it isadvices.advicenot advices. Advice is an irregular plural.thanks sirs helps mes englishs.

As a participant, I hope everyone will be happy in 2024!

May this contest help me in reach pupil

Goodbye 2023!

Always great to end the year with a contest!

Why is the

SCOREdistribution changing every couple hours?At the end of the year, I want to have my best contest !!

Hope it ends my slump. So the year enda on a Good note.

as a participant, i say: Happy New Year!

it's not sponsored by near?

Sad to say....but this gonna be my last contest for this year:(

i wish everyone good luck ;)

Good Bye 2023!

Good Bye 2023

Goodbye 2023,Or as they say in China: "再见2023".

I hope to get good results.

The last round will be good for those who are trying hard for the whole year.

Good luck to everyone.Chilling contest, chilling day.

Hope no queueforces like yesterday

Usually that's only a problem in Div.3/4 and not in Div.1+2, but we'll see

Happy new year in advance, everyone!

I don't wanna go back to being a newbie, please :!!

Good luck to everyone. This will be my first ranked contest

Good luck!

is this like a div2?

div2 + div1

It's a pity that it was postponed for 5 minutes(

10 mins :/

10 minutes :(

15 mins:(

guys，what happened? why is it put off？

it has been postponed for 10 mins

Good luck for us!

Good Luck!!

1 refresh cost me 10 min... lol :)

Hope the queue is not long today.

is the contest postponed for severval minutes?

As a non-tester, yes.

it seems so

yes, by 10 mins

Yes

yes

Because of CloudFlare?

anyway good luck to everyone today.

Is the contest postponed for 10 minutes?

what? not 22:35?

Good Bye 2023+10minutesGood Bye 2023+15minutesnowHope I get some ratings :D

Delayed ??

Out of curiosity, are the delays due to registration issues again?

I'm pretty sure I registered ~45 mins ago, but when I reopened CF around 20 mins I wasn't registered (and had to register again).

EDIT: Managed to reproduce the issue, opening the list of registered friends causes me to be unregistered even without clicking the unregister button on that page.

I also opened my list of registered friends. Didn't happen to me though.

I registered and entered the contest. After clicking "submit" on problem A, I found that there are no submission logs, and the submit button disappeared. After that I tried to click "submit code", but it said that I was not registered for this contest. I have to wait until 15:00 UTC for additional registration before submitting my code.

why 22:45

good luck!

Good bye 2023 :>

April fool 2023? XD

Looks like 2023 isn't quite ready to leave us yet

Father time is procrastinating, he's human too.

The Last Ride of the Year...

If I turn cyan today, it would be an actual "happy" new year :)

best of luck ;)

How to get rid of "Checking if the site connection is secure"?

Good bye 2023(((

Aren't we 2018 now? T_T

I thought this problem was solved already back in 2018. But it still exists in 2023 but with different language :P

bro just lost from Nott'm Forest he lost track of time

And yet another delay xD

Delayforces

Idk, but today I don't feel like giving contest X(

one refresh cost me 5 more minutes

I wish I had given up the round after knowing it had been delayed 15 mins

why still late for 5 minutes

Why 5 more minutes postponed

Are you kidding me? -_-

Delayforces!

With the repeated delays, I am starting to doubt the quality of the problems.

I guess its more likely to be a problem with platform issues such as judge stability (i.e, high risk of a large queue).

Now, it looks like the concerns were spot on

Good luck!

What happened? Do the contest authors not want to say goodbye to 2023? Rescheduled again(

and there's no explanation on announcement

Why delayed?

Ig the contest will start untill 2024

GoodBye 2023 typically

20:05 No

20:15 No

20:20 No

20:23 XD

uh oh

I don't wanna use codeforces mirror but cloudflare keeps reloading the page when i verify :(

What the he*ll bores?

I wanna cry(

Hope this is the last postponement...

Why it always delay

This is the most annoying thing that website can do

why did the time got rescheduled ?

This is my first comment on codeForces, lmao

stress

why is the time changing? I can't get on to the contest

Delay no more please

Codeforces ..its not april month XD

Can we get a

Belated Good Bye 2023:DDelayforces pls! :)

Goodbye "Good Bye 2023"

I was 10 minutes late and then to my surprise, I logged in 5 minutes earlier!

Bruh why codeforces trolling?

Delayforces

delay until 2024?

last contest of this year

5 minutes delay takes away the time about 0.3% of this year

8% of remaining 2023 into a dust. Only 22h remaining in 2023 at last.

Today’s contest is sponsored by SBI

lunch time chal raha hai

C'mon. Don't be angry. Let's focus on the contest.

Delay it one more time and It will be welcome 2024

Everytime i refresh got 5 min penalty

April Fools Day Contest 2023

As a tester, I think this round will be amazing

this aged like milk

Seems like it will keep on being rescheduled till its actual year end for Mike. X0

22:50?(UTC+8)

Why am I sweating in winters

I could have played 1 more Valorant-ranked game.

same

thank you sir for this amazing platform I wish this platform should be forever .

welcome the coming of 2024!

The delay was so long that contest become Hello 2024

I was registered, but I can't submit because it says I'm not registered. Can someone please fix this ASAP?

YES please

I was registered and now it is showing not registered and there is also not option for registration

Good Bye 2023 with LOL contest ....registered for it but showing i am not...:)

Ending 2023 with another mathforces round this is amazing

the rooms are broken i cant find mine

Thanks for the contest, Finally Cyan :)

Worst D I have ever seen even though I solved it.

that's what she said :(

It's really mathyy

it looks constructive to me

It is both

Now I'm really curious about the intended solution of H. Because it's 100000000000% not my solution.

there is an already available solution for this question on google.

link?

Exactly. And it's way, way too simple for last problem.

Biggest Mathforces of the year

Good Bye my rating... See you in the next year

same for me bro

Now I'll become a purple coder again :)

How much did 74Tr paid to Mike ?

I guess problem H is not an original question

I have a message for the author of D.

Your message is: tof to root

Mathforces

Sorry, guys. I was trying to report a streamer, but I didn't realize that my question would be visible to everyone.

All is well that ends well :( But It wasn't

And the prize for the worst contest of 2023 goes to...

Is H copied from somewhere or is it just easy? I dont remember the last time the last problem was solved so fast in a div1.

It is just simple if you have some basic knowledge on subspace counting :) see https://atcoder.jp/contests/abc278/editorial/5238 for example.

Sadly I don't :(

If it really is that simple i wonder how it got past testing. I just imagined it was from a random competition and people started googling it.

Thanks for the link though! Will read.

btw, i just know it can be found on oeis(https://oeis.org/A286331). It should make more sense now xD

how to solve E?

Build segtree on euler tour.

Now we do a dfs, and when are at node $$$u$$$ and have traversed all nodes in its subtree, for each node $$$v$$$ in its subtree, store only those nodes $$$v$$$ such that no ancestor of $$$v$$$ in subtree of $$$u$$$ has the same color as $$$v$$$. How to "store" such a node $$$v$$$? Simply add $$$+1$$$ on $$$[tin_v, tout_v]$$$ in the segtree (when deleting it, we will just add $$$-1$$$ on the same range) . It is equivalent to only considering highest occuring color on all paths to prevent overcounting.

For node $$$u$$$, we can now find the optimal path when we fix $$$u$$$ as the lca. This is simply the product of the two maximum values of $$$(1 + max(tin_c, tout_c))$$$ accross all children $$$c$$$ of $$$u$$$. The answer is the maximum of this value across all $$$u$$$.

How D?

For larger n its this pattern. X on the left, X**2 on the right.

10000011 100000220000121 10000101 100002020010201 10000110 100002200012100 10001001 100020021002001 10001010 100020201020100 10001100 100022001210000 10010001 100200120020001 10010100 100202102010000 10011000 100220121000000 10100001 102010020200001 10100010 102010202000100 10100100 102012020010000 10110000 102212100000000 11000001 121000022000001 11000010 121000220000100 11000100 121002200010000 11001000 121022001000000 11010000 121220100000000

Wow great problem

Or you can simply construct these:

might be simple question, but how do I know for sure these are perfect squares? Did you brute force for small n and guess the pattern? or is there some kind of proof for this?

Observing the answers for <=7 will be enough

A0..n..0B^2 = (A*10^n+B)^2 = (A*10^n)^2 + 2(A*10^n)(B) + B^2

Notice that $$$(10^k+3)^2=10^{2k}+6\times 10^k+9=10000\ldots60000\ldots9$$$ and $$$(3*10^k+1)^2=9\times 10^{2k}+6\times 10^k+1=90000\ldots60000\ldots1$$$.

So, the answer for something line $$$n=11$$$ can be:

you can try observation. I think its hard in this case, but possible.

I bruteforced for n<=9 and solved it by finding the pattern that way.

Jokes of assumption

H: https://math.stackexchange.com/a/1859668 ?

https://math.stackexchange.com/questions/3259887/distribution-of-matrix-rank-over-finite-fields

The most down-to-earth formula I found (and implemented) is here, at the bottom of page 19 (or 26 in PDF numeration): Thesis of Geoffrey Critzer

Along with how to infer it in the few pages above (which can be skipped in contest time).

btw, i wondered for a while how to deal with "divided by zero" is issue. It seems that the constraint does not imply $$$p^k \not\equiv 1 \mod 998244353$$$?

Interesting, I just assumed the values are "good".

Perhaps system tests will say otherwise :) .

i asked the authors for clarification during contest, and was responded "no comments" as expected xD

That may mean they (will?) add such tests before system testing phase. Especially if the author solution avoids such divisions. Would explain the wait, too.

It might not be an issue at all (and I think most contestants, myself included, kinda lucked out here).

By repeatedly factoring, you can see that $$$f(n, p, k)$$$ is

multiplied by some nonzero constant (everything happens in the field of numbers modulo $$$998\,244\,353$$$).

I claim that one of two things is true: either there are no zeros or there are strictly more zeros in the numerator than in the denominator. Let $$$r$$$ be the smallest positive number such that $$$p^r = 1$$$. It's a well-known fact in number theory that if $$$p^m = 1$$$, then $$$r \mid m$$$.

In the denominator, the first time a zero appears is the term $$$p^r - 1$$$. By that time, we have had all exponents $$$n - r + 1, \ldots, n$$$ in the numerator. That is $$$r$$$ consecutive values, one of them is divisible by $$$r$$$. Since the terms in the numerator are squared, it means that we have two zeros in the numerator among the first $$$r$$$ terms. Repeat the same argument for all blocks $$$[tr + 1, (t + 1)r]$$$ in the denominator, and the claim follows.

Since there are more zeros in the numerator, if you go back to the integers you can see that the entire thing is a multiple of $$$998\,244\,353$$$.

If you had a "typical" solution (e.g. incrementing $$$k$$$ and adding terms to the formula) and your code doesn't throw an error when calculating the inverse, then you could just pretend that no division by zero ever occurs and your solution would still be correct. Even if you had a different solution using some similar formula (maybe with additional pointless terms cancelling out), you can probably show that it is correct using a similar argument.

Thanks for your clarification! That's a cool proof.

Was this contest made from the rejected problems of Good Bye 2013? :)

I tried submitting C last minute but it lagged. Really annoying.

WTF H1 & H2???????

tests your googling skills

ruined my last cp contest of year

I hate game problem so much like it's unreal

OEIS moment... https://oeis.org/search?q=1+49+294+168+&language=english&go=Search

Does anyone use the same method as me in problem D?

Violent enumeration of numbers $$$1 \sim 575000$$$ squared, calculate the answer for $$$n \le 12$$$, and find that the number of answers for $$$n=11,12$$$ has exceeded $$$99$$$. Simply add an even number of zeros after these numbers.

Submission link

I did that as well, D feels more like an April first question than a div2. D

I used the fact that 31, 13 and 14 work for $$$n = 3$$$ and extended it with zeros, explained by the following example for $$$n = 7$$$:

$$$1300, 1030, 1003, 3100, 3010, 3001, 1400$$$ (all squared)

violent enumeration lol

truly the best translation of 'brute force'

Anyone else lose time trying to find the n = 7 case for D? I was stuck for 30 minutes until I brute-forced it...

I tried with n=9 LOL

Problem H: Link (page 20)

Or alternatively, the literal first expression of this paper (free pdf on scihub)

how tf do u do B

i returned lcm ,but if lcm<=b then multiply lcm by lowest prime factor of a/b and return. it worked for me hope it passes system tests

prove?

The smallest divisor of n is one. Next is a prime number p. Next may be other prime number q, or p^2. In first case a = n/q, b = n/p. gcd(a,b)=n/(pq) and lcm(a,b)=ab/gcd(a,b)=n. In second case a = n/p^2, b = n/p. lcm(a,b)=n/p=b. p = b / a, n = b * p.

As you can see, b/a is a prime number in second case. It is unnecessary to check it.

will it be unrated because of H.

OMG H1&H2, doesn't any testers noticed the task is already exist?

Can you guys tell me which topics or questions I need to work on to build intuition for problems like problem B

Number system

that much I know

The moon is beatiful, isn't it? But this contest is ...

Did H leak?

Actually, you can just search for it and find many solutions, such as https://maths.nuigalway.ie/~eoghan/GroupPresentations/Cian-7Oct2016.pdf. Then you just look for q-analog implementations and adapt it.

Pretty sure this solves it. the first search result :facepalm:. I was seconds from submitting an implementation for it because I only found out about it near the end, but the page didn't load fast enough :((

What is this D????

[deleted]

How to solve B? Here is my code, it is getting wrong answer in 2nd test case......

void solve() { ll a, b; cin >> a >> b; if(a == 1) cout << b*b << '\n'; else if(a%2 == 0 || b%2 == 0) cout << b*2 << '\n'; else { bool f = 0; for(ll i = 3; i <= a; i+=2) { if(b%i == 0 && (b*i)%a == 0) { f = 1; cout << b*i << '\n'; break; } } if(!f) cout << a*b << '\n'; } }

First 4 problems were really really bad. Bad problems for Good Bye 2023!

very good guessforces, I have a good 2023!

Squeezed H2 using $$$O(n\log^2n)$$$ FFT using AtCoder Library's implementation.

Hope that it doesn't FST.

Can you share your solution?

Pretest and problem statement for A were very bad, seems like a

FORCEDproblem.Why in hell someone need to verify if I'm a human or not when only 15s is remaining in the contest?

How frustating it is to not being able to submit because of verfication?

THIS. THIS HAPPENED TO ME. I could not submit my code for C b/c of this. I am malding rn

Couldn't submit D. An already frustating contest wasn't frustating enough at the end of the year.

Did anyone solve D without brute-forcing and guessing the pattern, if so, how did you come up with the logic?

Yeah i guessed a pattern but ain't sure abt that

i did not guess the pattern i coded for n = 5, 7, 9 digits and got the pattern.

Couldn't solve it as I spent most of the time generating cases for higher n and verifying locally. I think the solution is to append "00" and insert "0" in between the strings {"169", "196","961"} for higher n. For example {"16900","10609","19600","10906","96100","90601"}

10906 isn't a perfect square...