rui_er's blog

Codeforces Round 864 (Div. 2)
By rui_er, history, 3 years ago, In English

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:

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:

  1. syf2008
  2. elizazh
  3. zhouzizhe
  4. psz1
  5. wnmrmr

Div.1 + Div.2:

  1. jiangly
  2. heno239
  3. SSRS_
  4. BurnedChicken
  5. Sugar_fan

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

  • Vote: I like it
  • +407
  • Vote: I do not like it

Comments Comments (186)
| Write comment?
»
3 years ago, hide # |
 
Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +50 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +68 Vote: I do not like it

As a tester, I test.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +71 Vote: I do not like it

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.

  • A: Nice easy problem, seems a bit hard for its place. A little similiar to CNOI2016 Grid, but I think it is OK since Grid is much much much harder.
  • B: Nice easy problem, fits its place.
  • C: I personally do not approve of placing an interactive problem at C — for the unexperinced participants, the main difficulty will be to understand what is interaction, and a lot will likely spend the entire round wondering why they got "Idleness limit exceeded on test 1". The problem itself is OK though.
  • D: I don't quite get the point. It seems like it is just implementing the process with a balanced BST (something like std::set in C++), but somehow it also looks enough difficult for D? I don't know why. Still I think it is ok because at least it is not annoying to solve.
  • E: Quite standard, I got the solution 5 minutes after reading the problem, while Div.2 E usually cost me 15 minutes or more (not including implementation). Perhaps not that standard for non-Chinese participants? I don't know.
  • F: My favourite problem in this round. I was getting prepared to implement 300 lines of code at the first sight of the problem. And after getting nowhere with centroid decomposition, I came up with the intended solution which is just so elegant. I felt brilliant after solving it.
→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

Good luck to all of you.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +55 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +30 Vote: I do not like it

Problems are great. Good luck!

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +31 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +109 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -33 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -59 Vote: I do not like it

OMG CN ROUND

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it
About Li Hua
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Why did all these testers get downvote? bcz meaningless?

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +119 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      3 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it +70 Vote: I do not like it

      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.

      → Reply
»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

hope you enjoy this round.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +33 Vote: I do not like it

Those who think gotexans is newbie tester :o

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +56 Vote: I do not like it

My first unrated Div2 :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +45 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 6  
Vote: I like it -8 Vote: I do not like it

Please do not downvote .Apologize for my illogical comment.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -36 Vote: I do not like it

Please test more about problem D.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

Hope this round won't betray my trust.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -95 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

we will solve Li Hua's problems.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

Hope to become an expert...

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

The nice contest

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Chinese writers. Looking forward to Mathforces

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hope to become an Pupil ...

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

good luck

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it -57 Vote: I do not like it

Goo luck everyone!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -81 Vote: I do not like it

Yet another stupid mathforces round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I think it will be stringForces

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -17 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

stringforces?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Writing letters and not sending them?

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +18 Vote: I do not like it

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

Spoiler
→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Mazeforces :) || Patternforces :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +31 Vote: I do not like it
For who said it'll be mathforces
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +26 Vote: I do not like it

WAforces

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +13 Vote: I do not like it

    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.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it -43 Vote: I do not like it

stupid contest. most of these problems are well known.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +60 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

iq test round

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Cool round! I enjoyed the problems!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Div √(2*√2)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

D???

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -7 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

I think the example of D is too weak.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +46 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it
Denote the heavy son of a non-leaf vertex as the son with the largest subtree size

RIP, I've been doing heavy son of non-leaf vertex as the son with the largest subtree importance

B and C are too simple, but annoying to debug.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

How to solve Problem C

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    3 years ago, hide # ^ |
    ← Rev. 2  
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

who the hell starts numbering from top left T_T

But the problems were good ^_^

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Solutions looking for problems. Great examples.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +14 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +4 Vote: I do not like it

Gridforces!

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

Update got the mistake:)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Debugforces

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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] \gt 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.

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like 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)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

Nice contest, I like the problems a lot

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

I made 2 wa 2 re 1 iq
looks like I need work on it.

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +6 Vote: I do not like 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. :)

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +19 Vote: I do not like it

good contest.>.<

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it

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 understand

#include <bits/stdc++.h>
using namespace std;

int main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t;
	cin >> t;
	while (t--)
		{
			int n,m;
			cin>>n>>m;
			cout<<'?'<<' '<<1<<' '<<1<<endl;
			int d1,d2,d3;
			cin>>d1;
			if(d1<=n-1)
				{
					cout<<'?'<<' '<<1+d1<<' '<<1<<endl;
					cin>>d2;
					int y=(d1+d2+3-n)/2;
					cout<<'?'<<' '<<1<<' '<<y<<endl;
					cin>>d3;
					int x=1+d3;
					cout<<'!'<<' '<<x<<' '<<y<<endl;

				}
			else
				{
					int tmp=d1-(n-1);
					cout<<'?'<<' ' <<n<<' '<<1+tmp<<endl;
					cin>>d2;
					int y=(d1+d2+3-n+tmp)/2;

					cout<<'?'<<' '<<1<<' '<<y<<endl;
					cin>>d3;
					int 	x=1+d3;
					cout<<'!'<<' '<<x<<' '<<y<<endl;

				}

		}

	return 0;
}
→ Reply
»
3 years ago, hide # |
 
Vote: I like it +22 Vote: I do not like it

I actually like problem D lol

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

bruh nvm im stupid

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +17 Vote: I do not like it

apparently problem C appeared here:

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

probably just a coincidence though

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -16 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +2 Vote: I do not like it

GridForces

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +45 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -20 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

gridforces then treeforces hmm a little frustrating

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

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

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

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

→ Reply
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    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

    → Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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.

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

please update problem ratings

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it +18 Vote: I do not like it

Your solution 201286321 for the problem 1797A significantly coincides with solutions cjn_yzk/201277026

Respected Admin and Codeforces community I 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 :

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

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

  3. Even MikeMirzayanov mentioned about similar thing (Point 1) in his comment on one of the CF Blog How good is Codeforces Plagiarism Checker ?

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

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hello Can you give me the test 146 about problem c? I can't find my wrong at all!

→ Reply
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

LOL XD

→ Reply