Hello Codeforces,
We are very glad to invite you to participate in Hello 2024, which will start on Jan/06/2024 17:35 (Moscow time). You will be given 8 problems and 2.5 hours to solve them. One of the problems will be divided into two subtasks. The round will be rated for everyone. There will be at most 2024 interactive problems, so please read the guide for interactive problems before the contest.
All the problems are written and prepared by me.
Spoiler
We would like to give our sincere thanks to:
- errorgorn for his wonderful coordination!
- Alexdat2000 for translating problem statements.
- dario2994 for coming up with the solution to one of the problems.
- conqueror_of_tourist, iLoveIOI, Um_nik, oolimry, thenymphsofdelphi, Kaitokid, Brovko, Scintilla06, zengminghao, MarcosK, lanhf, beepbeepsheep, DylanSmith, kymmykym, CoDeRoK, wery0, kai824, teruel, asiad, priyanshu.p, chromate00, Blagoj, tibinyte2006, htetgm, Guevara74, Amrharb, Joshi503, BuzzyBeez, 18o3, nor, Kuroni for testing the round.
- dantoh, Myrcella, dario2994, dreamoon_love_AA, jamessngg, pavement, bensonlzl for testing a subset of the problems in 2022.
- MikeMirzayanov for the great codeforces and polygon platform.
- You for participating in the round.
The score distribution is $$$250 - 500 - 1000 - 1500 - 2250 - (1500 + 1500) - 4000 - 5000$$$.
Hope everyone will enjoy the round!
Congratulations to the winners!
Congratulations to the first solves as well!
- A: Spawnpoint
- B: tourist
- C: tourist
- D: tourist
- E: tourist
- F1: ko_osaga
- F2: ko_osaga
- G: VivaciousAubergine
- H: rainboy (after the contest)
UPD: Editorial
As a tester I went from expert to specialist during the making of this round
To make the round special?
you are my specialz
??
It is a reference to the anime "Jujutsu Kaisen". It became a meme within the anime community after the animators decided to play this song after something really tragic happened with the main character.
gambare gambare
Boo! The problems will be definitely brute force (:
as a tester, I can happily tell you that this round is surely one of the rounds of all time.
I'm 1330. Is this round too difficult? Don't wanan lose morale in the beginning of the year xD
Bruh, rating doesn't matter, I'm also 1330, And even if I lose 1100 rating I Would be happy bcuz of the experience I've gained, it's all about learning nothing more
just enjoy the problems and chill, rating doesn't matter
why do you care about rating ? If you care about rating so much you can't improve in long run , see my graph I have lost expert but giving contests will only allow me to improve faster than people who are camping in certain rank
what does this mean, will it be harder than usual ?
nothing, it is simply one of the rounds of all time
Is the difficulty closer to Div.2 or Div.3?
P.S. Anyway, good luck to everyone who participates!
please read the announcements sir it is a div1+2 format round
Thank you sir!
I wouldn't normally expect that from a round but this is surprising truly amazing work guys.
Hope to have fun in $$$1^{st}$$$ contest of $$$2024$$$.
It's my birthday today, hoping for a good round. Wish me luck..
as a tester
As a tester, problems are good
What about "problems are bad"?
waiting for this contest...
My last wish for Goodbye turned out true, so purely trying my luck, hope to become IM!
Best of luck
Missing by 2 points :(
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
Hi, Cars 1 is better than Cars 2 and 3.
I'm not sure about 2, but definetly better than 3 yes.
Hormat 🫡 maomao90 🐱 for contributing to civil defence 👮 and protecting 🙏 us from people like iLoveIOI 🥶
This is my first "Hello Year" contest.
I promise to solve at least 3 problems!
There is nothing to do with your promise... Efforts are better than promises !
As a tester, I can guarantee that this will be the best round of the first week of 2024
Lol, I can confirm that as it's the ONLY round in the first week of 2024.
I can guarantee that this will be the best "Hello" round in 2024 XD
I was forced to test.
poor tibinyte2006
Negative Delta*
As a tester, there is a non-negative number of problems in the problemset, and at least one person will win the contest.
As a iLoveIOI, peepeepoopoo
peepeepoopoo
peepeepoopoo
peepeepoopoo
peepeepoopoo
peepeepoopoo
peepeepoopoo
peepeepoopoo
Hope this contest will be good, unlike last contest :)
Scoring distribution?
Deleted
Why are people downvoting you ? Can't understand
Deleted
Hopefully there won't be any more googleable or oeisable problems in this round
coordinator diff
Can you tell me what problem(s) is(are) googleable or oeisable in Goodbye 2023(if there is any)? Are you referring to other contest instead?
H1/2 u can google/oeis.
Please, don't be mathforces this time
But math is fun...
Using algorithms is more interesting than doing math
Sry to tell you but the fact is you can't be a good algorithmic programmer without being good at math
Best problems are when math, algorithms, data structure and implementation are in balance. When it's overly biased like OEIS lookup of single number input it's not fun.
Agreed
talkig of maths, I want to ask about the last contest"bye bye 2023", problem B.
In the case where
b%a=0, why did we assume that the lowest divisor ofbis equale to the lowest divisor ofx?When
b % a = 0, you'd know thatb = a p, wherepis the smallest prime inx. Why? Let's assume thatpwas not the smallest prime inx, thena(b/p) would not be the second largest divisor as you'd be able to choose a smaller prime. Anyway,bis only missing this one prime, sox = b p.p = b / a, sox = b * b / a.Algorithms are math
But math is also a algorithm,right?
Math is Life
Tfw yet another genfuc question shows up in Div1.
Interactive problems are awesome!!!
can you tell a video where i can understand how to approach or submit such problems I haven't done that type of problems
see here https://mirror.codeforces.com/blog/entry/45307
3amy Amrharb <3
Guys remember to not upvote the blog before the contest.
Goodbye 2023 trauma
Look how trauma transforms man.
Hope Hello 2024 != Good Bye 2023
Hoping this contest brings the coordination back on TrAK
I ran some code and managed to optimise the upper bound on the number of interactive problems to $$$7$$$ from $$$2024$$$.
I'll write a formal proof of my algorithm later and edit that into this post.
I hope this round is better than before.
Fun fact: 2024 is divisible by 11 and 23
also, 2024 is divisible by its sum of the digits
The first tester tested on 10 October 2022.
Sounds more promising than Goodbye 2023.
I hope to kick off 2024 by becoming Pupil after this round.
Same
Same
You can submit 10 WAs on A and then resubmit it 100 times.
Fortunately, WA penalty doesn't do anything unless you get ac, and you can't get less than 30% of the points for a problem no matter the penalty.
Submitting 1234567891 wrong hacks should work though :))
Let's have fun in the first contest of 2024! Wishing everyone a positive delta!
It's annoying how every blog announcement has like 5 of these "positive delta" wishes, even though it is impossible for everyone to get a positive delta
Ahem, back to troll content: Good luck eveyrone! Hope you all get +200 delta in contest and reach new rank in contest!!1!!1 Hope i can reach my dream rating of 800
the last contest was "good bye rate" ... this contest going to be "hello rate" what do you think ?
goodbye 2100, hello 2000
We hope this will be better than the previous one
18o3 orz
Hello 2024
Clashing with LeetCode Biweekly. Skipping this one.
For the 69'th time, its not clashing with leetcode biweekly, leetcode biweekly is clashing with it
LC Biweekly always happens on the same day. CF contest happens randomly any day so you are wrong
Consistency of timings is not a measure of quality, if anything it is the reverse since the round nust happen even if the problems are not up to the mark
"codechef starters = bad" ~ codechef admin
I mean, nowadays cf rounds being scheduled before being ready xD, seemz like an universal problem
"ICPC = bad"
Yes sir, no doubt about that, +1
I feel like LC has better quality questions than CF. Most of CF rounds are Mathforces af like Good Bye 2023
you are delusional, LC has the worst questions known to mankind, practically every single problem is stupid and standard and well known
This has 69 upvotes. It's too perfect.
Just solve LeetCode Biweekly in 5 minutes
I aint that gud. Will Solve LC in an hour and then on to CF
There will be at most 2024 interactive problems — what does it mean?
This means that there may be interaction problems in this round, and that you will need to learn how to deal with these kinds of problems ahead of time.
i got it, but i am confused about 2024 part
it's a joke
Hopefully, I was able to solve first 4 problems!
as a noob ,I hope I can solve problem 1 within 1 minute and not get hacked
As a tester problems are good...but I'm not a tester
How humorous! I am looking forword to participating in this round!
Please provide scoring distribution
I wish 2.5 hours were 2 hours 50 minutes
I feel the contest will not be very good
Can the Python be used while solving in here?
You can solve with any language that can be used to solve a problem in the problemset (Including python).
But I wouldn't recommend using it as it's much slower than c++, you may need to further optimize your solutions in order to pass the tests.
If you are planning to use Python submit using PyPy instead of Python which is usually much faster.
For very early problems definitely. In harder problems, especially with more complex implementation, you can run into TLE, but at that point learning to code in a suitable language isn't the hardest part.
Hope it can make me excited instead of the frustrating "Good Bye 2023".
74TrAkToR won't be the coordinator of this contest. Yay!
С пасхой!
Guys, I am a complete beginner to programming. I have started learning basics of C++ from sololearn.com. If there is anyone who is hearing me, who is candidate master or master. Please can you help me? I want guidance for CP.
I want to dedicate 1 year for doing CP full time. I want to utilize this time to get maximum output.
Thank you.
Auto comment: topic has been updated by maomao90 (previous revision, new revision, compare).
i can not wait to start it!!!
I hope this contest has the opposite number of votes as Goodbye 2023.
I hope I can solve the first 3 problems
will we see "happy new year" instead of "accepted" in this round?
MikeMirzayanov
Hope this time I can finish at least 5 problems.
Hope to become CM this round!!!
I hope for a positive delta
I wish it's somehow better than Gb2023 lol
That bar is so low you could use it to play limbo.
IMO first ever CF round would have been better that Gb2023. At least people might have learnt about maybe Dijktra or knapsack rather than just coding math operations without understanding significance.
Wish a good perf and an enjoyable round.
how does score of questions related to our rating
It does not
Geothermal will win codeforces round Hello 2024
Will OEIS will be helpful in this round also? :P
ImbalanceForces
is time limit for C too tight ?
if not, please share the approach after the completion of the round.
Greedily considering this problem. We set the last number in sets $$$a$$$ and $$$b$$$ to $$$x$$$, $$$y$$$ (where $$$x$$$ and $$$y$$$ are the maximum values initially).
Assuming we add the number $$$z$$$ to the set:
$$$x \gt z, y \gt z$$$: Add $$$z$$$ to the set represented by the smaller number in $$$x$$$ and $$$y$$$.
$$$x \gt z, y \lt z$$$: Add $$$z$$$ to the set represented by numbers greater than $$$z$$$ in $$$x$$$ and $$$y$$$.
$$$x \lt z, y \lt z$$$: Add $$$z$$$ to the set represented by the smaller number in $$$x$$$ and $$$y$$$.
Then we solved the problem within the complexity of $$$O(n)$$$.
submission link
kringe round it was too bad!
unable to solve C,i better not be a retard
Every contest should be unrated when "YOU" can't solve problem C.
Nice JOKE.
I think you miss read the comment
...
I think that its about calculating the longest ( non increasing subsequence) but I couldn't figure out an approach except for the n^2 one
There's an nlogn way to find LIS, but it's not required for the problem. I solved this by greedy
C is not about LIS. But LIS is solvable in o(NlogN). I tried really hard though, to prove LIS way of solving C, but i can't. This sort of problem is really pain in the ass i gotta say.
I made a mistake I meant to say (Longest Non-Increasing Subsequence) not LIS
did you try to calculate that and it gives you WA too ?
yes it gives WA
I don't think calculating the longest non increasing subsequence is the right approach as there are multiple possible such sequences and it is not necessary that all of them will give the same penalty
apologies.
Prove_with_ACforce
Disprove_with_WAforces for me ;-;
I've participated in codeforces contests for 7 years, and I still can't solve Div2C. I don't know how much I've progressed in past 3-4 years. Maybe its time for me to quit this game now.
kinda comforting to see even gms struggle on greedies XD
Didn't know that greedy troubles not only me but GMs also
C was nice. I love it when I prove a solution during the contest
it was about finding the ( Longest Non-Increasing Subsequence) right ?
No, just try to start with the end. Then, you can compare each new item with the last added item in each of the two subsequences
The rest is casework
ok thanks, but can it be solved if we found the longest non-increasing subsequence?
the (Longest Non-Increasing Subsequence) penalty will be 0 and then we calculate the penalty of the remaining numbers in the set. do you think that this is a valid Solution?
You mean the longest non-increasing subsequese which will give us penality 0, right?
yes , I'm sorry
No worries!
The longest non-increasing subsequence will not work
Consider this test case:
107 4 1 6 2 3 5 8 1 9If we take the first subsequence as the longest non-increasing subsequence it can be
7 6 5 1The other will be
4 1 2 3 8 9Which has penality of
4But consider this solution wich have penality of
3only1 6 3 9 87 4 2 5 1The first has penality of
2and the second has penality of3which is less than the (longest non-increasing) solution
No it will be 7 6 5 1
4 1 2 3 9 8 This will have penatly 3.
u interchanged them.
I know LDS wont work because you can take this sequence :
27 28 29 100 99 98 97 96 20 19 18 30 27
When by LDS
100 99 98 97 20 19 18
27 28 29 30 27
The penalty :3
The better would be 100 99 98 97 96 30 27
27 28 29 20 19 18
Penalty :2
Yes, you are correct I changed the two numbers while testing
Thanks for clarifying
Goodbye, 2024.
I tried so hard to solve C. I tried varies of approaches to deal with it, but still failed. But I didn't give up. I tried to drew a lot of examples, tried to use dp, binary search, ternary search, graph, extended euclidean, ford fulkerson algorithm, .... And finally, I realised that I still unable to solve C.
Kind of the same... Sent 2.5 different solutions and tried maybe 5 approaches and all WA 2
UPD: actually I had correct idea but just initialised arrays wrong... Now I am specialist for the first time since 2014...
problem C reminded me of my skill issue
wow what IS d? new year, new pain
I found out that if x is the biggest element must have a brother that's equal to x-1 (both leaves). From that i think you can delete those two elements from the array and substitute them with their father (that has value of x-1) and solve again. I tried this with some data structures (double linked list and priority queues, very ugly) but got WA on pretest 2. I spent like 1.5 h on this :(
"I found out that if x is the biggest element must have a brother that's equal to x-1 (both leaves)."
I guess, not "x is the biggest", but x is the deepest.
if x is biggest, then it won't have children. Though this doesn't mean it will have a leaf brother, at least one maximum should have a brother that's a leaf. Maybe it becomes a problem if there's two possible brothers, i'm not sure if both choices lead to a tree or not
I saw that too, but what if X has both neighbors equal to X-1? Which one do you merge it with? What if it has one or both neighbors equal to X? I didn't really see any breakthrough in this line of thought
WOW I fucking misread the statement. I thought we could freely color the edges 0 or 1, turns out one edge HAS to be 0, and one edge HAS to be 1 for each non-leaf. I'm going to kms
If you do this until you can't:
The result will be a tree, not necessarily binary. The Dfs over leaves is now equivalent to dfs in tree, but with one tweak. We need to decide after which children (or it's possible at the beginning) we insert the inner node into dfs_order. Everything is possible, which means if (e.g.) choose the root, then there will some subtrees dfs_order concatenated on the left, and some subtrees dfs_order concatenated on the right. This can be checked with RMQ and recursion, but instead of deciding where to break the concatenated blocks in the root, we will decide them in the children. So at the end we need to check if the root is unique.
240558002
(oh i see you misread but maybe this will be helpful to someone else)
In that case if you have [... x-1, x, x-1, ...], then you merge any neighbor to x and always get [... x-1, x-1, ...]. Anyways this is the editorial sol
i did exact same thing and 5 minutes after the contest i realised, that there must stay only 1 element and it must be equal to 0, otherwise it's a "NO".
240601323
is problem c dp?
No, you could just greedily decide whether to put the ith element in set a or b.
I did that only but couldn't pass pretests... what's wrong with it https://mirror.codeforces.com/contest/1919/submission/240551011
Consider you are trying to add 20 to one of your arrays. Array a.back() is 50, and array b.back() is 30. It is better to add 20 to the back of array b because the 50 may be more useful in the future.
is D DSU?
Yea, I did a DSU based solution; however, something like linked lists might be easier to implement
Nothing to see here guys, certainly not E but like, in O(N) or anything
Wow, I came up with the same solution without realizing that the complexity becomes linear if done recursively.
Really nice problem D! A bit hard for its position though?
What's the idea for D?
Firstly, there must be only one $$$0$$$ in a valid sequence. Next, give some examples on the draft paper. You will find that if $$$x (x \gt 0)$$$ appears in the sequence, then $$$x-1$$$ must have appeared.
Let $$$x$$$ be at position $$$t$$$. Combined with the drawing, it can be found that $$$t$$$ must be within a interval $$$(l, r)$$$, satisfying the conditions of $$$\forall i \in (l, t) \cup (t, r), a_ i \gt =x$$$, and $$$a_l=x-1 \vee a_r=x-1$$$.
I'm not very good at expressing its proof in words, sorry!
Finally, we use dfs and binary search to solve this problem. Pass three parameters $$$l, r, x$$$ into the dfs function, representing the current interval $$$[l, r]$$$ and the value $$$x$$$. Record the position of each value in the array $$$t$$$, find the value $$$x-1$$$ in the interval $$$[l, r]$$$, split the entire interval into several small intervals, and recursively solve the problem.
Happy New Year!
Here are some examples as a reference:
Additionally, if you use bfs instead of dfs, some optimizations can achieve $$$O(n)$$$ complexity!
The webpage lag 15 minutes after the start of the competition caused me a lot of trouble.
Anyway, the problems all look interesting, thanks!
problem d is interesting but so hard, didn't solve :(
$$$\frac{Div. 3 \ + \ Div. 1}{2} \neq Div. 2$$$
great contest but did not manage to perform as expected !!
C had some good observation
How to practice for problems like C (guessable but not trivial greedy problems)?
Accidentally submitted F2 to F1 & got -350 score...
Great contest! Thanks.
Hello 2024 != Good bye 2023
Wow, it was such quickforces. My last accepted submission was on 0:11 .
My ideas to D:
Even though I couldn't solve the problems, I liked the problems as they are short and nice.
Accepted/Tried
How brutal the C test is. (The pretest btw)
thats better than having FST :(
cloudflare is SHIT
Now I know how difficult to welcome the new year is.
I wonder how many people proved solution of C.
welcome to codeforces
In my opinion, high-level coders will prove this because they can demonstrate it almost instantly.
The proof of this problem is a typical one. Consider iterating from 1 to n. Suppose the current two subsequences end with a and b, assuming a <= b. Suppose the current number is x. Consider two cases:
You put x after a number greater than or equal to it. In this case, if both a and b are greater than x, choose a. Otherwise, choose b.
You put x after a smaller number. In this case, it will choose to put x after a.
We consider that if we can make two choices in the current step, it must hold a < x <= b. If we choose 2, it becomes x, b, and penalty++. If we choose 1, it becomes x, a. We can imagine that the penalty is like a free ticket, which can change any number into INF at any time (including changing a into INF instantly), so 'a' with one less penalty is strictly better than 'b' with one more penalty.
I don't know how others did this problem, but I only realized the answer to this problem after the proof.
Proof by AC is the most powerful method
Didn't really prove it, but my reasoning went kind of like this. There's no real reason to take a penalty if not strictly necessary. If i raise one of the two sequences when not required I might also have done this later for the same cost. Then I just thought about how to keep a good state and figured out the best greedy moves after some tries. Then i proved by AC.
Proof is a big word, but having an idea what you're doing is good enough usually
More and more vegetables,what should I do?
cower than me
First two problems were satisfying. Solutions are short and pretty
Is F1 difference + segment tree?
E seems classic, but I can't solve it. How to solve E? QAQ ~
240509224 240515600
Identified and rectified a discrepancy in Problem A submissions; both versions passed the pretests and shared the same logic. However, there was a point reduction of 50 points. :"(
Someone Kindly share the solution of A using recursion. Thanks.
u can just solve it through if a + b is an odd or not
you don't need recursion observe that in every turn total coins will decreased by 1. when will it become 0 ?
C was the hardest problem of all time
Why do I perform well in shxt rounds and brick the good rounds, weird
spent 1h writing F for nothing
For every non-leaf vertex, one of the edges to its children has weight 0 while the other edge has weight 1.
I forgot about this restriction while solving D, a sample in which this makes any difference would have helped so much :(
2024 is already ruined for me after this contest. 2025 will be my year!
great problems, enjoyed a lot! kudos to the author(s)
Feedback on the round:
A: Fine easy problem.
B: Good problem conceptually. I personally would have preferred for the entire sentence "Note that there are no constraints on the sum of n over all test cases." to be bolded, which would have made the fact that O(n^2) solutions are not intended to pass more obvious.
C: Good problem; I've seen the general greedy strategy used as part of other problems before, but it serves reasonably well as a standalone C.
D: Nice problem; simple idea and the implementation isn't too bad.
E: I don't think this problem is objectively bad, but stylistically it isn't my favorite. Most of time time I spent solving it involved working out details rather than coming up with the general idea. Also, a (somewhat harder) version appeared as ARC 146 E (thanks to AC server for pointing this out).
F: Good problem. I prefer DS problems like this one where the data structures part can be handled mostly by copying a standard template, but writing the merge function itself requires a little more thought. Amusingly, I didn't come up with the idea for F1 before solving F2 and I didn't think about the flow idea given in the editorial while solving F2.
G: Great problem. This problem particularly improved my contest experience because it's the kind of problem where even if you don't end up at a solution, you can at least make reasonable progress throughout the time you have left in the round. In my case, I think I was very close to a solution, but unfortunately I hadn't finished working out all the edge cases or implementing the XOR hashing idea.
H: Didn't seriously attempt.
Aside from the fact that problem E had been used before (which empirically didn't seem to affect the standings much, if at all, and would have been hard to Google anyway), the round seemed very successful--the problems were interesting and the contest was prepared well (there seemed to be very few FSTs, there were minimal server issues during the round, and systesting started/the editorial was posted quickly after the end of the round). Thanks to the author and the coordinator!
Thank you for the contest.
Ended with positive delta, now starting with positive.
2300, recorded.
Really great contest enjoyed it altough solved till C but got me to specialist Nice
special thanks to the testers and coordinators for creating such an amazing contest
Wish I could have solved D and F1.
Awesome problems
@maomao90 Thank you for the great contest!! Enjoyed it a lot. Lots of DSA involved. LinkedList, Priority Queue, DP, Segment tree, Flow, Min Cut, Segment tree.
problem C is too greed!
Bad contest.... AB are quite good, but D's conclusion is too hard to think(the implementation is easy, though). Also, C's greedy is hard to prove. The other problems are not bad, but there's no time for me to solve them as ABCD cost me the whole time.
And, why editorial isn't available now?
Tree LGM -> Three LGM
I keep getting WA3 in F1 using a segment tree. Can anyone please advise, what might be the problem? code here Thanks :)
Take a look at Ticket 17229 from CF Stress for a counter example.
Can you help me with failed testcase 241324677 Thanks
Why H is only 2000?
Great round