rui_er's blog

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

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

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

As a tester, I test.

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

OMG CN ROUND

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    are these people hating you or the chinese round? lol

    → Reply
    • »
      »
      »
      12 months 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
»
12 months ago, # |
  Vote: I like it -12 Vote: I do not like it
About Li Hua
→ Reply
»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Why did all these testers get downvote? bcz meaningless?

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

hope you enjoy this round.

→ Reply
»
12 months ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
»
12 months 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
»
12 months 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
»
12 months ago, # |
← Rev. 3   Vote: I like it +33 Vote: I do not like it

Those who think MagentaCobra is newbie tester :o

→ Reply
»
12 months ago, # |
  Vote: I like it +56 Vote: I do not like it

My first unrated Div2 :)

→ Reply
»
12 months 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
»
12 months ago, # |
← Rev. 6   Vote: I like it -8 Vote: I do not like it

Please do not downvote .Apologize for my illogical comment.

→ Reply
»
12 months ago, # |
  Vote: I like it -36 Vote: I do not like it

Please test more about problem D.

→ Reply
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    also for Canadians (location)

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
12 months 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
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +31 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      12 months 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
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it +14 Vote: I do not like it

        Matb is the soul of cp

        → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I love math very much.

        → Reply
        • »
          »
          »
          »
          »
          12 months ago, # ^ |
            Vote: I like it -47 Vote: I do not like it

          Then go do math problems instead.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 months 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
      • »
        »
        »
        »
        12 months 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
        • »
          »
          »
          »
          »
          12 months 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
»
12 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

we will solve Li Hua's problems.

→ Reply
»
12 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope to become an expert...

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

The nice contest

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Chinese writers. Looking forward to Mathforces

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to become an Pupil ...

→ Reply
  • »
    »
    12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck

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

Goo luck everyone!

→ Reply
»
12 months ago, # |
  Vote: I like it -81 Vote: I do not like it

Yet another stupid mathforces round

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

I think it will be stringForces

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

stringforces?

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

Mazeforces :) || Patternforces :)

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

WAforces

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

iq test round

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Cool round! I enjoyed the problems!

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

Div √(2*√2)

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D???

→ Reply
»
12 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
12 months 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
»
12 months 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://codeforces.com/contest/1797/submission/201318204

→ Reply
  • »
    »
    12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    what you get is(5,2)

    result
    → Reply
»
12 months 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://codeforces.com/contest/1797/submission/201297818

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

I think the example of D is too weak.

→ Reply
»
12 months 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
  • »
    »
    12 months 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
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
12 months 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
»
12 months 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
  • »
    »
    12 months 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
»
12 months 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
»
12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Problem C

→ Reply
  • »
    »
    12 months 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
  • »
    »
    12 months 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://codeforces.com/contest/1797/submission/201341195

    → Reply
»
12 months 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
  • »
    »
    12 months 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
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solutions looking for problems. Great examples.

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

Gridforces!

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

Update got the mistake:)

→ Reply
»
12 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Debugforces

→ Reply
»
12 months 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
  • »
    »
    12 months 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
»
12 months 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
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    you print "! n m" in line 28

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

Nice contest, I like the problems a lot

→ Reply
»
12 months 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
»
12 months 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 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

good contest.>.<

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

I actually like problem D lol

→ Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

bruh nvm im stupid

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

GridForces

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

.

→ Reply
»
12 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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

→ Reply
»
12 months 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
  • »
    »
    12 months 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
  • »
    »
    12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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
»
12 months 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://codeforces.com/contest/1797/submission/201286585

→ Reply
»
12 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
»
12 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://codeforces.com/contest/1797/submission/201435408

→ Reply
  • »
    »
    12 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
    • »
      »
      »
      12 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
»
12 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://codeforces.com/contest/1797/submission/201309514

The other member's solution: https://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
»
12 months ago, # |
  Vote: I like it +10 Vote: I do not like it

please update problem ratings

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

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

Respected Admin and Codeforces community I know plagiarism is a common problem on this platform but I would like to prove that my solution 201277026 exactly matching with AvidAshu solution 201286321 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 DevC++ maybe the other user used the same platform 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 AvidAshu.

Later in this contest I failed to submit the solution for problem B but AvidAshu didn't. Moreover his right 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.

→ Reply
»
12 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
»
9 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