Hi, Codeforces! Happy New Year!

I'm glad to invite you to Hello 2022, which will take place on Jan/03/2022 17:35 (Moscow time). You will have **$$$2$$$ hours $$$15$$$ minutes** to solve the problems. **This round is rated for everyone.**

All problems are authored by me. I would like to thank 74TrAkToR for excellent round coordination and MikeMirzayanov for great Codeforces and Polygon.

- Thanks to isaf27, budalnik, MichsSS, TadijaSebez, ijxjdjd, Um_nik, flamestorm, ashmelev, Monogon, errorgorn, Mr.Robot_28, AlexLuchianov, Kirill22, Prokhor08, romanasa, Dragonado, marzipan, magnus.hegdahl, olyazyryanova, DIvanCode, plagues, wxhtzdy, voventa, DanShaders, ptd, PurpleCrayon, stevancv for testing the round and giving valuable feedback.
- Thanks to Kapt, MForest for discussing some of the problems before the proposal with me.

There can be an interactive problem in this round. Don't forget to read the guide on interactive problems.

The scoring is $$$500-1000-1500-1750-2250-2750-3000-3500-4500$$$.

Good luck!

Thank you for participation! Congratulations to the winners:

Happy new year

cout << Happy new year & Happy coding << endl;

sorry

That's life to u my friend

Syntax is still fucked up even if it was declared in that scope.

its sarcasm bro

Happy new year to everyone!

cout << Happy new year & Happy coding << endl;

Hello and happy new year to you too but encase it in double inverted commas as it is a string and using cout without fast i/o is not preferred by good competitive programmers ,if you don't wanna use fast i/o ,use printf instead .I guess that's the reason you were downvoted massively .

UPD: Sorry i missed one more point ,you are using endl which is too slow as well ,use \n instead for your wishes to reach people as soon as possible

Happy new year everyone and wish you happiness!

Fun factThe number of solved problems by IgorI is 2022

Another fun factAt 31th December

2021, he had2021submissions, and he submitted another one today (1st January2022), which makes2022submissions in total.Another fun factHe actually submitted once per year. He has been doing this for

2022years now.This is 2023 times, the world started at year 0.

Actually according to the Gregorian calendar, it didn't. The year before 1 AD was 1 BC.

time went very fast now we are in 2030

Happy new year and hope a wonderful round!

Happy new year!

Happy New Year Everyone!

Hoping to break out of grey this year : D

Me too! We can do it!

me too

HAPPY NEW YEARLet's start this year with positive hopesHappy new year!!!Happy New Year

Happy new year everyone, hope this 1st contest of the year brings more positive delta.

Happy New Year! May everyone have positive deltas in this round!

Is it even mathematically possible?

Maybe it's impossible, this blog says that "Choose a group of the most rated (before the round) participants and decide that their total rating shouldn’t change."

Happy new year everyone. Hope for a great year ahead.

Good luck to all competing!

cout << Happy new year & Happy coding << endl;

Unfortunately ur red colour is also not helping u in upvotes

If you are shining and you will give some shine to others then, you will not lose your shining.

It doesn't work that way with contribution boi

cout << "With best wishes for A HAPPY NEW YEAR!\n";

cout << "Wish you all positive deltas in the competition!\n";

endl is too slow, use '\n' instead if you want to send wishes :)

Yeah, i got tle once due to endl;

Happy New Yearand I hope everybody will have a great year and get what they want =)))

Good luck for the 1st contest in this year.

Any guesses on the amount of problems?

sekrit as usual

Happy New Year! I didn't make any new resolution this year (previous years resolutions yet to complete)

Happy new year!

as a dark reader user i hate the snow in the background

You might want to try this.

Happy new year！

Hope my first contest will be wonderful!

Happy New Year for everyone

Happy new year..I hope everyone have positive deltas in this round!!

Happy New Year everyone!

Happy New Year!

Happy New Year everyone! Let's gain rating in the first contest of the year)

Happy New Year everyone!

Happy new year everyone!

Happy New Year Everyone!

How many problems will be there ?

I'm excited for contest

Happy New Year! The amount of testers makes me sure that the first round of the year will be a good one.

Happy New year Everyone! (✿◠‿◠)I like your anime a lot (＾▽＾) Good luck and have fun!Glad you liked it, season-2 drops April 2022! ヾ(≧▽≦*)oHappy new year

