rui_er's blog

Codeforces Round 864 (Div. 2)
By rui_er, history, 21 month(s) 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 (187)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it +39 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +21 Vote: I do not like it

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

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +68 Vote: I do not like it

As a tester, I test.

→ Reply
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it -59 Vote: I do not like it

OMG CN ROUND

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    are these people hating you or the chinese round? lol

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

      → Reply
»
21 month(s) ago, # |
  Vote: I like it -12 Vote: I do not like it
About Li Hua
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Why did all these testers get downvote? bcz meaningless?

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← 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
»
21 month(s) ago, # |
  Vote: I like it +16 Vote: I do not like it

hope you enjoy this round.

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

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

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← Rev. 3   Vote: I like it +33 Vote: I do not like it

Those who think MagentaCobra is newbie tester :o

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

My first unrated Div2 :)

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

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

→ Reply
»
21 month(s) ago, # |
← Rev. 6   Vote: I like it -8 Vote: I do not like it

Please do not downvote .Apologize for my illogical comment.

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

Please test more about problem D.

→ Reply
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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 DitaMirika are cute qwq).

Hope this round won't betray my trust.

→ Reply
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

    Think positive and do your best. Good luck to everybody.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it -77 Vote: I do not like it

      Bro, check out last 5 chinesE rounds, they're utterly disgusting. Math, math, math...

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Matb is the soul of cp

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

        I love math very much.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it -47 Vote: I do not like it

          Then go do math problems instead.

          → Reply
          • »
            »
            »
            »
            »
            »
            21 month(s) ago, # ^ |
              Vote: I like it +9 Vote: I do not like it

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

            → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
          Vote: I like it +6 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          21 month(s) ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

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

          → Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

we will solve Li Hua's problems.

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

Hope to become an expert...

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

The nice contest

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

Chinese writers. Looking forward to Mathforces

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

Hope to become an Pupil ...

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

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

    → Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it -57 Vote: I do not like it

Goo luck everyone!

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

Yet another stupid mathforces round

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I think it will be stringForces

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

stringforces?

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

Mazeforces :) || Patternforces :)

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +31 Vote: I do not like it
For who said it'll be mathforces
→ Reply
»
21 month(s) ago, # |
  Vote: I like it +26 Vote: I do not like it

WAforces

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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
»
21 month(s) ago, # |
  Vote: I like it -43 Vote: I do not like it

stupid contest. most of these problems are well known.

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

iq test round

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

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

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

Cool round! I enjoyed the problems!

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Div √(2*√2)

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

D???

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

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

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

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

→ Reply
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

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

    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++;

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    what you get is(5,2)

    result
    → Reply
»
21 month(s) ago, # |
← 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
  • »
    »
    21 month(s) ago, # ^ |
      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
»
21 month(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

I think the example of D is too weak.

→ Reply
»
21 month(s) ago, # |
← 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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

      → Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem C

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
      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
  • »
    »
    21 month(s) ago, # ^ |
    ← 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
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

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

Solutions looking for problems. Great examples.

→ Reply
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

Gridforces!

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

Update got the mistake:)

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

Debugforces

→ Reply
»
21 month(s) ago, # |
  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] > 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
  • »
    »
    21 month(s) ago, # ^ |
      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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you print "! n m" in line 28

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

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

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

Nice contest, I like the problems a lot

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← 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 и дерево 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

      Yes, I also think it is tougher

      → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

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

good contest.>.<

→ Reply
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
    1
3 4
? 1 1
1
? 2 1
1
? 1 1
1
! 2 1
Correct Answer : 2 2
    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you, I just realized that I have been understanding the wrong meaning, always thought that the input was Manhattan distance

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

I actually like problem D lol

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

bruh nvm im stupid

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

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

→ Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

GridForces

→ Reply
»
21 month(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

.

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

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

→ Reply
»
21 month(s) ago, # |
  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
  • »
    »
    21 month(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
»
21 month(s) ago, # |
← 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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
21 month(s) ago, # |
  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
»
20 months ago, # |
  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
»
20 months ago, # |
← 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
  • »
    »
    20 months ago, # ^ |
      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
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
20 months ago, # |
  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
»
20 months ago, # |
  Vote: I like it +10 Vote: I do not like it

please update problem ratings

→ Reply
»
20 months ago, # |
← 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
»
20 months ago, # |
  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
»
18 months ago, # |
  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
»
5 months ago, # |
  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