Hello, Codeforces!

AC-Automation and I rui_er are glad to invite you to participate in Codeforces Round 864 (Div. 2), which will be held on Apr/08/2023 17:05 (Moscow time). **Please note the unusual start time.**

This round is rated for the participants with ratings strictly lower than **2100**. You will be given **6 problems** and **2 hours** to solve them. All the problems are prepared by AC-Automation and me.

We would like to thank:

- darkkcyan for a perfect coordination and help with the problem preparation.
- AC-Automation for providing some
~~rejected~~problems and helping me a lot in preparation. - zplqwq for polishing English statements and editorials.
- Alexdat2000 for the Russian translations.
- N_z__, HQJ2007, 2_3_3, ShmilyTY, blobugh, fishy15, Celtic, 10circle, LXH-cat, Hanghang007, wsc2008qwq, KaguyaH, XG0000, Astolfoo, 5ab, Electric_Field, MagentaCobra, RedLycoris, Everule, ieeqwq, Dominater069, Sol1, happydef, geospiza, amenotiomoi, zengminghao, yoy68, DitaMirika, yzy1, vectorwyx, vinfat, AliceLiCF, le0n and ak2006 for testing this round and providing valuable feedbacks.
- MikeMirzayanov for the great Codeforces and Polygon platforms.
You

for participating in this round.

There will be a finite number of interactive problems, so please see the guide of interactive problems if you are not familiar with it.

The main character of the problems is Li Hua.

**Who is Li Hua?**

Statements and editorials will be available in Chinese (Simplified) after the contest.

This is our first round. We've tried our best to make the round enjoyable. We are looking forward to your participation and hope you gain a non-negative delta in this round.

**UPD1: Score distribution: 500 — 1000 — 1500 — 1750 — 2250 — 3000.**

**UPD2: Editorial is out.**

**UPD3: Statement in Chinese and Editorial in Chinese are out.**

**UPD4: Congrats to the winners!**

Div.2:

Div.1 + Div.2:

Also congrats to the only div.2 participant who solves problem F: reborn2023!

As a first-time tester, I hope you enjoy the round!

Good luck for everyone！！！

As a tester, I lose a chance to get

~~negative~~rating cuz I solved 5 problems~~with totally +8~~:(Hope everyone be careful and good luck and have fun (:

First time to be a tester, wish you good luck & huve fun! :)

As a tester,I like this round which is very interesting! Wish you can enjoy it :)

As a tester, I test.

orzzzzz

As a tester, I won't say that the problems are perfect, but I still enjoyed the round. Hope you guys do too :)

Btw, rui_er is kawaii >w<

Upd. my testing experince and comment on each problem goes below.

During testing, I solved all six problems, but just barely. (I made my last submission at 01:50:15) Out of 7 total submissions, I got a runtime error on problem D but only due to insufficient array size. All my submissions run in one-third of the time limit.

As a tester, I think this contest is very Chinese characteristics and worth attending.

Good luck to all of you.

As a tester, The problemsetter rui_er is very cute! The problems are interesting and challenging. Wish you can enjoy her round!

As a tester, I enjoyed the Chinese problems, and I wish you can enjoy them too! :)

Problems are great. Good luck!

(When will Li Hua stop his foolish behavior of writing letters? lol)

As a tester, I recommend everyone to participate in this round! The problems are interesting. Good luck and positive delta!

As a first-time tester, I hope you can enjoy the fun problems!

As a tester, the problems are interesting but some are trivial.

[EDIT] Sorry. I didn't want to tell you not to participate in this round. I think one should participate by himself and has his evaluation.

Love rounds with Chinese authors. Let's do more in the coming days :)

OMG CN ROUND

are these people hating you or the chinese round? lol

idk why there are so many down vote. And by the way, I always lose ratings in cn rounds though I'm chinese.

About Li HuaLH is short for LHQ who founded the moon-thanking religion. The moon shines, thank the moon.

LH,9:00,sing

LH,9:00,singLH,9:00,sing

LH,9:00,sing

show show way

Why did all these testers get downvote? bcz meaningless?

I think people saw Chinese round and Celtic's comment, and thus thought other testers' comments are unreal.

This is our first round and, to be honest, there may be some imperfection in the round. Also, it seems that there is a wide prejudice against Chinese rounds.

It's always welcomed to give us suggestions to improve after the round. But anyway, in my opinion, I don't think it's proper to valuate a round before it's held just based on one tester's comment.