Score distribution ?

What are the degree of difficulty by the contest?

I am very excited for this round. !!

Getting back to giving contests regularly after a long time. (part of my new year resolution). All the best to everyone and me xD.

Codeforces comeback? There weren't any contest for the year!

happy new year all.

|is this contest suitable for div3's people?

this contest is suitable for all.

thx :)

2022!

Why 9 problems in 2:15 and not in 3 hours?

I think that will be 2 problems interactive (2 versions)

Verdict : Prediction failed

I will try hard in next time

There are still more than 35 minutes left to register and the registration count is already above 24k... Seems to be like that the community is taking new year resolutions seriously... Happy to see this happening :-)

.

Prediction: WA on system testing

7 participants from top-6

MikeMirzayanov, I know that this is not the right place to write this but the false positive against my solution for Problem A of Goodbye 2021 still hasn't been reverted. I haven't even got any reply from the headquarters whether my appeal has been rejected or not. I want to participate in this contest but I can't unless this matter is resolved.

You cheated before. I have neither the time nor the desire to delve into the situation this time. You have exhausted your credit of confidence.

For example, in Codeforces Round 700 (Div. 2):

I have already accepted in my previous blog that I used two accounts for Codeforces Round #700 and I accepted all penalties for it without questioning. And as I promised in the blog, I stopped using my account Need_For_Sleep_MW. That round was the first and the last time I did something like that.

I understand that it is hard for you and the community to believe me but all I want to convey to the community through this message is that I have never copied someone else's solution, nor provided anyone my solution during a contest.

Thank you for the great platform and the community which helped me learn a lot of things and improve my skills. I hope I will not disturb you again.

I registered for the contest but I am unable to submit my code as it says that I have not been registered.

TOO LONG statements and quite bad experience on prob B

What was the approach in Problem B?

some kind of sorting + set (I did so)

It is some case work.

We want to buy the cheapest segment with min L, and the cheapest segment with max R. But we need to consider the extra case that one segment covers the whole range, ie has minL and maxR.

Let $$$lx$$$ be the smallest $$$l$$$ and $$$rx$$$ be the biggest $$$r$$$ from $$$1$$$ to $$$i$$$. Then you have three options:

Take segment $$$[lx, rx]$$$ if such exists (type 1).

Take the cheapest segment that starts at $$$lx$$$ (type 2), take the cheapest segment that ends at $$$rx$$$ (type 3).

Let's store the indices of the cheapest segments of types 2 and 3 in variables left_seg and right_seg respectively. When you find a segment with $$$l$$$ less than $$$lx$$$ or with $$$l = lx$$$ and less cost, reset the answer, update left_seg and of course $$$lx$$$ itself. Do the similar thing with $$$rx$$$. When you find a segment of type 1, try to improve the answer with its cost.

Implementation (probably even clearer than my words above):

ImplementationI hate English reading contest.

Back to IM.

