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, artew, IzhitskiyTimofey, __Foam, a_ok, Bibikov, hopele555, 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, sadness 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.....:)
I hope to keep it :)
PFP ;);)
congratulations!
thanks man .....
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
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
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 .
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
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.
Wish everyone a happy new year 2024!!!
goodbye 2023
Hopefully 2024 will be good lol
So the final contest for the year 2023, hope for everyone to get positive delta
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!!!
Any idea about the difficulty of the contest ?? Like similar to div2 div3
Div. 1+Div. 2 ?
= Div3 ?
Why so many downvotes?
as a tester, i can wish you only good luck
Hoping to reach cyan before year end :)
What will be the score distribution?
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.
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!
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...
I need +70 or I lose the bet to pk_27. :(
wow so many problems but i only wish to reach pupil after this round
marzipan did the score distribution for problem E and G changed ?
Hoping for a doable D
bye 2023!
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 useful advices. Bro, it is advice not advices. Advice is an irregular plural.
thanks sirs helps mes englishs.
As a participant, I hope everyone will be happy in 2024!
Goodbye 2023!
Always great to end the year with a contest!
Why is the SCORE distribution 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.
it's not sponsored by near?
Good Bye 2023!
Good Bye 2023
Goodbye 2023,Or as they say in China: "再见2023".
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
Good luck!
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？
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.
yes, by 10 mins
yes
Because of CloudFlare?
anyway good luck to everyone today.
Is the contest postponed for 10 minutes?
what? not 22:35?
Good Bye 2023+10minutes
Good Bye 2023+15minutes now
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.
Good bye 2023 :>
April fool 2023? XD
Looks like 2023 isn't quite ready to leave us yet
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"?
Aren't we 2018 now? T_T
bro just lost from Nott'm Forest he lost track of time
And yet another delay xD
Delayforces
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 :(
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 ?
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 :D
Delayforces pls! :)
I was 10 minutes late and then to my surprise, I logged in 5 minutes earlier!
Delayforces
delay until 2024?
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
C'mon. Don't be angry. Let's focus on the contest.
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
Why am I sweating in winters
I could have played 1 more Valorant-ranked game.
thank you sir for this amazing platform I wish this platform should be forever .
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?
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
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.
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?
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]
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 FORCED problem.
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?
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...
You can observe pattern by brute force.. see my code both brute force and pattern...
D was a pattern question right? for n=1 i can make 1 ** n=3 i can make 13 31 14 169 961 196** ** n=5 i can make 103 130 301 310 and 14xx kinda pattern?** tell plz or was it a dp question?-
you could make the solution by using a 1, a 6, a 9 and a bunch of 0's, and the rest you can guess
For n=13 there exists 99 numbers that have the same multiset of digits. For larger n, just add zeroes to the end, and for smaller n, just bruteforce
Can you share you solution I'm bit confused in implementation
I wasn't able to solve during the contest, but I think something like this should work: https://mirror.codeforces.com/contest/1/submission/239718740 I saved the 99 numbers in a string to save time on the submission. Slight modification on bounds so that solution was fast enough: https://mirror.codeforces.com/contest/1916/submission/239724876
Start with 169, 196 and 961.
Now for the next n i.e. with two more digits simply add 00 to each, and you need only two more numbers. Those are 1x6x9 and 9x6x1, where x is (n-3)/2 0s.
With this you can go on to find for any n.
How to prove that adding (n-3)/2 zeros between the numbers will make it a perfect square ?? can you please explain ?
It easier if you look at its root. 1x6x9 is obtained by squaring 1x3, where x denotes some non-negative number of zeros.
However, for your question we can rewrite 1x6x9 as 1a + 6b + 9, where a and b denote some non-negative number of zeros.
With x = (n-3)/2, we have a = n-1 and b = (n-1)/2, since n is odd, both a and b are even.
1x6x9 = 1a + 6b + 9 = 1b*1b + 2*1b*3 + 3*3 = (1b + 3)^2 = (1x3)^2
1x6x9 is a perfect square is proven by the existence of its integer root.
Apologies if the notations seem a bit unconventional/confusing, hardcode some 0s inplace of x
Yeah this is my solution, pattern like you described
trash problem D, downvoted. :(
D is the worst problem I have ever seen.
++
oh i feel i got a slap instead of gift for the new year
Good Bye 2023, Good Bye my blue color T_T
Why is the last problem of a Div1+2 round solved by as many as 140 participants? Do you have any idea?
Because the answer is easily googleable.
how E??
a more difficult f
Good Bye 2023Bad Bye 2023 , worst contest of 2023At least thanks for E
How to Solve?
During dfs we can maintain diff function for each vertex in subtree (to current vertex). If current vertex has value $$$x$$$ we need to add +1 for each vertex in its subtree except vertices already contating $$$x$$$. This vertices are united to subtrees so we can add +1 to whole subtree and add -1 to these subtrees. And after just choose two maximums and update answer.
The rest is usage of rmq with range add and find subtrees where -1 will be added. There will be no more than $$$n$$$ such subtrees.
Thanks!
can you please elaborate on how are you adding +1 over a subtree? Are you using a euler tour ?
good bye rating round <3
I felt like D gave you a lot of space for your own creativity))
I have a headache after the contest. Can anyone else relate, or is it just me? ;_;
how about having headache before, during and after the contest ? :)
I wasn't assigned to any of the rooms during the contest.
I checked my submissions' page (the one which can be opened in the "standings"), and there isn't any room information as it used to be in the first line.
As a result of that, I can't make any hacks (and I thinks my solutions can't be hacked by others too).
I checked the standings and saw many people with the same problem.
I asked about that during the contest and got replied with "no comment".
Will this happen in the next contest? or There's some rules about this that I didn't noticed?
mathforces
If the test data of G isn't wrong, I will start to learn Russian.
1916B - Two Divisors
I don't think problem B was a good one.How can we determine that input values a=6, b=8 are not valid?
I think they expected us to assume that the input has a valid answer.
this is hilarious
If x is divisible by 6 and 8, then it is also divisible by 24. However, that means 12 is a larger factor, so a and b are not the largest factors.
The author has stated that a, and b will be provided in the test cases such that it always leads to a valid x. I will quote the statement — "It is guaranteed that a, b are the two largest divisors for some number 1≤x≤10^9. "
I understand sir. but that's not how you write a problem. the condition(1<=a<b<=10^9) says it is possible to have input such as a=6,b=8;a=4,b=8... So, as an ordinary human being, anyone can think of it. No one is going to make a research on which kind of inputs are possible and which are not to solve B. Therefore it's not a good problem.
for problem B, if a=6, b=8, what is X ?
24
EDIT: Wrong, it will divide 12!
But 24's biggest divisor is 12, not 8. The question does not guarantee input is valid !
nvm i missed reading a line
Yeah! got it late
you are right
its not vaild input i guess. No ans exist for this imo.
It isn't possible to have a number with 8 and 6 as it's greatest divisors
This round quality compliments my experience of the entire year,garbage.
First time I ever feel need to downvote round. Terrible set.
Lets see if we can make this blog the most downvoted blog in 2023 as a prize for the most trash round in 2023
Someone might like B and C or not, we can argue. E was nice. BUT D IS OBJECTIVELY THE WORST PROBLEM THAT WAS EVER MADE IN THE HISTORY OF THIS PLANET.
Agree
Not gonna lie, problem D made me think for little bit.
The quality of the contest doesn't deserve the title "Good Bye 2023".
More like "Goodbye good quality problems".
These types of contest along with CloudFlare Feature is quite annoying
problem D is definitely something
D told us look question carefully, you can find the answer in the first line itself
can you tell me what is bad about D, i never solved a D so i dont know how normally Ds are
Start by generating a sequence using 13, 31, and 14 for n = 3.
For n ≥ 5, calculate the solution for k = n — 2. Multiply these numbers by 10. Then, add two more numbers: 100...003 and 300...001. After finding those numbers for n, square them and you get the answer.
I don't know why but it works.
Weak pretest of A and very easy H1 and H2. Not a good round. I hope Hello2024 can be better.
74TrAkToR Could you please OEIS the sequence before you use a "several-integer-input-problem" in contest next time?
i actually want to quit cf after this round
i actually want to quit life after this round
Editorial should be fun, no way this was the intended solution for D right?
Typical 74TrAkToR round :)
Am I the only one who actually solved H instead of googling the answer?
apparently its well known (see https://mirror.codeforces.com/blog/entry/123930?#comment-1100429 ) so i suppose not
Actually, the ending of 2023 would be much better without this "awesome" contest. Thank you very much for ruining everyone's expectation.
Yes, I love you too.
Today's contest was the greatest I have ever seen. Spectacular problems from start to finish. The problem D was exceptionally good. Having to hardcode and look at some 1s 6s and 9s truly is the epitome of contest problems. I definitely didn't have a headache and no, I won't cry myself to sleep.
Thanks for making 2023 even more bearable for me!
Hacking overflow solutions in A was an interesting task in itself. You basically had to find at most $$$5$$$ numbers less than or equal to $$$2023$$$ such that their product is of the form $$$k\times 2^{32}+x$$$ where $$$k$$$ is any positive integer and $$$x$$$ is a factor of $$$2023$$$ (i.e. $$$x\in {1,7,17,119,289,2023}$$$).
The smallest number satisfying this is $$$3\times 2^{32}+289 = 12884902177=7\times 691\times 1489\times 1789$$$. When this product overflows in the hacky solutions, the value becomes $$$289$$$ which is a factor of $$$2023$$$ and they print $$$\texttt{"YES"}$$$ instead of $$$\texttt{"NO"}$$$. I really hope such tests are present in the system tests.
There's no overflow if you use long longs right?
You could also print five numbers whose product is $$$2^{32}$$$, which would overflow to $$$0$$$ and cause a runtime error in many solutions which then attempt to modulo by $$$0$$$.
Well, that works too and is much easier to find. I was so focused on getting WA that I didn't think about this, lol.
For solutions with a test like
2023 % product == 0, another idea to hack them is to use $$$2^{32} - 7 = 3 \cdot 37 \cdot 167 \cdot 223 \cdot 1039$$$. (I kept making Wolfram Alpha factor numbers around $$$2^{32}$$$ and finally found this!)And yes I've just realized $$$2^{32}$$$ works just fine because it causes zero division...
You can just write test like this:
And this product will be equal to
0(with integers).Finally the round where you can hack someone in easier problems! ++
F is https://www.luogu.com.cn/problem/P9394 by ix35 and H is very similar to 1603F - October 18, 2017
By the way I think I have a funny solution to D. I noticed through brute forcing that for 11 digits there is > 100 different numbers, so i just copypasted the best sequence of numbers for every number of digits up to 11: https://mirror.codeforces.com/contest/1916/submission/239681879
I also got TLE on pretest 1 for trying to calculate it instead of copypasting, lol
I have the same solution (but I didn't notice n has to be odd, so I did the same for 12 digits too)
Great solution, tbh after seeing this solution I feel problem D was not bad at all XD. Also there have been similar problems like this before on cf as well, but ig for most people doing cp now this might have been new, hence the angry reaction. XD
What is special about testcase 15?
The worst contest in 2023.
2:00 Hours only wasn't enough
my theory is that they didn't have problems that were hard enough for strong contestants so they just shortened the length of the contest to artificially increase the difficulty
How to do B?
I know there are another solutions and in fact I don't think this is the intended. But the one that I've used is this one:
Okay you know that $$$a \lt b$$$. They are the biggest divisors of $$$x$$$, if we don't count $$$x$$$. So it means that $$$b \cdot e = x$$$, where $$$e$$$ is the smallest divisor of $$$x$$$. So if we find $$$e$$$, we can know $$$x$$$. So the key is how to find $$$e$$$. We can be sure that either is in the decomposition into prime numbers of $$$a$$$ or $$$b$$$. This is because if $$$e^{2]$$$ divides $$$x$$$, $$$e$$$ is going to divide $$$b$$$ too, but if not, $$$e$$$ is going to be divided by $$$a$$$.
So you can just iterate over primes until we reach one that divides $$$a$$$ or $$$b$$$.
If a is a factor of b, than the answer is b*b/a, otherwise the answer is lcm of a and b. So yeah, I don't think your solution is intended)
Yes hahaha, in fact i've got tle on test 5. I don't know why, but maybe it was just not suposed to get accepted
I doubt my mathematical skills after the contest
I saw some blogs asking something like "what is the worst problem in 2023". Seems like voters have been tricked by the author of problem D!
What a disaster this was.
so much maths
I feel like crying after this contest
I'm not super shocked by authors setting a purely mathematical problem for 4500pts, thinking it's very difficult. I'm shocked that so many testers went through it and didn't try to Google it. Even just looking at the statement you feel like this must've been an original problem only in the 1800s.
cringe D
with all respect , round was terrible
problem D is so weird.
I'm gonna go and say (controversial opinion time) it might be worth making this contest unrated. The balance of top ranks is completely screwed by H since it's worth so many points and takes so little effort to find, or even a surprisingly small amount of effort to figure out. In addition, the gaps between number of solutions for other problems are huge.
This is a bad situation to be in as a contest organiser, where you're either discarding a bad contest even though you don't need to (results are not invalid, they just suck), or you're not discarding a contest even though the results suck.
The most memorable contest throughout 2023, in a way
disaster
just learnt that guess forces are also welcomed by codeforces.
in D just look at number 31
31^2, FOR SERIES OF 3 ANAGRAMS 31^4 for series 5 anagrams.
and so on.
what's wrong with D, I was stuck at B.
2023's worst contest DELETE H!!!!!!!!!
Can we officially call this MathForces?
I hated C so much
ABC meh
D I can't evaluate it coz it is AD-HOC.Personally I dislike it.
E a bit classical,but not bad.
F I used a random algorithm and passed it easily...
H Bro why it could exist in a codeforces round in nearly 2024???????
I see A got hacked for many people. Is it because of integer overflow?
i think so
yes it is. that is how some people got lots of hacks
You are right.Some people multiply all the numbers in the b array and it exceeded the range of int.
This hacks a few people who used int. The product(2^32) overflows to 0 and could cause RE through division by 0 error
Before Contest... : D
After Contest... : |
Ah darn, I forgot that we're supposed to google problems instead of trying to solve them, what a newbie mistake by me
That's what I thought seeing people say that H is already online. That shouldn't have happened, but still, I think googling it instead of solving it is cheating.
it's not against the rules, however, the problem that everyone expects to be the most difficult shouldn't be solved by a simple google search though, serious oversight from the authors
Sadly I gave up googling too soon :(
Have been testers and coordinator awake when they were doing their job?
Solved D 10 seconds after the contest ended. That was a great lesson by the end of the year to look less at the scoreboard.
I really think this is the worst contest of all time. What the hell are these problems????
why pretests of problem A were so weak...Get fst qwq
Bad ending for 2023 ...
I guess it does make me want to say goodbye to 2023 harder
After participating in this contest, I felt like a failure
aGreE weLl
I thought people were overreacting when saying that this round was gonna be bad because traktor was coordinating. I was wrong.
Here is the test case for hacking problem A:
Anyone who didn't use long long will have a product of 0, which will result in RTE when checking 2023%(product of array).
What happened with the statements of this round? The statement of problem B is just incorrect (x is still a divisor of x), the word "parent" is used in two different ways in problem E, and problem F is so hard to read. I think testers were supposed to actually READ the statements.
It's also possible testers read the statements, told that the were unclear and the setters ignored it. This happened to me once as a tester so wouldn't be surprised.
I thought in such cases it is the coordinator's job to force the setter into fixing the statement before the round is held.
It probably is. Funnily enough TRAKTOR WAS ALSO INVOLVED: https://mirror.codeforces.com/blog/entry/121579
I was participating in an online round previously and there were many beginners there I remember they were shocked that the round was online and they said "oh it should be a test for googling skill". After problem H I think I am a beginner and they were masters actually :).
Positive topic: I like E! At once it seems very hard task, but it's actually good training of data structures and Euler Tour Technique. (though TL=1s is too tight)
(but H makes everything into trash, so sad)
You can simply find solution of H by searching example output "1 49 294 168" in OEIS.
https://oeis.org/search?q=1+49+294+168+&language=english&go=Search
I think this round should be unrated
Yes, it will be so illegal if this round goes rated
tired. time to quit. this game is just so fxxked up.
You can get the answer of H1 if you copy the example to oeis.Why can it happened in an codeforces round???Don't you guys try finding answer when testing???
74TrAkToR = -delta
It's a pity that H was easily googlable, but guys, have some respect to the authors, problems except H were alright (as I see by the comments D is arguable, but for me it is not that bad). Also I think that H is not even made by initial authors and was taken from proposed Div.1 problems (which explains that platelet is an author whereas other authors are all from Lyceum Num. 31 in Chelyabinsk).
thx for this round,but i think i waste plenty of time in these "excellent" problems,i should play genshin impact instead.
by the way,does 74TrAkToR play genshin impact?i think so because these problems are so "excellent" that only genshin players can make these.
Imagine if H1 and H2 were switched up and presented as D1 and D2! I bet a whole bunch more would've nailed them with googling -_-
fun" math force
Being mathforces was the least of the problems on this round
Though hating the fact that H1 is googlable, I'm now aware of the existence of oeis :v
I hope this contest is rated, because this is the first time I solve F in 1:57. I don't know what happened in H, but I will be very upset if it is unrated.
It wasn't the best round I've ever written.: 1) The authors delayed the round by 15 minutes (they had 2 months to prepare, but they couldn't do everything on time) 2) Task H is on the Internet, which is unfair to all participants. However, there are also positive aspects — the first 5 tasks were very interesting (not including d)
Ok, what's wrong with D?
What aspect of problem solving does problem D test?
Crytical thinking maybe?
If there was some logical path by which you could arrive to the solution then sure, but don't see how brute forcing small values tests any of that.
If it was this simple, why didn't you solve it?
Maybe because you still have to get to that idea and it takes quite a time?
you can construct answer from i to i+2
That's why n is odd
this is a task to build an example in which you almost don't have to think, but do the implementation
You have to get to that idea. If it was that simple, you could have solved it
Very Good.That's like my terrible 2023.
How to prove or disprove that $$$\prod_{i=1}^{n}p^{i+k}-1$$$ is divisible by $$$\prod_{i=1}^{n}p^{i}-1$$$ for all $$$n,k \gt 0$$$? I thought division by 0 would be an issue in H, but if that's true then every time division by 0 happens the answer is 0 anyways.
The quotient is equal to the q-binomial coefficient which is an integer.
Or, alternatively, you can check the degree of any complex root of 1 in these polynomials.
If n is 7168, p is 573817, and k is 3584, division by zero will occur, but the answer will be nonzero.
My code says that the answer is 0. Here's why division by 0 should cause the answer to be zero if what I wrote in the comment above is true(which it is, as the other 2 replies to it show):
The answer is $$$\prod_{i=1}^{r}\frac{p^{i-1}(p^{n-i+1}-1)^2}{p^i-1}$$$. For $$$k=n-r$$$, product of $$$p^{i+k}-1$$$ is divisible by the product of $$$p^i-1$$$. So, that expression is an integer multiplied by $$$\prod_{i=1}^{r}p^{i-1}(p^{n-i+1}-1)$$$. The latter is a multiple of the product of $$$p^i-1$$$, so if the product of $$$p^i-1$$$ is 0, then it's a multiple of 0, so the entire answer is 0.
Oh, you are right, I forgot that I need to multiply further. My apologies. Thank you for your detailed explanation, I understand now.
Does this mean that FST will happen?
What a trash round in any sight and what a trash year I've passed.
Does anyone find it strange? Where is k?
lol, in the first line of the statement they have already mentioned $$$k$$$
If you don't want to write k here, then you shouldn't explain k here.
yeah the statements are full of weirdness
Never going to compete in codeforces rounds again in 2023.
500+ downvotes in just 30 mins after the contest ended, insane
UPD: 800+ now (40 mins), let's keep going!!!
UPD: 1k+ reached in under 1 hour!
must be more after the system testing ends and many people fail on A
Well problem D managed to capture how my 2023 went. I had falshbacks while trying to find the patterns.
"Save the best for last"
I guess it did not apply this year.
Bad contest!!!!!!
I don't really mind tho, who cares about CP these days
I agree. Who cares about CP.
LOL, 1 second E is insane
bro if you are an lgm and you can't solve task c after 50 minutes of the contest when there are around 3000 solves, then maybe the issue is not with the task.
yeah the issue is def me being an lgm but why i have positive delta here
Can you please elaborate A? What does "no int32 hack case" means?
Some of the code involves taking products of all numbers in int32. If you put the factorization of above number into the input, such code will produce an invalid solution.
If this round goes rated i will never come to cf again and also will encourage people to leave codeforces
I know really think that this round should be UNRATED
i think instead of this we should post like #UNRATED THIS!
Is this the intended solution for problem E?
Calculate for all vertices number of different values $$$a_v$$$ on path to the root. We can do it using one dfs with a set.
Now we want to calculate answer for the root. Actually, for all pairs of vertices, such that their lca is root. Look at subtrees of root. Either one of the vertices is root, and other one is in subtree, or both of them are in different subtrees. So we want to know max on subtrees and out of them 2 max values.
But what if answer is not root? Go to the child of the root. Now we want to recalculate array $$$a$$$. Assume value of root is $$$x$$$. We want to do $$$-1$$$ for all vertices in subtree, if there is no vertice with value $$$x$$$ on path betreen them, and the root. So we iterate over all vertices with values $$$x$$$ in subtree and do $$$+1$$$ on that subtree. But we don't want to do it for vertices, which has another vertice with value $$$x$$$ on their path to the root. So do the following. Do euler tour. For all values calculate positions of vertices with such values. Now we do vector lower_bound on segment of subtree on value $$$x$$$. Do $$$+1$$$ on found segment (using segment tree) and jump to the end of the found segment. Do lower_bound again until end of subtree. Now we changed the root and ready to answer for this one as lca.
I think that should work but I got TLE on pretest 15 for some reason for O(nlogn) :( seems like the limit is tight. Very frustrating :|
This solution passed in 0.8s. Looks time limit is evil here. I used only vector lower_bound in "heavy" part of code and no sets and maps.
An $$$O(n \sqrt n)$$$ solution for G: (I didn't write the code and I doubt whether it can pass due to huge constant factors, but possibly this could inspire provable AC solutions?)
If the length of the resulting path $$$(u, v)$$$ is less than $$$B = \sqrt{n}$$$, the GCD along the path $$$(u, v)$$$ has to be at least $$$\frac{w_e}{B}$$$ for every edge $$$e$$$. Therefore, we can calculate the number $$$\frac{w_e}{j}$$$ for each edge $$$e$$$ and $$$j \in [1, B]$$$ and work on the connected components formed by edges containing the same number. This should be $$$O(nB)$$$ (and actually smaller than that because $$$j$$$ divides $$$w_e$$$) with careful implementation.
If the length of the resulting path $$$(u, v)$$$ is at least $$$B = \sqrt{n}$$$, consider the path $$$(u_0, v_0)$$$ that covers the middle $$$\frac{1}{3}$$$ of the path $$$(u, v)$$$. $$$(u_0, v_0)$$$ has length at least $$$\frac{1}{3}B$$$. Since we can select a vertex set $$$S$$$ of size $$$O(\frac{n}{B})$$$ from the tree such that every path of length $$$\frac{1}{3}B$$$ passes through an element of $$$S$$$, $$$(u_0, v_0)$$$ must go through a vertex in $$$S$$$, denoted by $$$w$$$. Suppose $$$\gcd(u, w) = x$$$ and $$$\gcd(w, v) = y$$$. Then, $$$\frac{x}{y}$$$ can only be one of $$$1, 2, \frac{1}{2}$$$ (or $$$(u, w)$$$ or $$$(w, v)$$$ would have a larger value than $$$(u, v)$$$). By enumerating $$$w \in S$$$ and computing the GCD over each path starting from $$$w$$$ in linear time (this might require special properties of this problem and is a bit tricky, but easy with an extra log factor), the process for finding the optimal long path $$$(u, v)$$$ can be done in $$$O(\frac{n^2}{B})$$$ time.
Disclaimer: I am strongly against setting competitive programming problems without provable (possibly aided by computer) AC solutions.
Problem A is probably the "best" problem in Codeforces. Thank you 74TrAkToR!!!!!!
It's UNBELIVEABLE that you can pass the pretests without using long long 239642528
How shit the pretests.
I think problem D is actually a nice problem.
First, solve it for small values and list all possibilities. It is a common enough step to arrive at a solution, no guessing involved.
Listing the multisets of digits which appear at least
ntimes, we get:Now, it can be seen that
n = 1is a special case. For the others, the common part is the digits1,6, and9with some zeroes. It is now within reach to explicitly construct such solutions.What you mentioned is exactly why I think it's a bad problem. It's just "find the pattern in small cases" which requires no thinking at all.
Perhaps I regard a more diverse set of activities as "thinking" then.
Anyway, we can agree to disagree on that, and move on :) .
You arent thinking. Thinking requires motivation. You are just hoping for a pattern, and you got lucky (i also did but i hate it because of that)
so you encourage guessing from just an observation? how do you prove this?
How do I prove... what? That
100...0600...09is a square of100...03and the like? The number of zeroes can be arbitrary, as long as it is the same. We just have to have no carries in the multiplication.I didn't even notice this till you mentioned it, I just saw some patterns with zeros, 1, 6, and 9, and coded something. Another reason why the problem is not as elegant as you think.
My point is this: "the problem can be solved without guessing". No more, no less.
It is also true that the problem can be solved with some guessing. That's a bit unfortunate. However, my view is that the no-guessing solution takes the same time, and has the benefit of being reliable.
You can also bruteforce the squares of $$$10^{(n-1)/2}+i$$$ for all small $$$i$$$ until you find the first such set, and store only all the relevant values of $$$i$$$ in your solution, so it doesn't exceed the submission size limit. The full solution then just does $$$O(N^2)$$$ addition and square. No need for brain.
Oh, I love when there are various approaches to a problem, like a mathematician's approach and a programmer's approach! Contestants with different backgrounds can then play to their strengths, and still solve the problem. Perhaps some would then call each other's solutions "no-brainey" and "too mathy", respectively. Okay, good for them.
What is the maximum value of $$$i$$$? I thought you will be checking too many values
$$$10^8$$$ is definitely enough, and you'll likely stop before that. Besides, your program can take 10 minutes to calculate that, and you can write another solution in the meantime.
How to become a coordinator?
change your id to 75TrAkToR
Hi.
Of course, there was an unpleasant incident with the problem today. In fact, the problem can be effortlessly googled.
You, of course, are shocked. You, of course, think that the round should be unrated.
You're
wrongright. Here's why.make this UNRATED!!!!!
Wait for system tests, if I fail something, make it unrated. If I don't, make it rated.
true!
Editorial when?
Will system testing happen today?
It may not happen this year.
Can someone provide any hints for E, I was thinking about HLD but couldn't progress further
My 2023 is just like this round.TRASH FROM BEGINNING TO END.
Problem E is really good, but the time limit is super, super tight.
I don't think E is really good. It was an extremely standard problem, I am a low master was able to find a solution in several minutes.
It would be a great problem for an Edu round, but not for the Good Bye.
Can you please explain your solution?
"Good Bye 2023" change to "RIP 2023"...
A very excellent experience of this round that literally mirrors my life in 2023: pain, sickness, bad luck and helplessness. Thank 74TrAkToR for fxxking hurting me again.
You should stop coordinating!!
true!
My great-grandmother can do better than 74TrAkToR as a tester.
marzipan path to lowest contribution :/
marzipan is not to blame
im not blaming him.... I just feel bad for him considering all the downvotes to the contest. Other than the math and the copied problem, it wasn't too bad.
The worst contest in 2023
Why the responsibility for coordinating such a crucial contest is given to somneone who has a great history in coordinating rounds
Great! Now i have to read more retarded comments and blogs of xlpg0317
If there were various issues with the contest's problems, can the system test still be started?
2023 deserved a better ending.
I wonder if this blog could actually reach a thousand downvotes. :)
The worst round I've seen in half a year, and that's 74
I need a explanation for why is 10 not a valid answer for a = 1 and b = 5 and 18 same for a = 3 and b = 9
Question B. Note: i may have misread the question or something cuz i need an actual explaination for this. like I dont get what i thought wrong first.
Because greatest divisors of $$$10$$$ are $$$2$$$ and $$$5$$$. Similarly for $$$18$$$, are $$$6$$$ and $$$9$$$.
If X was 10, a and b would be 2 and 5, not 1 and 5. If X was 18, a and b would be 6 and 9, not 3 and 9.
Because largest divisors of 10 are 2 and 5, not 1 and 5. For 18, largest divisors are 9 and 6, not 9 and 3.
for 10; 5 and 2 are the two largest factors
for 18; 9 and 6 are the two largest factors
I got a WA on Test Case 2 because of that ....
Never let him cook again
Key lesson:
Don't upvote a contest blog before the contest.
That was a very nice round Especially d , very good problem pro ❤❤
Now I understand why this round didn't get supported by NEAR.
can we attempt for hack after contest is over and if yes, how?
my solution of question A was accepted at time of contest but now showing Runtime error at test 8 why??
I guess integer overflow!
whole product will never be greater than 2023 then how??
But it got accepted at time of contest and now showing error, why??
if that was case at time of contest then I tried to solve further
that's bcuz of weak pretests
yeahh it is due to Integer Overflow, one of my friends lost it similarly :(
I did the same thing 239624846 :)
in your solution variable pro can be more than int, that's why it's RT8, try to use long long instead
But why after contest ?? ;(
Final testing isn't end yet bro
That's how it works, you can also see a disclaimer beside every problem statement that Passed Pretests doesn't ensure your solution passes System Tests and is correct..
Try this testcase
Goodbye 74TrAkToR
Round must go Unrated!!
Folks kindly chill! There has been a mistake and the host has acknowledged it. What else he can do? Most of us are here to learn something new and all of us atleast learnt something in today's contest, even if it was very small. We are not here to criticise someone, afterall mistakes do happen and its a very very very tough task to come with new problems with such high complexity. Lets not turn toxic and appreciate the positives, thats what the whole cp community is about. Nothing like all your years hardwork was dependent on this 1 contest... or is it? JUST A CONTEST!
Up, just safe critics. But we wished for a well done contest for the end of the year :(
Oh, there have been so many mistakes you probably can't even count them. Here's just a few:
my new steps for solving problems :
1-google the problem
2- put it on OEIS
3- try some random solutions
4- think
You can still skip step 4 and get the same result
Make this unrated pls
why the heck do u want it unrated ? u couldn't even solve B today
goodbye cyan, hello green
where is the excellent co-ordination mentioned in the blog?
Problem D is why I will be switching from Competitive Programming to Linguistics Olympiad.
Petition: Make round rated only for users with positive rating delta, just for new year's sake
sorry, what do you mean?
"high-quality testing and valuable advice"
Why yet not it is unrated ?
.
Let's not downgrade ratings to save the holiday vibe :)
Got FST(tle) in B on tc6. Why make such a weak pretests? Whatever solution we think of, apply it to problems like A and B. At least let us know if our solution doesn't pass the time limit!
Same here.
Same here. although the same idea passed for some participants.
you might get AC if you change the lang version.
those are the exact same code using deferent C++ versions:
AC: 239725425
TLE: 239723373
Yeah, I used int instead of int long long it's AC.
Good Bye 2023 with 2023 downvotes?
UPD 2 : surpassed 2023. Please upvote!
Can someone try to uphack my solution in E? I think that my solution is O(N^2) in worst case.
Looking at 2023, few contest where I performed good, but most of the times I struggled lot in these maths constructive problems. I hope in 2024 I reach CM
Oh hooray, now there are (at least) 3000 FSTs on A. The cherry on top.
Goodbye my rating! :D
I'm lucky I didnt attend
PieArmy orz, you would get positive delta anyway, I think! Your are good at finding patterns.
mean beard :D
LOL!
I understand that people are complaining, I don't understand why people that cannot solve E,F,G and H complain the loudest though. Should be kinda okay to make the Contest rated for Div2 only.
it's feels nice to get onto the bandwagon when you have f'ed up really bad today :sob::sob:
Admittedly alot of the time I get annoyed it is in bad faith but the large amount of complaints should hopefully ensure these issues do not happen again (especially considering the history of past contests like the one where div2c is NP-hard).
ohh absolutely. But in that case, the minus should not go to marzipan, but 74TrAkToR
that was a nice video of you eating an onion
what does onion taste like
tastes like bad
I just wanna say sorry for all the negative contrib due to traktor :skull:
Gee I love Googleforces
problem D (ChatGPT): https://mirror.codeforces.com/blog/entry/124045
problem H (oeis): https://oeis.org/A286331
got any more?
marzipan is now the most downvoted CF profile and thats just sad, since the bad quality of the round doesn't seem to be his fault
what will be answer for Problem B, if a=30 and b=210? will answer exist under problem's constraints?
this is not a valid case, as no such x would exist. the prime factors of a either have to be a subset of b, or the 2 sets(prime factors of a and prime factors of b) have to differ by at most one element. here, both these conditions are not satisfied for a and b, so they are not a valid input
70 would also be a factor
Worst D question, I wasted more than 1 hour on that problem.
2023 is NEAR
Meanwhile me who had a bad contest today watching this round get unrated:
I'll do suicide, i can't solve problem B still now, I'm a loser. i can't do anything in my life. my friends aee progressing
I'm 20 months into Codeforces and I haven't been able to solve it, don't worry You're good
Can anyone explain how to solve C please?
Consider the sum value of all numbers. If you merge two number with the same parity, the sum stays the same. If you merge two number with the opposite parity, the sum decrease by 1.
So the first player would merge the two number with the same parity (always possible) and the second would merge numbers with opposite parity (if possible). Also note that after merging two numbers you get an even number. The first player would take this advantage. He knows that the second player can decrease the sum only if there are odd numbers, so he would take two odds and merge them if possible (instead of two evens).
Now, we know that the number of odd numbers is what matters, take mod 3 of the number of the odd number (mod 3 because if the first player take two of them and the second take one of them, it would decrease by 3 after both player played).
What is the idea behind E problem?
https://mirror.codeforces.com/contest/1916/submission/239707511
This is my submission for E problem. I had just did 100 times bruteforce until I get an optimal solution. My code is wrong.. but still it gets accepted by the judge.
I wanted to know the exact approach for this E problem.. Anybody explain pls.
Also try to hack my submission . It would be a great help.
DFS the tree. From the leaves to the top, maintain the numbers of the color by using segment tree, then calc the max subtree and the second max subtree.
For a node u, we get the lowest ancester that has same color. We may calc one color for multiple times, so reduce it on the ancester. Note that we only do operations like interval +1 or interval -1, and we work O(n) times. So the complexty is O(n log n).
this is amazing! need moar tosters!
Can anybody clarify why this round is rated?
I am surprised myself. The real issues were problem F(harder solutions exist: https://loj.ac/p/3176), G(had no valid solution when the contest ran) and H(solvable with oesi: https://oeis.org/A286331)
is it rated ?
i cheese cbrt for b
It would be nice if this post reaches 2024 downvotes
Happy New Year!
Goodbye 2023!
[ Deleted ]
It seems that nobody mentioned it before, so: in problem F there is a randomized solution. 239664519. The idea is that we building random spanning tree using dfs (dfs-tree) and looking for subtrees of size n1 or n2. If such subtree found, it is the answer. Repeat the procedure for all roots ~20 times. I have no real understanding why it works. Maybe someone can hack..
I did this as well lmao
Someone did
A ....weak pretests (no overflow handling lol) B ....statement is wrong (b<x and 1<=x<=1e9) D H ....googlable G ....wrong author solution F ....stolen Very bad contest
Editorial.Please.
I used to think that 74TrAkToR is a good problem setter because of good problems in Round 905. But I was wrong!!!!!!
Wake up to check the problems I missed hours ago, only to find this... Worst Goodbye contest ever!
Worst contest ever! Make this unrated! It's okay if the contest was having small problems but the contest was delayed 2 times, the site keep using cloudfare, first 4 problem was really really bad (unimaginable) and leaked a problem that can be easily searched.
I think I should read the last few questions and OEIS them first next time.
.
IMO, problem E time constraint should've been at least 2 seconds, considering 3 * 1e5 input size.
Can anyone please tell why this solution for Problem A fails. And it got accepted without the if (multiply > 2023) condition in the for loop?
Because you are not completing the input, whenever the product goes beyond 2023. Never return something in the input loop.
Because you return in the loop too early and ended up not reading all the numbers.
Consider the case below:
Your code will treat the second 2023 as the $$$n$$$ for Case#2
you should read all the inputs in one task before output and handle next
void solve(){ int n, k; cin >> n >> k; ll multiply = 1; for (int i=0; i<n; i++){ ll temp; cin >> temp; multiply *= temp; }
if (2023 % multiply != 0){ cout << "NO" << endl; return; } else { cout << "YES" << endl; cout << (2023 / multiply) << " "; k--; while (k > 0){ cout << 1 << " "; k--; } cout << endl; }}
So where is the tutorial?
They just argue about who should publish the editorial, because that unlucky guy will have to face -3000 contribution too :)
Ah, now I understand why some contests have no editorial for long time.
Now I can see
Tutorial Good Bye 2023 (en)on the contest page. But when I click on it, I seeWhat the f*cking sh*t is it???
I think I,47TrAkToR can do better than 74TrAkToR as a tester.
Is it hard for you to create the Editorial ?
Sometimes I feel strange when I ask a question I already know its answer
So where is the tutorial?
Python users !! Can E be solved using recursion?If yes,then how and how do python users solve recursive problems as python can do only limited recursions (not enough for CP).Advise needed! look at my submissoin:my E solution
Time limit here is tight even for C++. Probably, it is impossible to get intended solution on python, which pass time limit. (However, probably, it is possible to submit something hacky.)
lets not hope hello 2024 will not be as terrifying as this
Does anyone know what is the lowest contribution on CF ever? This guy might have made a history
Since there is no editorial, can anyone explain E ? I would be very grateful.
It should be unrated. I wasted a lot of time because of this round. And...... Where is Tutoria ??? It's a bad ending of 2023.
Why is hack gets Unexpected verdict?
Everyone :-3231 downvotes
Mike : what a beautiful round ! it should be rated.
i need help?how to understand C?my idea is wrong,emmm,please give me a idea
Oh, what a magical number!
Why everyone is disapointed about this contest.If you did not know that 2023^5>10^12 then it is your problem.At minimum you can use calculator to see it.Be realistic and attentive.And I think it was good contest to see your math skills.
There were much more severe issues than '2023^5 > 10^12'
Goodbye,$$$ 2023 $$$
We hope hello 2024 be better ❤️
This round describes 2023 very well
Why did they allow such a crazy man(74TrAkToR) to be responsible for such an important contest?
oeisforces
Mathforces af
Good Bye 2023
monument to 4k. congrats!
Are you waiting for -5k to make this round unrated?
Should be rated for everyone except div1 participants imo. First 3 problems were alright.
Sure!
is this the most downvoted post ever?
Really Nice Contest.
The same situation
Same Situation as i can only solve two questions.
Why so disliked?
Why doesn't this contest have its sponsor?
Can anyone explain why this blog is so disliked please ? It's not common.
read the editorials or problems, you will see why
but still, it doesnt deserve to be the most disliked blog
I am sorry if i got something wrong in the problem, but bear with me still.
In the B problem, for the test case 8 32:
the answer according to the tutorial and what most have solved should be 128(this code was accepted), but 64 should be the correct ans, as if 128 is correct, then 64>32 hence incorrect.
Please tell me if i am wrong somewhere.