Sorry. I want to express that some problems are a bit classic for well-trained participants. It's only my personal opinion, not for everyone. I agree one should participate by himself and has his evaluation.

hope you enjoy this round.

the contest starts only 5 minutes after the end of ARC :(

Li Hua is the main character in English writing exams for Chinese students. He always asks you to write letters for him.Expecting string problems O_o

I can't wait to enjoy this round cause rui_er is so cute!

Those who think MagentaCobra is newbie tester :o

Lmao

My first unrated Div2 :)

Congratulations! You are Orange Name

congo!

congrats.

No offense, but I'm scared of problems from Chinese high school...

Please do not downvote .Apologize for my illogical comment.

why?

Please test more about problem D.

This contest is a bit earlier than usual (For Chinese people)

also for Canadians (location)

However I forgot that and join in at 23:05...

Usually I perform badly in CNR. But still willing to give it a try(bcz rui_er and DitaMirika are cute qwq).

Hope this round won't betray my trust.

Nice round!

I bet something is gonna be wrong with problemset (problems are too mathy, unbalanced, annoying). Let's see after the round.

Think

positiveand do yourbest.Goodluckto everybody.Bro, check out last 5 chinesE rounds, they're utterly disgusting. Math, math, math...

Matb is the soul of cp

Do you know that ... ?CP $$$≠$$$ Math

Did you know that I didn't say so?

I

lovemath very much.Then go do math problems instead.

Programming and math are the most interesting things for me. So i like combining them when solving CP problems.

I don't understand why have you mentioned math as disgusting!!! Math is the best way to develop the ability to think. It even makes the contest more interesting.

That's very sad that people say that math is disgusting only because they are bad at math ;(

we will solve Li Hua's problems.

Hope to become an expert...

All the best brother, I hope the same

The nice contest

Chinese writers. Looking forward to Mathforces

Hope to become an Pupil ...

The first step is knowing that u can't use 'an' before words starting with consonants

I have solved a good problem raised by rui_er in Luogu, and I believe these six questions will be very interesting.

good luck

Goo luck everyone!

Yet another stupid mathforces round

Yet another stupid bot.

2nd acc?

its normal time!Good luck everybody,i wish to all get positive delta!Thanks for doing contest!

I think it will be stringForces

There is a high chance that there will be some math problem on crt

stringforces?

Writing letters and not sending them?

There will be a finite number of $$$graph$$$ problems.

this will be my first round,Hopefully to get positive delta, Good luck everybody!i wish to all get positive delta.Thanks for doing contest!!!Sorry for my poor english.

You'll guaranteed get positive delta ;)

Maybe the author's writing task for the next English exam will be like this.

Spoiler假定你是李华，你正在出一场codeforces div.2 round，但最近你遇到了一些问题。于是你给Mike写了一封求助信寻求帮助。

Suppose you are Li Hua, you are setting up a codeforces div.2 round, but recently you have encountered some problems. So you wrote a letter to Mike asking for help.

Did any one notice Last line of I would like to thank ...

Spoiler"You" are the best

I guess this will be a mathforces round. ಠ_ಠ

Mazeforces :) || Patternforces :)

I think I made a mistake by giving priority to this contest over my tomorrow's exam ;(

For who said it'll be mathforcesYou were

wrong.WAforces

For real. I bricked B b/c I forgot about the case where i could make a move changing the center square if n is odd.

C was nice for its position! glad that they atleast made strong pretests, WAforces > FSTforces

Problem D is very interesting — literally do what is written in the statement

iq test round

iq means implementation quotient

Is...Isn't E just segment tree?

Cool round! I enjoyed the problems!

The problems are very good.I am glad I participated in this round.

Div √(2*√2)

D???

Thank god, my Last minute submission of C saved me :>

Problem D is the worst possible div2D. Thank you for this problem.

Why is this giving wrong answer on pretest 1 for C? I clearly get (5,1) as the answer for the second test of pretest 1.

link to code: https://mirror.codeforces.com/contest/1797/submission/201318204

Same, I don't know why my solution keeps giving WA on pretest 1. I tested it locally and it worked fine.

submission

UPD: I found my mistake, I didn't read the problem statement carefully as well as forgot King could also move diagonally

Same here. Just look at my code 201346552