long statement + very tough contest :(

After struggling for around 1 hour on problem D, I conclude that it is undoable for me ;_;

After watching editorial, I feel stupid ;_;

After stopping for about two years, jqdai0815 participates in today's contest, Welcome back!

i dont agree with this blog

Early congratulations to Gennady Korotkevich for the 1st to reach 3.9k! (hopefully...)

I'm sorry! This B let me goodbye 2022...

Hello 2022(X

Hell 2022(O

Sorry!

I don't have any idea why you get WR in PreTest 1.

but you code get WR in this case :

Test1

3

1 5 3

1 5 2

5 8 20

Problem B ate me

constraint in D so low why

Problem B did me psychopath

I usually never criticize contests, but

not-lighthearted memeI can't tell if D is either extremely standard DP problem or some extremely cute simple solution, can I get a hint?

Edit: Bruh I literally just realized that I forgot to account for half of the cases (extreme corners and the two top left corners of the (n/2)x(n/2) blocks not on the main diagonal. I'm so sad wtf ;-;

Extremely cute simple :)

I think the intended solution is DP based which is why constraint is so low (n<=250)

I stuck in D for a long time ...

Where can I find the editorial for Hello 2022 Contest?

B is an abomination. E is just boring implementation, too standard for its place.

F also seems like greedy casework. A, C are okay. D is nice.

I think the problem setters should focus on how to improve the skill of contestants of all levels. Not only differentiate winners and losers in a random way.

Only if I knew that the interactive problem would be pre-D prior to the contest.

Anyone else who thought problem C that, q initially identical as p, and waste a lot of time on it?

After this contest, I don't think I should have high hopes with 2022....

please explain the test case 4 in problem 4, I am still getting 44.

The persons can also move out of the grid and enter on the opposite side.

ohhkk, thanks

can you find a way to move such that at every stage every friend remains in one of below positions ?

{a[i][j]: 1<=i,j<=n} U a[1][n+1] U {a[n+i][n+j]: 1<=i,j<=n}

How to solve C?

In a permutation the numbers on the position form a circular list. The movement after each ask moves the number by one position within these circular lists. That means, by asking repeadetly one position we can get all numbers in that cirlce in the order they are in that circle. So resolve all circles.

For me it was a implementation nightmare, did not get it right for like 1 and a half hours.

Hint7 6 1 3 2 5 4

4 5 7 1 6 2 3

3 2 4 7 5 6 1

1 6 3 4 2 5 7

7 5 1 3 6 2 4

4 2 7 1 5 6 3

3 6 4 7 2 5 1

u will notice one thing that there are two individual cycles in this permutation after we have done some operations

Basically, we are given a kind of loop between which elements of the permutation q can rotate. e.g. if the original permutation was 4 3 5 6 2 7 1 ;we have the following rotation for q :

In each step : q1->q4->q6->q7->q1 and q2->q3->q5->q2 .

So, just keep iterating at any index whose value in the original permuation is not yet known and keep assigning the obtained value to the preceeding value/index till you reach the start of the loop again i.e. encounter a value twice. Then move to the next unknown index and repeat the process.

I'd like to think of the solution as: Query the same position twice. The first answer gives you the

`address`

and the second answer gives you the`data`

. You can then fill in the array likeNow, you will have to sometimes reset the address to a new unexplored one by using previous

`data`

as address or using a new address to fill in the rest of the array.Is it just me , or problem B even is getting tougher these days

seems so

How to solve F?

E was so boring.

I hate

`Problem B`

(:Are you serious? cyclic permutations + interactiveness for C! Meh Man!!

Imagine getting penalty (and time penalty because I doubted my solution) for D because of this:

`#define INF 999999999`

Hi,pls help me to debug where I am doing wrong in the code : https://codeforces.com/contest/1621/submission/141566448

try this Case :

Test1

2

1 5 2

1 5 3

why this is wa? problem A- 141506189

Why You don't set any initial Value for the array?

ArrayAC Code : 141571522

Happy Wrong answer on test case 2!!

After giving this contest, I have a feeling that my 2022 won't be going well either.

im pretty curious why im getting WA for 2nd case problem B !

The most terrible Problem B I've ever seen...

You are right. And I think

Problem Dwhich you only spent3 minsolving is much easier.Actually I've wrote a code for D at about 1:20 that I think it'll probably FST and, after solving E, I decided to submit it. That's why "3 minutes to solve D" exists.

Was it really intentional to make first contest of 2022 so hard?

Imagine how much better this contest could have been if F was just deleted

B

is it sarcastic ? was only F good ?

F was terrible imo.

Imagine how much better this year would have been if this contest was just deleted

What exactly is wrong with F?

In my opinion, this round was one of the worst in recent memory.

AB were not interesting, but it's hard to have interesting div2AB for a combined round, so I'll give them a pass.

In C, I'm sure there is a clean solution, but I immediately saw one solution, and had to spend a very long time making sure my indexing was correct. Also, in this problem it is hard to simulate the grader by hand, so I didn't even know if my solution would pass sample 1. I Think this problem would have been better if Q was always the identity permutation.

EDIT: turns out q at the start is always the identity permutation, and I just missed that part of the statement. As I stated above, my solution made no assumptions about what q initially is, which makes the problem much trickier to do. Please bold all important details in the future!

D is a one-observation problem. The observation is nice, but in my opinion this kind of problems shouldn't appear in a competitive programming contest. I most likely would never have been able to solve D if someone showed it to me and claimed it is very hard. Because so many people solved it, I just guessed random simple strategies until one worked. This kind of solving process is not fun.

In both E and F, you can immediately see a solution, but need to handle many cases to make sure your solution works on all inputs. Also, in both problems, the given sample is very weak, and covered less than half of the cases I had. I'm sure you have nice solutions to these problems, but if the optimal strategy to solve the problem is to just write tons of casework, it doesn't matter, it's a bad problem.

I did not get to problems after F, but at least from what I heard from others, G is not nice either.

I think D is very cool. I had full knowledge why the required algorithm is correct once the idea came to my mind (you need to move some corner at some point and any of these 8 cells suffices). I don't buy arguments "not suitable for a competition, because there is a cute observation constituting short solution", especially if it is not much harder to prove the correctness than to come up with the idea for the algorithm

G is very cool as well

But I agree with the criticism of ABCEF

I think D is boring too. That being said, I would have forgiven D in a contest where the other problems were better.

I completely agree with your sentiment on D. I started off with an unproven solution (mainly because it was a D) before actually thinking about its correctness. While the idea is cute, I can totally see myself get stuck with it on another day and it would be extremely demoralizing in such scenario.

I don't think E is bad though. It's a bit too standard and perhaps it's meant to compensate for D. Your approach is probably different from the intended one.

First thank you to the author, I know it is a hard job preparing a full round.

Then, I would like to say that I did not enjoy the round. Partially because I am weak and I spent a huge amount of time on D (which I misread) and E (implementing) so I could not reach harder problems. But it is not only my fault:

greedy. The first impression after reading it is "Ok, here we have to remove the short gaps as fast as possible and split in a gazillion cases". I did not get accepted (started implementing) in the contest and I have not read the editorial, so I might be very wrong, if that is the case I am sorry.On the other hand, problem D was a nice tricky problem.

B and C is probably obvious to most red coders, but I think it's a great problem for their target audience. It is approchable, has some educational value, while requiring some thinking and implementation. And it is not "yet another math puzzle".

D was a funny problem. I think the problem itself is not hard, but the limit being $$$250$$$ and the problem being in D made me feel nervous about my solution.

This really shouldn't have been the first contest of 2022 :(

F is such a terrible problem, stop creating problems like that.

mathforces

man there was 1 math problem, and thats if youre liberal in the definition of math

I guess in light of all the negatives everyone else mentioned, I thought problem G was a kind of cute DS problem, and my final implementation (that I just needed like 1 more min to debug in contest :sob:) ended up being relatively clean. A shame that it was buried in the back because CF logic seems to dictates that any problem with a range query is automatically harder than an ad hoc problem, no matter how difficult the ad hoc.

At least the author hasn't formulated problem B on the grid

Didn't solve B because I was using $$$>$$$ instead of $$$\geq$$$.

Now I found out I FSTd on C because due to a basic out-of-bounds issue

sed life

Why is this contest so short? It is not some Anton round where every problem has a short solution.

+1054 delta when his rating is 3681 lol

inspect?

nope, you can check here. His seed was zero, because he has not competed in >= 6 months, but still interesting to see +1000 delta

Oh, I use a carrot[extension] and it showed me -76.

No surprise in decreasing likes after contest (600->500). It was made for candidates and higher, not for ordinary folks, no Hello for them.

Is this div1 or div2?

Thanks for the contest, I enjoyed it!

A: fine easy problem.

B: I find it a bit interesting — even though it's just problem B — that it's possible to maintain the smallest $$$l_i$$$ and the largest $$$r_i$$$ on the prefix, along with the smallest costs of segments containing $$$l_{min}$$$, $$$r_{max}$$$, and both. Harder than an average B.

C: you can just find each cycle in $$$length + 1$$$ queries.

D: $$$8$$$ cells touch both $$$n \times n$$$ squares, and you need to clean at least one of them, otherwise you can't move friends from the corners of the original $$$n \times n$$$ square anywhere. At the same time, cleaning any of those $$$8$$$ cells is enough to move

allfriends to the destination. Definitely an interesting idea.E: probably other solutions exist that use the structure of our queries. However, the somewhat standard idea "a matching exists $$$\iff$$$ for any $$$x$$$, $$$cnt_{teachers \ge x} - cnt_{groups \ge x} \ge 0$$$" along with a segment tree for range add and min does the trick.

F: basically just greedy simulation. There are four types of moves on $$$0$$$'s: replace $$$00$$$ with $$$0$$$ in an inner group, replace $$$00$$$ with $$$0$$$ in an outer group, remove $$$0$$$ from an inner group, remove $$$0$$$ from an outer group. The moves should be prioritized in this exact order, unless there are no $$$11$$$'s left, in which case you either replace any $$$00$$$ with $$$0$$$ and stop, or remove $$$0$$$ from an inner group and continue. It also follows that replacing $$$00$$$ with $$$0$$$ should always be done in the shortest group of $$$0$$$'s possible. Overall, this problem is fine. If your approach is more complex and you get stuck in the details, obviously you feel sad, but I believe my solution is reasonably simple.

G: a nice problem, did not seem approachable at first because it's hard to count increasing sequences containing

twoelements at the same time, but it turned out to be possible due to the structure of these pairs of elements.H: looked hard initially, and I was pretty sure it would take a bunch of data structures to get through it. However, my final solution uses nothing except a single DFS, which is cool!

I: I think I can prove that after $$$O(\log n)$$$ iterations of $$$op()$$$ the array stops changing, but I could not figure out how to evaluate one $$$op()$$$ in $$$o(n^2)$$$.

tourist orz

He is just a genius

Nice solution to F!

Can anyone explain me where my logic for the 2nd question went wrong?? I was stuck on it for almost the entire contest duration Link: https://codeforces.com/contest/1621/submission/141560841

The variable names are so similar even the compiler got confused, I guess.

Input1 3 1 2 2 2 3 2 1 3 3

Your Code Output2 4 4

Correct Output2 4 3

Seeing problem D in that place makes me immediately think of much more complicated approaches. I mean If I encountered this problem in div2-B I would've solved it in no time. This is a bad mentality I know.

But I do believe it's much easier than C, and after spending around 1 hour in C I did expect D to be much harder which was so annoying to see such a naive solution.

Yeah, completely agree.

For problem D,

Shouldn't the answer for this case be 9? From what I've seen the expected answer is 14

Try to rotate all your friends through your 9 cost path without stepping onto snowheaps. E.g. friends (3,1) and (3,3).

If you want to move only through zeros,

~~you can move 2 columns from top-left to 2 consecutive rows in bottom-right~~. But you will not be able to move the $$$3^{rd}$$$ column. Remember that the whole column/row moves not only specific ones within it.EDIT:You will not even be able to move a $$$2^{nd}$$$ column from the top-left $$$n \times n$$$ square, as moving it will result in moving the $$$3^{rd}$$$ column to one of the columns with cost $$$5$$$'s.ProblemB,can anyone tell what might be the error. What i did is i maintain lowest integer and the minimum cost for such segment. And the highest integer and minimum cost for such segment. I also maintained fans variable which considers single segment case. If single segment not possible then sum of cost of lowest integer and highest integer will be the answer. Here is the code link. https://codeforces.com/contest/1621/submission/141533792

Try this test:

Test1

5

1 2 8

1 9 10

4 5 6

9 10 6

1 10 16

Your output8

8

8

14

14

Expected8

10

10

14

14

Will be very thankful if someone can explain my mistake in B — https://codeforces.com/contest/1621/submission/141579787 i commended the code, but i guess it's pretty easy, but still don't get what test doesn't pass and what's my mistake

Consider this test case:

A teacher/student with age $$$10^5$$$ in problem $$$E$$$:

I don't think F is bad although it's all about the case work. (I'm saying this as someone who had a minor implementation bug when handling one last case and barely missed it)

There are so many dubious accounts in this contest. iltt1, iltt2, ..., iltt7, ilg1, ilg2, ..., ilg6, ig1, igg2, ig3, ig4, ig5, ig6, ilt1, ..., ilt6, dk1, dkk2, dk3, dkk4, dk5, dkk6

These 31 accounts all submitted the same problems at roughly the same times with highly obfuscated code. They can be found in the 1100s in the standings.

Though I performed really bad, I feel EFG are really interesting. I agree with kpw29, recent rounds are becoming standard and boring, but this round gives me different feeling. Thank the author.

I never said that the rounds are becoming standard and boring ;__;

Though I agree with happyguy656 — thanks for a good round!

Happy New Year!) And good luck on the next round!

Happy new year! I hate this round!

I think D is a really cool problem, one of the best in a while.

Is anyone else wondering, what would happened if tourist reached 4000 contest rating ?

Happy new year!

Another contest for tourist to come first...lol