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, tibinyte, 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 (:

How?

tolbi it's even easier than that xD just A and B

it 69, i can not up vote this :((

as a tester, I can happily tell you that this round is surely one of the rounds of all time.

Congratulations to everyone on the first competition of 2024! YAY!

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

can't agree more bruhh :)

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 everyonewho participates!please read the announcements sir it is a div1+2 format round

Thank you sir!

Wow, just ended up on CodeForces, hope it'll be fun :)

I wouldn't normally expect that from a round but this is surprising truly amazing work guys.

Please open our correspondence

Hope to have fun in $$$1^{st}$$$ contest of $$$2024$$$.

It's my birthday today, hoping for a good round. Wish me luck..

kaisa gya bhai , aa gye mje

as a tester

As a tester, problems are good

As a tester, problems are good

What about "problems are bad"?

return;

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 🥶

Hi, Cars 1 is better than Cars 2 and 3.

nobody cares

I'm not sure about 2, but definetly better than 3 yes.

I agree with u, Cars2 was better

Hormat maomao90 for contributing to civil defense and protecting us from people like iLoveIOI

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 tibinyte

SpoilerSpoilerNegative Delta*

As a tester, there is a non-negative number of problems in the problemset, and at least one person will win the contest.

I hope

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 of`b`

is equale to the lowest divisor of`x`

?yep , i do also have the same doubt. someone please help bruh..

When

`b % a = 0`

, you'd know that`b = a p`

, where`p`

is the smallest prime in`x`

. Why? Let's assume that`p`

was not the smallest prime in`x`

, then`a`

(`b/p`

) would not be the second largest divisor as you'd be able to choose a smaller prime. Anyway,`b`

is only missing this one prime, so`x = b p`

.`p = b / a`

, so`x = b * b / a`

.you will find the best answer here after min 13 https://www.youtube.com/watch?v=6vbL_jd5Ghw

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

no

3amy Amrharb <3

Guys remember to not upvote the blog before the contest.

Goodbye 2023 trauma

Look how trauma transforms man.

hope this will be better than "Goodbye 2023"

Nothingcan be worse than "Good bye 2023" contestI don't want to say this but it's true

Why are people downvoting you? Didn't you say the truth?

Hope

Hello 2024!= Good Bye 2023Hoping this contest brings the coordination back on

TrAKI 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:

2024is divisible by11and23also,

2024is divisible by itssum of the digits1+1+2+3=7 thala for a reason

hope that we'll have $$$\mathtt{fun}$$$

SpoilerThe 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 :))

18o3 sir as a tester orz...:)

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

This is what happens when an unstoppable force meets an immovable object.

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

18o3 orz tester

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

2024partSpoilerit's a joke

As-Salaam-Alaikum 2024

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

moo

Do not be a second 74TrAkToR or marzipan again!

marzipan was not the problem.

How humorous! I am looking forword to participating in this round!

Hyped up by the blog !

Please provide scoring distribution

I wish 2.5 hours were 2 hours 50 minutes

I feel the contest will not be very good

Bye 2023traumacould a beginner participate this contest ?

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.

As a newbie i tried the sample interactive problem but solution was incorrect and i cannot see correct solutions of other people. Can someone please help me with this one

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 beginnerto 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 yearfor 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

omg mao zedong round orz orz orz

I don't usually love contests with 500 point for problem B

can someone help me with this question

A brave Knight "A" has an array of monsters to face, and will use a combination of might and magic to defeat as many as possible. In this challenge we'd like to know if the knight is successful at defeating them all, and if not, how many monsters are defeated. A can see the monsters and their order ahead of time. Despite being evil monsters they will politely queue and challenge A in the current order. Knowing this, A can plan what to do so that it is optimal.

The first monster will always be defeated by A's squires while A prepares for battle For each other monster there are two possibilities :

1.If the current monster is weaker than the previous one (i.e. monsters[current] < monsters[current-1]), The enemy surrenders — what goblin would face someone who has just defeated a dragon?

2.If the current monster is stronger than the previous one (i.e. monsters[current] > monsters[current-1]), then A has two options :

2.1) Might! A fights the monster taking damage (reducing hit points by the difference between the current and the previous monster). 2.2) Magic! A can drink an invulnerability potion, defeating the monster without taking damage.

Write a function that takes as initial parameters A list of monsters in order of how A will face them, with their strength as values; A’s initial hit points; A’s amount of invulnerability potions. And returns The 0-based index of the last monster A defeated.

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.

As a not tester, i can tell u this round it's much better than Goodbye2023

Happy new year frands .

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

Hope, 2024 will better perform than 2023.

I have deregistered even , I had registered for the contest

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>z, y>z$$$: Add $$$z$$$ to the set represented by the smaller number in $$$x$$$ and $$$y$$$.

$$$x>z, y<z$$$: Add $$$z$$$ to the set represented by numbers greater than $$$z$$$ in $$$x$$$ and $$$y$$$.

$$$x<z, y<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

thank you sir

kringe round it was too bad!

now why ?

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

sad for you sir!

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:

`10`

`7 4 1 6 2 3 5 8 1 9`

If we take the first subsequence as the longest non-increasing subsequence it can be

`7 6 5 1`

The other will be

`4 1 2 3 8 9`

Which has penality of

`4`

But consider this solution wich have penality of

`3`

only`1 6 3 9 8`

`7 4 2 5 1`

The first has penality of

`2`

and the second has penality of`3`

which is less than the (longest non-increasing) solution

thanks, some comments on the editorial section are talking about the correctness of this approach you can place this counter example there too

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...

Omg bro you have a long past!

problem C reminded me of my skill issue

Same goes with me ,First I tried with LDS(using binary search) then soon realised the question might not be that much complex.

I think the solution will be greedy, the basic argument is every element will either go array a or b

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

CCCCCCCCCCCCCCC!help!

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.

Got it. Thanks mate.

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?

difficult hai kya ? kya hogya

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>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>=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!

Today contest: Problems A & B is which ratings predict plz..? problem C question is kinda hard for me, I mean understanding the concept! what should I do to resolve this? also C: predict ratings? how much...

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)?

Practicing Greedy problems might help.

Practice reasoning based on "Proof by contradiction"

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:

Im failure after taking this contest :(

Even though I couldn't solve the problems, I liked the problems as they are short and nice.

Interesting contest, third problem was as easy, as it was hard.

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

Yeah. Missed that simple observation :(.I am trying to understand how recursion works. Confused how to implement this as there can be 6 cases I think?

you don't need recursion observe that in every turn total coins will decreased by 1. when will it become 0 ?

Deserves the first contest of 2024. I really enjoyed it. :) Plus, thanks for the flash-fast editorials.

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