:(

may be u dont notice that:

After asking a question do not forget to output the end of line and flush the output. Otherwise, you will get Idleness limit exceeded. To do this, use: fflush(stdout) or cout.flush() in C++;

endl in C++ automatically does that for you and you do not have to deal with that.

what you get is(5,2)

resultoh got it!

Ohh thanks! I forgot king can move diagonally as well.

Hmm why does'nt this code work for B? Did i misunderstand the question?

https://mirror.codeforces.com/contest/1797/submission/201297818

you need to check if n is odd when you check k%2 == 0, since if n is odd you can change the center element as many times as you want as after rotating 180 degrees, it remains at the same location! Therefore the correct check is

if k%2 == 0 or n%2 == 1

I think the example of D is too weak.

No.

Question about Problem C: I ask (1,1), (1,2) first. If the answer to the two times is the same, I can get x. If it is not the same, I can get y. And then I ask (1,y) or (x,1) to get the other coordinate. Is it wrong?

Depends on how you're calculating Y. You need to be careful about the case when the king is already on (1,1).

I did special judgment when n==1 and m==1

Original statement of B was very very bad, nothing said that you are not allowed to recolor a red cell to a red cell.

It sometimes makes sense in real world. Like in my room all of the walls are painted green. And if I want to freshen up the look and I like the same color, I will recolor green walls to green.

Idk maybe I am insane

Good problems. liked the idea of C and D. Good contest overall.

what idea is in D? you're literally just doing what the statement says

ABC were very decent, but problem D is very surprising to see on Codeforces in 2023, this is just implementation exercise, isn't it? Could've say the same about E if it was Div1 round, but in Div2 it's probably alright

RIP, I've been doing

heavy son of non-leaf vertex as the son with the largest subtreeimportanceB and C are too simple, but annoying to debug.

Me too lol.

How to solve Problem C

My solution is , first ask "? 1 1" ，then you will know ans1 = max(r,c).The king will only locate in(ans1+1, x) or (x,ans1+1) ,1<=x<=ans+1 .Then ask "? ans1+1 1" or "? 1 ans1+1" and get ans2 to check x. If ans2 isn't enough for u to check , remember that you can ask 3 questions. Just ask another question to check the final location.

first choose (1,1) then ask question on (1,1)

let mo be the minimum number of moves then I observed that answer can be

from [(1+mo,1) to (1+mo,1+mo) row wise] or from [(1,1+mo) to (1+mo,1+mo) column wise ]

also adjust the given ranges according to the availability of the cells

Now let x=min(1+mo,n) and y=min(1+mo,m)

then again ask question on (x,y)

which will give some moves let say mo

then either (x-mo,y) or (x,y-mo) is the answer

My submission https://mirror.codeforces.com/contest/1797/submission/201341195

who the hell starts numbering from top left T_T

But the problems were good ^_^

I mean that is the most natural numbering in coding when thinking about array indices.

Solutions looking for problems. Great examples.

The problems are good. But for me, problem D is a bit annoying, because I can't write the code correctly. Hope to enhance my coding skills.

Gridforces!

Update got the mistake:)

Debugforces

true

Can we solve $$$E$$$ using segment tree?

I firstly build a tree with $$$C$$$ vertices and prepare lca there (though is consumes much TL and ML).

I store in node the number of numbers, the lca of numbers, the minimum depth of number and the sum of distances from all numbers to that lca. On merge I do $$$c.lca = lca(a.lca, b.lca)$$$ and $$$c.res = a.res + b.res + a.cnt \cdot (depth[a.lca] - depth[c.lca]) + b.cnt \cdot (depth[b.lca] - depth[c.lca])$$$. On move up I do $$$mindepth--$$$ and if $$$depth[lca] > mindepth$$$ then $$$lca = euler[lca]$$$ and add to result $$$\pm 1 \cdot cnt$$$. But there can be case, when there are numbers $$$1$$$, and seems I have to count their number. This killed me.

Based on brute-force calculations, I found that the maximum depth is $$$23$$$. Which means that the maximum changes i might need to do before the number reaches $$$1$$$ is $$$23$$$ changes.

I thought of doing lca on segment tree and just brute force the update query but making sure not iterate on any number equal to $$$1$$$. this will guarantee a maximum of $$$23 \times n$$$ updates on segment tree.

I didn't have time to write it.

Great contest, I had a lot of fun solving the problems (until i got a bug in D that i couldn't figure out)

Can anyone please help me find the flaw in this code for C? Thanks!

201335214

My solution process is to first look for the top left and bottom right corners, and then all the possible answers left will either be a horizontal line, vertical line, or two points. I check this solution for half an hour but honestly had no clue of why its wrong...

you print "! n m" in line 28

Thank you so much..I don't think I'm able to sleep well tonight with this error..

Nice contest, I like the problems a lot

I made 2 wa 2 re 1 iq

looks like I need work on it.

Bad problemset — at least for 2A ~ 2D. In my opinion, 1797D - Li Hua and Tree is the worst div2D I have ever seen. I can't imagine why the authors put such a trivial problem for this position. And Celtic you are right. :)

Why am i getting WA on pretest 3 in this submission for problem D : 201343094

how to solve problem b?? i was checking v[i][j]==v[n-1-i][n-1-j] for every i, j it should satisfy but getting wrong answer on pretest 3 please help

Think about the case where n is odd

To those who feel confused about 'Li Hua'（李华）:

Li Hua frequented in many important English exams in China, including NEMT. So all students in China who take the exams are very familiar with him(or her?).

Here is the writing section in NEMT 2019:

translation:

Suppose you are Li Hua, your friend Terry in New Zealand asked you about the local customs, please reply the letter....

I think problem C is very similar to a previous problem from an ICPC mirror.

This problem is much more difficult than C, isn't it?

Yes, I also think it is tougher

I would say the solutions for both of them involve nearly the same procedure, albeit the ICPC one involves a bit more case work.

good contest.>.<

Could someone please tell me why WA1 happens? I can get the correct answer when I run it on my computer. I really don't understandThank you, I just realized that I have been understanding the wrong meaning, always thought that the input was Manhattan distance

I actually like problem D lol

bruh nvm im stupid

If only I had used "set" instead of "priority_queue" on D...

apparently problem C appeared here:

https://codingcompetitions.withgoogle.com/codejam/round/0000000000051708/000000000016c77c (subtask 1)

probably just a coincidence though

A: We need to block all adjacent cells of start or end cell. If one of them is on the corner, answer is 2; if one of them is on the edge, answer is 3; otherwise answer is 4.

B: We check each pair of symmetric cells ((x, y) and (n+1-x, n+1-y)), each pair of different color needs 1 operation. So we first adjust these pairs, and if there are extra operations, we do all of them on any single cell. If the amount of extra operations is even, we are done, otherwise we need to do the final operation on the center cell (if n is odd). If there's no center cell (when n is even) there's no solution.

C: For a single query (r, c) the set of valid answers is the boundary of a square center at (r, c) with length of side 2*query(r, c). We can first query on 2 corners, and the intersection of their set of valid answers will be a segment or 2 different points, then we can query for the final answer.

D: Implementation. We need to maintain the set of children of each node and sort them by (size[u], -u), and maintain the parent of each node. For rotating x, we first find it's parent p and it's heavy son h (which is the maximum in the child set of x), then we do (size[h], size[x]) := (size[x], size[x]-size[h]), similar for their importance. Finally we set parent of h to p, parent of x to h, and modify the child set of p, x, h.

E: Let dp[i]=the number of operation we need to change i into 1. By some pre-calculation we can see dp[i]<=23. So we can store all elements of a in 23 different sets, where set[i]= (set of indexs j where dp[a[j]]=i), and we can do range updates in 23*n set operations. Also we can use segment tree to maintain the sum of dp[i] and LCA of a[i] in range [l, r] (we assume all numbers are on a tree rooted at 1 and has an edge between each pair of (i, phi[i])).

YocyCraft, thanks for the short editorial. You deserve much contribution. Hope you author some contests soon :)

Why the color of "You" (in the last entry of thanks list) same as the color of a LGM?

Thanks for this great round, with +109 I'm now a cyan with 1435 rating.

GridForces

.

Ratings updated preliminary, it will be recalculated after removing the cheaters.

i really liked the problems A to D, but i am not able to figure out what was that edge case in pretest 3 of D

For me it was that I took son with smallest size and smallest index instead of biggest size and smallest index

`vector<set<pair<ll,ll>>>vs(N+1);`

I guess for it was the same:)no i have taken biggest size and smallest index

I forgot to delete x's pair from parent of x during type 2 operation

Can we determine the answer by asking for three vertices For problem C

Not solving D with over an hour left is so disappointing. I'm too slow at implementation

E is nice, but constraints on values up to 10^6 adds too much difficulty

It was the best Chinese codeforces round (in my opinion), thanks to rui_er and AC-Automation!

Hello Codeforces, In todays contest,in Ques B,my code got TLE on test case 10,but when I used ios_base::sync_with_stdio(false); line it got accepted after the contest. It is my request to plz accept this code as this code deserve to be right. Submission Id : https://mirror.codeforces.com/contest/1797/submission/201286585

gridforces then treeforces hmm a little frustrating

but still a good round, maybe one of the best cn round ever

Can anyone explain why my code is giving TLE for ques 4 ?

Submission Link — https://mirror.codeforces.com/contest/1797/submission/201435408

pi dfs(int node, vi adj[], int par, vi &a, vi &imp, vi& pa, vi &size){

here every time you are passing vi adj[] which takes time of O(n) every time you write a dfs statement you are accesing dfs for almost n times so it results in o(n^2) time complexity which results in tle.

you can try passing the address instead of passing complete adjecency list

The arrays are passed by reference so I think there is no need

Except vi adj[], here you passed the whole array

Today, I received a message from the Codeforces system that one of my solutions during this contest (Li Hua and Chess) significantly coincided with another member's solution. I found this very distressing since I would never even think of participating unfairly, and I now fear the same thing happening to me in future contests.

My solution: https://mirror.codeforces.com/contest/1797/submission/201309514

The other member's solution: https://mirror.codeforces.com/contest/1797/submission/201322475

I'm not entirely sure how to defend myself, since I did not use any pre-written code. First off, I would say I had no incentive to cheat. The other member was participating unofficially out of competition and their solution was sent ~20mins after mine. I do not know this other person, but even if I did, why would I give them my solution if they couldn't even benefit from it? It would be completely illogical for me to risk penalties or bans when neither of us has anything to gain, since they wouldn't be able to gain rating.

Of course, I know that's not really a valid argument. But comparing the code, I think it's perfectly reasonable to believe that the similarities are completely coincidental. This was an interactive problem, so naturally most of the lines have to cin or cout whatever the problem asks, in the order that the problem asks. Of course these lines are going to be the same between almost everybody's code. The only potentially suspicious similiarity is maybe some of the if/else statements, but among thousands of submissions, it's reasonable to think that some of them would use the same if/else structure. There's only so many ways you can solve this problem.

Unfortunately I don't really have any strong arguments to present, but I hope I can at least get a second look and potentially be exonerated. If not, I at least hope that I will not get banned or suspended long-term, as I would really love to continue competing in Codeforces contests and improving in competitive programming. Of course, I'm not going to play unfairly in any future contests, so hopefully a streak of nonsuspicious submissions can improve my credibility.

please update problem ratings

Your solution 201286321 for the problem 1797A significantly coincides with solutions cjn_yzk/201277026Respected Admin and Codeforces communityI know plagiarism is a common problem on this platform but I would like to prove that my solution 201286321 exactly matching with cjn_yzk solution 201277026 is purely coincidental and it is very rare of those cases where a user is penalised without his/her fault.The following points are some of my clarifications regarding the same :

The problem was simple (it has only 4 possible cases according to me) and there could have been more than one users trying the same logic (checking for the 4 cases in a simple order).

I code on VS Code and use Prettier (A Vs code extension to format the written code) maybe the other user used the same platform(VS code with same settings) or tool (Prettier) while writing the code.

Even MikeMirzayanov mentioned about similar thing (Point 1) in his comment on one of the CF Blog

How good is Codeforces Plagiarism Checker ?Neither do i use any public platforms like ideone to code, nor have i ever communicated with cjn_yzk. I would also humbly request cjn_yzk to clarify the same.

Later in this contest I successfully submitted the solution for problem B but cjn_yzk didn't. Moreover his wrong submission for problem statement B was nowhere close to mine.

Last but not the least I would like to state that "I honour and accept the final decision of Codeforces Admin" but as a supporter for fair cp platforms and better evaluation systems I felt it was my duty to state my side regarding the matter.

Edit 1:I am ready to clarify and provide any other possible proof which I may.Hello Can you give me the test 146 about problem c? I can't find my wrong at all!

In recent English exams of senior high school entrance examinations in Anhui Province,Li Hua is no longer busy because a guy called Li Hui has taken his duty away...

Li Hua is the main character in English writing exams for Chinese students. He always asks you to write letters for him.

LOL XD