xcyle's blog

By xcyle, 3 months ago, In English

EPIC

Hi, Codeforces!

We are pleased to invite you to EPIC Institute of Technology Round August 2024 (Div. 1 + Div. 2), which will be held on Aug/11/2024 17:35 (Moscow time).

The problems are prepared by Flamire, le0n and xcyle. You will be given 8 problems and 3 hours to solve them. Two problems are divided into two subtasks. The round will be rated for everyone.

We would like to thank everyone who has helped prepare for this round:

The score distribution is 500 - 750 - 1000 - (1250 - 1250) - 2000 - (2000 - 1250) - 4000 - 6000

Good luck, have fun!

Congratulations to the winners:

  1. jiangly
  2. Radewoosh
  3. Benq
  4. Um_nik
  5. maspy

UPD: Editorial is out!

And now, a few words from today's sponsor!

About EPIC Institute of Technology

EPIC Institute of Technology is an innovative educational project, driven by the Deltix team under the EPAM Systems umbrella. As part of EPIC — EPAM Product Innovation Center, we aim to cultivate the brightest minds and prepare them for a future in cutting-edge technology projects.

Why EPIC:

EPIC Institute of Technology is an accelerator for the best talents. Our students will acquire hands-on experience in one of the selected major programs, all of which are highly demanded right now on top projects, together with the fundamental knowledge, so indispensable for real professionals. Successful graduates will have a unique chance to jumpstart their career on the most challenging and interesting EPAM projects worldwide. You will join the community of intelligent and driven individuals and have an honor to work with and learn from them.

Here are the answers to the most common questions:

How much does education cost?

EPIC Institute of Technology is completely free. There are no fees to register for exams, tuition fees or any other hidden liabilities. The only restriction for getting into EPIC Institute of Technology is age. You must be older than 18 years old to become a student.

How is the educational process organized?

Each program lasts exactly one year. The academic year consists of two semesters. Courses in the first semester are the same for all programs. Courses in the second semester depend on the selected major program.

During the semester, students complete homework assignments and take 2 exams—a midterm and a final. The final grade a student gets for each training course depends on the quality of completed assignments and participation in practical classes.

How will the classes be held?

Lectures will be pre-recorded and available for self-study. Practical classes will be held at the specified time according to the provided schedule. Also, students will have an access to a Discord server, where they can discuss topics of academic interest with teachers and other students.

In what language will I study?

All programs are in English.

How can I apply?

The admissions process is as follows:

  1. Fill out the form on the website.

  2. Take part in one of the entrance exams that will be held in our Codeforces group. You can also find past exam breakdowns there, which may help you in your preparation. Exam dates will be announced later, so stay tuned to the announcement channel and our LinkedIn group.

  3. If you successfully pass the exam, you will receive an invitation email.

What will happen after graduation?

All EPIC Institute of Technology graduates will get a diploma and the best students will be offered to join, either as an intern or a full-time position, one of the hot EPAM projects where skills acquired at EPIC Institute of Technology will be demanded.

Please visit our website to learn more about EPIC Institute of Technology and the available programs. If you have any questions, you can quickly ask them in our chat.

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

»
3 months ago, # |
Rev. 2   Vote: I like it +221 Vote: I do not like it

I hope Gennady will win this round, break 4000, and finally achieve a new rank 'God'!

»
3 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I am the first comment ;)

»
3 months ago, # |
  Vote: I like it +138 Vote: I do not like it

As a tester, I missed the opportunity to post the first comment because I spent too much time thinking about what to post as an "as a tester" comment.

»
3 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

yay! as a tester & translator, good luck to everyone!

»
3 months ago, # |
  Vote: I like it +128 Vote: I do not like it

$$${\color{orange}{\text{As}}}$$$ $$${\color{purple}{\text{a}}}$$$ $$${\color{blue}{\text{tester}}}$$$,

»
3 months ago, # |
  Vote: I like it +29 Vote: I do not like it

I got -155 last EPIC round, hopefully it will go better this time!

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

    The last EPIC also went badly for me, I hope not to screw up problem C again ;)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Welp... I think EPIC rounds are just cursed for you at this point lol

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Welp, at least not an EPIC fail like last time!

»
3 months ago, # |
  Vote: I like it +11 Vote: I do not like it

As a tester, I tested this round.

»
3 months ago, # |
Rev. 2   Vote: I like it +61 Vote: I do not like it

As a tester, I suggest you taking a nap when you got stuck. (It did help me)

BTW le0n is so cute! It's such a pity we don't have a photo of the authors.

»
3 months ago, # |
  Vote: I like it -52 Vote: I do not like it

boooo 3-hour round

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

My last performance in EPIC div1+2 was so bad. Hope I can come back this round

»
3 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Hope tourist cross 4000 rating after this round.

»
3 months ago, # |
  Vote: I like it +16 Vote: I do not like it

le0n is BeiJing's Captain!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Another EPIC Round!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

great contast there is some cheater who submit que 3 before 10 min of contast.there is whole youtube chanel who cheat people and there is 4000 views on video and code forces can't able to see them ,i open a rendom submition and i found he is also cheater and his name adarshrai24 . he also cheat in last contest so do some action on them ,it roune other's hardwork ;)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain the score distribution (esp the bracket part)?

The score distribution is 500 — 750 — 1000 — (1000 — 1000) — 2000 — (2000 — 1250) — 4000 — 6000

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    The brackets means the problems (in this case pD and pF) are divided into subtasks. So you'll see problem D1, D2 and F1, F2 in the competition.

    Usually, the second part has tighter constraints, and a code passing the second part would also pass the first part (hence the harder second part might award less points, like in pF. But actually you get 2000+1250 by solving the hard and only 2000 by solving the easy.)

    However there are examples where the two parts are different questions, such as problem 1984C1 and 1984C2.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      I appreciate you telling me that in a comprehensive manner. Thank you BaoCoder613

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Hoping to break the 1400 barrier and becoming specialist this contest! Wishing everyone goodluck!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

"a few words "?

»
3 months ago, # |
  Vote: I like it +55 Vote: I do not like it

please no median this time

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully the problem score distribution is proportional to the problem difficulty this time.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Hopefully I can break 1600 barrier :)

»
3 months ago, # |
  Vote: I like it -153 Vote: I do not like it

Um_nik jiangly if you rank is higher than tourist please do some unnecessary wrong hacks to decrease your rank in this contest

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope I can get a good score!Good luck to me and to you!

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

Good luck, Gennady.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is so EPIC about it

»
3 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

hope to reach expert in this round

»
3 months ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

All the best everyone

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Did you notice that the logo in the announcement doesn't loop? This is the first time I saw a GIF not looping. Did some search and found out that there's a “loop count” field in a GIF file.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope the best for every candidate.

»
3 months ago, # |
  Vote: I like it -8 Vote: I do not like it

I hope I will become Red after this round

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Am I a mad man by going in div1+2 and expect to reach specialist?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    no, im mad for trying to reach expert

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      We're both mad man then, let's do it.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        fr best of luck!

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

          I'm ready to take my minus rating. Today problem got me real good but I'm convinced

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

            Lack of sleep got me real good :)

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

All eyes on tourist!

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a newbie, I am sure that I will lose my rating.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Today's Target :- A, B and C.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Let's hope it won't backfire horribly! Like on the last Div 2. Or on the last EPIC Div 2.

    Today's objective: Survive

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

where is tourist :<<<

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hope for Salah7_a

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck Radewoosh :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

all the best

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

Great work this time, got nice results, keep it up.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

im going insane with this B

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2 hours of brain storming on B and still nothing code forces made me masochist

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

    hey, it was easy. Just see if both the arrays are initially equal or not. If not, check if the array for Bob if reversed will it become equal to a or not, if yes, print Bob, otherwise in all other cases Alice will win.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My brain ain't braining after seeing problem B and C.

»
3 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Nice and very balanced contest :)

»
3 months ago, # |
Rev. 2   Vote: I like it +36 Vote: I do not like it

Not intending to be whiny but 1100 ACs for D2 is crazy ngl (all evidence points towards cheaters). Someone remind me to skip the next EPIC round (got -117 delta lol).

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I hope I am not the only one skipping both D1+D2 to solve E+F, like I honestly can't grasp how to implement even D1...

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    My implementation was really messy but the idea (at least for me) was to notice that the nodes in a perfect binary tree have to have specific positions. Like, 2 has to be either 1 after $$$1$$$ or $$$2^{k-1}$$$ after 1, and so on like that.

    So I kept a Fenwick tree $$$c$$$ where $$$c_i$$$ represented whether node $$$i$$$ was in the right spot in reference to its parent.

    Then after each query, I just checked if $$$\sum_{i=1}^n c_i = n$$$.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      F*ck me, I was stupid. In fact if I got it right, that could be implemented much more simple even, not requiring a Fenwick tree.

      Thank you.

      • »
        »
        »
        »
        3 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I think I tried along these lines but couldn't convert to a right solution. Got WA at pretest 4. Can you help me with this pls?

        Spoiler
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any suggest on C to deal with epsilon stuff in python?

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

    You don't need to. Do not sqrt it, just compare the squares.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      oh man... thanks. Too late to notice my naive-ness

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

        *naivety.

        In fact by removing hyphen, naiveness is actually a word. Learn something new everyday, I guess.

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

      i did'nt undersatnd why it gives WA when we use sqrt((x2-x1)^2 + (y2-y1)^2))...

      but it got accepted when i removed sqrt

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

        Precision error. Especially so when comparation does account for equal values.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For me A >> B :(
Please someone explain with proof...
I was able to come up with a logic on pen & paper but could not implement it :(

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

    Try with Pen & paper for few cases. looks how many box need to be color differently.

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

      I tried but couldn't implement it properly (WA on 2), you can see my submission.

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

        overcomplicated. Also, you solution probably gives TLE in further case also. For solution, draw full box of 7 rows and 4 cols, here k=3; see, grid inside k*k boxes, we are not allowed to draw same color twice.

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

    it took me an hour or even more to derive it mathematically and implement it :')

    Spoiler

    hope this helps

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

      this is a bit over complicated

      Spoiler
  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    basically you can make a k x k square of all different colors and just copy it around. But if one side of the board is smaller than k you can cut a part of the square that doesn't fit (either in height or width independently)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Solution for problem A
»
3 months ago, # |
  Vote: I like it -7 Vote: I do not like it

EPIC fail

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Couldn't solve C. The fact that I rarely got AC from a problem relating to real numbers :(.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Then don't do real numbers.

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

    you don't need real numbers

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

    kudos to your spirit tho, you tried till the end and got D1 :)

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

      Actually I was about to give up after seeing thousands of people got accepted in C, before trying to ignore my despair about that and continue.

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

2.6k solves on that D1? lmao sure

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

    are you forgetting that this is div1+2?

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      nop i am not, if you will take a quick look at people in the leaderboard , you will find a staggering lot CMs, IMs skipping D1,D2 and going for E. While there a HELL LOT and yeah i mean a LOTTT of pupils and specialists solving D1 who are not alt accounts, and guess whats the common factor? They started submitting D1 after 1:35 hr and then submitted D2 wihtin a span of 1-5 mins .

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        I'm not noticing much around 1:35 mark, but I will admit that D2 submissions are suspect. Plenty of newbies who were getting rank 10k+ in contests a few weeks ago suddenly solving it.

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

        Yeah I even solved F1 but failed in solving D)

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

    if you know basic segment tree or BIT ( Fenwick ), you can also solve it :) .

    The constraint that it is complete binary tree, made the question very easy...

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

      i mean i agree to that i dont know fenwicks :) , but 2.6k people with a lot of pupils and specialists like come on most of them dont know fenwick.

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

        dude it's a div2c you think bit or fenwick is necessary?

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

          well i am talking about D1, and go and look at people at rank 502 and 504 in the leaderboard and tell me they are not cheaters, lmao

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

            sorry brainfarted, i meant d not c

            even so div2d VERY rarely requires seg/fenwick, I solved D1 (but not D2) using just std::set and a bfs

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
              Rev. 2   Vote: I like it +5 Vote: I do not like it

              brother you are missing my point :). My point is not about people who solved only D1 , or who solved D1 and D2 but like there is a gap of 20+ mins in their submission. I am talkng about pupils and specialists solving D1 and D2 within 5 minutes cuz they are pasting the same code in both, i.e. the code that is leaked is for D2 and works on D1. Like i literally opened a random page at rank 450+ and you will find lots of people like this.

              Just examples from a 30 sec look , ranks: 502, 504, 510, 527 even if 2 of them are cheaters it took me 30 sec to identify them that means there a hell lot of them

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

        don't worry, things take time. It is quite easy, you can learn it before system testing finishes !!

        https://www.youtube.com/watch?v=CWDQJGaN1gY

        Google for more resources.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Definitely a lot of cheating going on.
    Found this guy Aryanap963 in my room who looks suspicious with the biggest red flag being he's from IIT BHU

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      I have seen a lot of shitty very obvious cheaters from IIT KGP on this contest too. Like on one hand there is a demon like Dominater069 and then there are these cheaters from a same , and I believe prestigious college, I mean I even don't care that much about my rating but the thing is this mass cheating thing is just getting sader and sader :)

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

is D2 HLD ?

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

275842383

Hello, I'm wondering what is wrong on my code here. It fails on Test Case 4 and have been searching the error for more than an hour but don't find it.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Stuck at C for more than one hour before I realize it's simply to solve the intersection between perpendicular bisector and the path.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Me while submitting D2: "Yeah it's definitely gonna TLE"
OMG running on pretest 10 !!
OMG running on pretest 20 !!
TLE on pretest 23
WHY GIVE HOPE ?????

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    be thankful to organiser. It could have been worse.

    OMG running on pretest 10 !!

    OMG running on pretest 20 !!

    OMG Pretest Passed !!

    FST on test case 183 :(

    Glass half-full half-empty brother. Think on positive side :) ,

»
3 months ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

E < D < C

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

    LOL, kidding right ?

    C is just taking distance of circle to target, and comparing if it is less than or equal to character's distance from target.

    One simple if condition... The only thing is,,, we need to keep the square of the distance, rather than taking square-root.

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      E was waaaaay more intuitive for me than C.

      In C I thought we shoud take colinear vector and for each point check if distance from intersection to circle center is less than distance to start point.

      E has a simple stack solution (you can check my sub: 275826831)

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Please don't make me feel further depressed lol

        I solved C in 5 minutes but came up with all kinds of wrong intuitions on E so that I almost could not solve it. I literally debugged E for 1.5 hours using a random generator and completely wrote new solutions several times. The solution is simple but it was a hard way to reach there...

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

        Don't joke like that. As a grey, I've solved C for 30 mins while getting stuck in E though I know that wasn't too hard

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In a way, I can see their sentiment on E < C. E actually required less "thinking" to come up with the idea, like the solution is straight-up simulating the given process in a careful way — at least the catch is partially within what's given. For C, it's more covert.

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

      I think the hard part is to convince yourself that this works and not the implementation difficulty...

      My way of convincing is that if you can't go to the end point through a straight line and instead you bump into a circle, you can't go to the end point through a curve without bumping as well

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

    sure? I got C in 15 minutes and struugled 2hours for D and ended up not solving it :/

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

nice problems but i'm too weak for them.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was able to blaze trough ABC in half an hour but then i saw D. Got the idea on how to solve it quiet fast but then didn't manage to implement it in over 2h. Quite an EPIC fail Otherways great contest

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

    can you tell me your thought process in B ?

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Bob can only win if he manage to delete the same element which is deleted by Alice in each operation, and this is only possible when b == a or b == reverse(a).

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

      Lets say that we have a = {1,2,3} and b = {2,3,1}. In this case if alice chooses to remove 3 bob will have to remove a number that is not 3, since his 3 is not on the edge of the array. Now alice can just remove everything except for what bob removed on his first move like this:

      a = {1,2} b = {2,3} // At this point alice can just not remove the 1. If she doesnt remove it bob wont have it and she will win.
      a = {1} b = {2}
      

      What we noticed is that bob will always want to remove the same number as alice since if he doesn't he looses. Knowing this bob will win if he at all points has the same numbers that he can remove as alice. So we will just check if a = b or if REVERSE(a) = b since in that case they still have the same options every turn.

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

    Same, I had the idea, but man implementing it takes just too much time. Btw I saw that there is a known algorithm to do that. You can google Depth First Search algorithm

»
3 months ago, # |
  Vote: I like it +13 Vote: I do not like it

Was writing line intersection in C for an hour(problems with precision), only to realise it is solved with one distance check.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    kak?

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      int n;
      		cin >> n;
      		vector<point> l(n);
      		for (int i = 0; i < n; i++) {
      			cin >> l[i].x >> l[i].y;
      		}
      		point start;
      		cin >> start.x >> start.y;
      		point finish;
      		cin >> finish.x >> finish.y;
      		
      		double ans = true;
      		for (int i = 0; i < n; i++) {
      			if (dist(finish - start) >= dist(l[i] - finish)) {
      				ans = false;
      			}
      			
       
      		}
      
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    true story, cost too much time on intersection for naught. I too, fall for the same trap

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

    i was thinking the same kind of thing ... I just guessed the distance check at the end.. can you explain me the proof ?

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

      Can't prove it. Just guessed it is something simple considering how many people solved it. Distance solution was kinda reasonable so I tried it.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I did some haphazard proof on pen and paper that first it's always optimal to take a straight line between start and end points. Then I started doing some perpendicular distance stuff and then I checked using Pythagoras theorem and found that if a circle will intersect the straight path at some time "t" before you reach that same point, then it will for sure also intersect the end point before you reach it. Hence you can just check if any circle reaches the end point before you do. Honestly it's kind of a half-assed thought process that I just went with intuitively so I didn't really have a formal proof.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Assume you walk the straight line from A to B. Then for each circle with origin C, you can calculate the earliest time a when the circle touches the line AB, which is just the closest point from AB to C:

                C
                |
               a|
                |
        A-------+----+--B
      

      At time c > a, the circle covers some length 2b of the segment:

                C
              / | \
           c / a|  \ c
            /   |   \
        A--+----+----+--B
              b    b
      

      The Pythagorean theorem says a² + b² = c², and a is constant, so if c grows at a rate of 1/s, then b must grow at a rate greater than 1/s, which means that even if you are ahead of the circle, it will eventually catch up to you, unless you reach the destination (B) before the circle does. That's why it suffices to check that the distance AB < distance BC for all circle origins C.

      This also shows that there is no point in following a curved path (which seems plausible initially), because if distance AB < distance BC then you can just walk the straight path, and if distance AB ≥ distance BC you cannot reach B before the circle does, so there is no solution.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I fell for the same trap :/

»
3 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Problem B really screwed up this contest for me lol

»
3 months ago, # |
  Vote: I like it +9 Vote: I do not like it

D2 — check if 2 neighbors could be next to each other ina a correct dfs order. Check it for every neighbors and update during swaps. Use lca to check if they could be next to each other

»
3 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

In D1, I checked if the children were initially OK for all elements and then only checked for the swapped elements and their parents. But this gives WA on pretest 3. Can anyone explain why?

Submission for reference

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

    I had the same problem. I'm not sure if it's your problem, but you should check for OK for the children of the nodes swapped too. This is because their answers could have change.

    Submission for reference

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

      What I was doing wrong was running into the wrong memory location, and instead of giving a Runtime error, it just gave a WA :/

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

was there a chance I could get pretests passed with some more pragmas? it initially was tle10. with pragmas it got till pretest 13 https://mirror.codeforces.com/contest/2002/submission/275836926

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I see a lot of complaints about C and even though I didn't get stuck on it, I agree it was misplaced. Geometry automatically adds difficulty, doesn't matter if there's a clever idea behind that simplifies it — a clever idea adds difficulty!

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

    More than 8k people got AC though, so it's not really bad.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Most submitted without proving. Just so happens that the first naive check works because of a clever observation

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      3 hour contest and it's C. If you get stuck, you start guessing.

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Is there anyone trying to find projections in problem C?

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

    I did and failed in vain. Not handling the epsilon good enough

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I did shortest distance between line and point then take the intersect to calculate distance between start point and compare distance.

    and then realize that line equation doesn't worked for perpendicular line so I used Area of triangle then take height and use pythagorean theorem to calculate base and compare distance. which also fail

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

      I started doing the perpendicular distance thing but then luckily I realized if a circle reaches that perpendicular distance point on the line before you (or any point on the line in fact), then it will for sure reach the end point before you as well (I did it using Pythagoras theorem and some inequality). So I scrapped everything and just checked distance from end point

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

    I immediately thought of the Voronoi diagram. Makes intuition a whole lot easier.

»
3 months ago, # |
  Vote: I like it +43 Vote: I do not like it

D is nice, it made me notice how I don't know DFS.

The main idea for E is the same as https://uoj.ac/contest/91/problem/890 . I thought I should do something different because at least one of the testers should know it, sad...

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

itsover-2

1 and half hours of debugging C using double only to realize greedy argument with integer distance calculation without sqrt

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Just checking distance from centre to destination is either completly braindead or ingenious. No in between. Guess it is one of those times when not proving is helpful.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    I proved and solved in 3mins, it is possible

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

    Quick proof for C.

    Your speed and Circle speed is same. 1 unit per second. If circle reaches the target before you do, there is no way, you can reach the target. Try to do it for just one circle. and you will get it. :D

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -10 Vote: I do not like it

      thanks for this proof failed to solve the problem but will do learn from it

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I think this is only a proof that it is necessary, not that it is sufficient.

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

Completely got tricked in both B and C. Hands down to the problem setters for giving good problems and traps to test us. Thanks and appreciated.

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

    how did you solve B?

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

      Since the game is taking the 1st and last element, you can break it down into 2 options: - An array from a[1..x] - A reversed array of a[x+1..n] Bob want to match with Alice every turn so he can win. So you need to compare array b with a.

      There's 4 option to compare just "if then" compare them all. And there's an edge case (n is odd, in my case I got RTE coz I tried to compare 2 array with different length)

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

      if array A and B are same means Bob can always delete element alice deleted and get same ans it is also the case for when A is reverse of B , Bob can again do it . else Alice win

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Spoiler
    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ooooh I overkilled the problem again. Oops that was dumb of me

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

That D (D1) was way harder than usual D in Div2

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem C :

Calculate Squared Distance Between Two Points:

  • The squared distance between two points (a, b) and (c, d) is calculated using the formula:

$$$distance^{2} =(a−c)^{2} +(b−d)^{2}$$$

  • This is done to avoid computing the square root, which is computationally expensive and unnecessary for comparison purposes.

Calculate Squared Distance from Each Point to the Reference Point:

For each point (x, y) in the array v, the squared distance to the reference point (c, d) is calculated similarly:

$$$distance^{2} =(x−c)^{2} +(y−d)^{2}$$$

If the minimum squared distance is less than or equal to the squared distance between $$$(a, b)$$$ and $$$(c, d)$$$, it prints $$$NO$$$; otherwise, it prints $$$YES$$$.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Was D2 just D1 with binary search and some advanced data structures or is there a unique solution?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    D2 was about checking adjacent elements and seeing if they can exist as an adjacent element. I think either the problem order should have been D1,E (no D2) or E,D2 (no D1).

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      The scoring told you exactly that. You weren't able to add 1250 and 1250?

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

        I once got jinxed because of relying on scoring to predict my problem solving order. So I don't really check scoring now.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Just a thought at 178th minute for F2, I think it was correct but couldn't confirm. Is it just F1 with more complex casework?

In F1 I thought of DPing the availability of states within range $$$[n-300, n]$$$, F2 would be the same but with more case-handling (checking $$$(i, j)$$$ with $$$i \in [n-300, n]$$$ and $$$j \in [m-300, m]$$$, cannot force $$$i < j$$$ like in F1 since $$$n$$$ and $$$m$$$ aren't symmetric anymore).

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Is it me or someone else also getting "NO" response in 5th test case for C on my local compiler.

Test case 5: 1 999999998 1000000000 999999999 999999999 1 1

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

    Happened to me and it was because I was using the built-in pow function instead of just multiplying which resulted in a overflow.

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

    if you are using double then there would be some precision issues .. i jut squared the differences and used long long (didn't take root)

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

      Was having issues with understanding pow fn. Resolved now. Thanks

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

    use long double/powl instead of double/pow

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think i can pass D2 now. Debug finished. Why not another 30 minutes XD

»
3 months ago, # |
  Vote: I like it +37 Vote: I do not like it

I just realised: Problems A-C all have a simple solution and a complex proof.

»
3 months ago, # |
  Vote: I like it +14 Vote: I do not like it

The most wise thing I have ever done in this contest, is skip D2 and try E in the earliest time. Because I found D2 way much harder than E, at least for me.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

somehow I solved B in 2 minutes but struggled lot in A

»
3 months ago, # |
  Vote: I like it +27 Vote: I do not like it

A round made up of problems with huge personal differences.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can D1 be solved by calculating hashes for all unique dfs trees and answering yes on queries for which hash exists and no for those which doesnt?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I solve D1 via this method, but fail at D2 'cuz I have to update all ancestors, which can be $$$O(n)$$$. As of D1, the constraint ensures the depth is $$$O(\log n)$$$ so the complexity is $$$O(n\log^2n)$$$

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

      I dont understand what you mean by updating all ancestor, cant we just re update the hash?

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

        In my solution, I use a segment tree to maintain hashes, and for each query, the hashes of both query nodes and its ancesters need to be recalculated. What's your thought?

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

          Thinking the same... I didn't understand how check the adjacent elements works... Someone please explain

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

any one who solved A in o(1) can explain how did he derive the equation ?

»
3 months ago, # |
  Vote: I like it -21 Vote: I do not like it

D and E were really cool :)

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

Never has a task destroyed my confidence in my braincells as thouroughly as D1. How are people able to solve up to D2 so fast? Am I just a brainlet or is there some straightforward observation that I'm missing?

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

    Every node have at most 2 child, and subtree of each child must be same!

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it +52 Vote: I do not like it

    In problems of the form "swap/modify elements and say if the array is good", you usually have to break down the given global condition $$$C$$$ into local conditions $$$C = c_1 \land \ldots \land c_k$$$ such that each modification impacts a small number of local conditions, and each local condition can be verified quickly.

    Then, you maintain for each condition if it's currently true or false, and the count of satisfied conditions.

    I usually try to find a necessary set of conditions, and then alternate between simplifying/weakening the condition (to make it local) and strengthening the condition (to make it sufficient).

    First attempt (transform the condition into a set of conditions). First I remark that when $$$p_i = u$$$, the interval $$$[p_{i+1}, \ldots, p_{i+\mathrm{sz}_u-1}]$$$ must be a DFS order of the subtree of $$$u$$$. It's necessary and sufficient, but not local (the condition $$$c_1$$$ is literally the global condition, we didn't make any progress).

    So we would like to rewrite $$$c_u = \phi_u \land c_{v_1} \land \ldots \land c_{v_k}$$$ where $$$\phi_u$$$ is a brand new local condition around $$$u$$$ and $$$v_1 \ldots v_k$$$ the direct children. That way, we will have $$$C = \phi_1 \land \ldots \land \phi_n$$$ by induction.

    It's very powerful because you can rely on strong $$$c_v$$$ while building $$$\phi_u$$$!

    Second attempt (weaken the condition $$$c_u$$$ to make it local around $$$u$$$). All direct children of $$$u$$$ are in the interval $$$[pos_u + 1, pos_u + sz_u-1]$$$. It's necessary and local (when you swap two nodes $$$u$$$ and $$$v$$$, you update the good/bad status of $$$u, v$$$ and their parents), but not sufficient anymore, because a child of a child could be outside the interval.

    Third attempt (strengthen the condition to be able to rely on induction). I ask $$$[pos_v, pos_v + sz_v - 1] \subset [pos_u +1, pos_u+sz_u-1]$$$, it's both necessary, sufficient (by induction) and still local. For example, you can use std::set to get $$$\min(pos_v)$$$ and $$$\max(pos_v + sz_v)$$$.

    There is also a linear-time solution, check the editorial!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    We have a problem in which we want to find a sufficient and necessary conditions, so we just throw in necessary/sufficient conditions until AC (my real thought process)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain logic for D1?

  • »
    »
    3 months ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    height of the tree cannot be greater than 15.

    Now check the all the conditions like the distances of siblings should be constant with a certain value , positions of children should always be greater than parent and also one of the children should adjacent to the parent.

    My solution — 275851102

    P.S: I used a lot of map which resulted in TLE and after changing them into array, I cannot debug till the end of contest.

»
3 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for geometry!!

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

when will be rating roll back??

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem H?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem B what if alice has 1 3 5 2 4 and bob has 4 3 5 2 1 how does alice win ?

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

    alice 1 bob 1 alice 3 and bob sucks

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

    Alice removes 4. If Bob removes 4, then Alice can remove 2 and Bob cannot remove 2. If he tries to remove 2 by removing 1, Alice can just keep 1.

    If Bob removes 1, Alice can just keep 1.

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

    Alice removes 1 then bob also removes 1.. now alice removes 3 but this time bob can't remove 3 so now bob will have to remove some number other than 3.. in this way bob could not simulate the moves done by alice. so alice wins :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.me/contest/2002/submission/275851891 Isn't the TC of code q*logn? why is it giving TLE?

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

My Insights for A,B,C

A
B
C
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved D1 by hashing the set of nodes in the subtree of each node, and updating the paths for each query.

submission

seems very hackable though, is it feasible?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone please help me understand why this code doesn't work for D1? Thanks.

275855167

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

    (5x10e4*10e4) is it fitted in timelimit?

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Still no one rainboy the problem H

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

My solution for D1 was to use a node's relative position to its parent. In a DFS of a perfect binary tree, a node can only be in 2 possible positions with respect to its parent node (Ex: for size 3, we can either have 1 2 3 or 1 3 2, i.e. 2 can only be at a distance 1 or 2 from node 1. Same for node 3). So I just maintained a set of "wrong" nodes that did not satisfy this condition. Whenever 2 nodes x and y are swapped, we just check if x and y are wrong nodes after the switch (I did this using a hashmap to maintain positions of parent nodes). Apart from this, you also have to check if the children of x and y are in the right positions with respect to their parents, as that relative position may have changed after swapping x and y. After a swap, if the set of wrong nodes is empty, then it's a valid DFS. However, this only works for D1 as the complexity increases with an increase in the number of children per node. Maybe some data structure could help but I couldn't think of it in the contest.

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    i spent the contest brainrotting on this idea, it works because there's only two nodes per level and the subtree sizes of both children are the same

    if you generalize the condition to this problem's description of a valid dfs order), you can do some subtree xor hashing thing, though i couldn't come up with any provable solution (ideally you would only need to add O(1) or O(log(n)) bad nodes to your set per swap)

    here was my final solution 275822556 (it's definitely wrong btw but its hard to come up with random tests against it probably, i tried locally too). maybe there's some provable bound or a smarter way to maintain the bad nodes.

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

      Thanks for sharing! Can you explain the hashing part? I don't think I quite understood it from the code. I didn't even consider hashing at all to solve something like this lol

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

        so with xor hashing, you want to map every element to a random number (in my case i used two random numbers to make the hash bigger)

        then, if you want to check if two sets of elements are the same, you can just instead take the total xor of their hashes

        the valid DFS order check that I mentioned is the same as checking whether the set of nodes in my subtree is equal to the set of nodes in the range [position[x], position[x] + size_of_subtree[x]) of the dfs order, so you can verify that a DFS order works by checking the range hash on the dfs order for all nodes, which can be done with a segment tree (after subtree xor hashes)

        to limit the amount of nodes we check, I have no idea how to do it properly with this approach, but I heuristic bashed by adding node X, the node before X in the dfs order, the parent of X, and then the parents of each of those as well

»
3 months ago, # |
  Vote: I like it +49 Vote: I do not like it

I enjoyed problem F very much! G, on the other hand, left me dissatisfied with the contest, because I feel like I just played the system and didn't solve it.

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I have $$$O(N*Q)$$$ solution for D1. But I am curious about how any tester or author didn't notice that fact.

My submission: 275797240

UPD: Wrong submission, sorry fixed

»
3 months ago, # |
Rev. 3   Vote: I like it +13 Vote: I do not like it

There are some submissions to G that partition into equal halves, I wonder if it's possible to bound the time complexity or hack them:

»
3 months ago, # |
Rev. 9   Vote: I like it -18 Vote: I do not like it

very big round.

»
3 months ago, # |
Rev. 3   Vote: I like it -22 Vote: I do not like it

I am getting time limit error on test case 08 for the following code for D1 question.

Can anybody help me to optimize it more?

can some provide code to not to use check function after every query.

Your code here...
#include <bits/stdc++.h>
using namespace std;
#define mx 65538
int n,q;
int vl;
unordered_map<int,unordered_map<int,int>>dp;
vector<int> vc;
vector<int> p(mx);
unordered_map<int, int> mp;


void solve() {
    mp.clear();
    vc.clear();
    cin >> n >> q;
    int nwnw = n;
    
    for(int i=  0; i < n -1 ; i ++){
        cin>>vl;
        dp[vl][i + 2] = 1;
    }
    
    for(int i = 0 ; i < n ; i ++){
        cin>>p[i];
    }
    
    int x, y;
    
    int j = 0;
    while (n > 1) {
        vc.push_back(j);
        j++;
        n = n / 2;
    }
    int l = vc.size() - 1;
    int ll = vc.size();
    for (int k = l; k >= 0; k--) {
        ll = vc.size();
        for (int kk = k; kk < ll; kk++) {
            vc.push_back(vc[kk]);
        }
    }
    
    for (int i = 0; i < vc.size(); i++) {
        if (mp.find(vc[i]) != mp.end()) {
            int df = i - mp[vc[i]];
            for (int nxt = 0; nxt < df - 1; nxt++) {
                vc[nxt + i + 1] += df;
            }
        } else {
            mp[vc[i]] = i;
        }
    }
    vc.insert(vc.begin(), -1);
    // for(auto i : vc){
    //     cout<<i<<" ";
    // }
    // cout<<endl;
    n = nwnw;
    auto check = [&](){
        if (p[0] != 1) return false;
    
        for (int i = 1; i < n; i++) {
            if (dp[p[vc[i]]][p[i]] != 1) {
                // cout<<i;
                return false;
            }
        }
        return true;
    };
    while (q--) {
        cin >> x >> y;
        x--, y--;
        swap(p[x], p[y]);
        // for(int i = 0 ; i < n ; i ++){
        //     cout<<p[i]<<"_";
        // }
        // cout<<endl;
        if (check()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    vc.clear();
    mp.clear();
    return;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while (T--) {
        // cout<<"-----------------------------------------------------------------"<<endl;
        solve();
        // cout<<"-----------------------------------------------------------------"<<endl;
    }
    return 0;
}

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

    It would have been better if you provided submission link instead of pasting code here. Kindly keep that in mind.

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

      thank you for the information. actually i am new to the comment section that's why, but i will keep in mind for next time.

»
3 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nobody is going through that messy code just to debug runtime error!

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Either I'm blind or there is no H in the editorial...

»
3 months ago, # |
  Vote: I like it +8 Vote: I do not like it

became pupil

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

I will reach expert today

Meanwhile problem D test case 3:

salute to my nonexistent couldve increased rating

UPD: got 658th query wrong

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

Lol it's funny to see submissions of H. A lot of newbies got the logic.

»
3 months ago, # |
  Vote: I like it +1 Vote: I do not like it

For c problem if anyone needs help in c problem u may read this. -- 1)The path we should follow must be a straight line otherwise the chance of any circle cutting our path would be more,so this is the most greedy way and even u can do little casework to get some idea. 2)secondly suppose we cross a circle at a point in our path in that case circle will reach before us or with us at the final point ( geometric observation) it will never reach final point after us(as it is expanding radially with 1). 3)so we can calculate the distances of every circle center from final point this will be the time for it to reach the final position of our path and if we reached to final point before the fastest circle (circle taking minimum time to reach there) we can always get the answer as yes as we would not have encountered any circle in that case, otherwise we can't reach and answer is no. Hopefully it helps Sorry for my poor explanation skills

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D1 can be solved with divide & conquer ?

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Thank you for the contest! The problems are nice.

»
3 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Actually the problems are cool,

But the order...

As for me E < D1 < F1 < D2, so maybe it would be better if swapping D and E :)

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved AC and somehow got 0 delta

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how does this O(n * q) solution pass for D1 275884243. I have calculated every nodes current parent according to the permutation and checked it with its original parent

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

    It isn't $$$O(nq)$$$,it is $$$O(n+q)$$$.Because you just use the dfs function once.And in $$$q$$$ queries,because the given tree is a perfect tree,so each vertex only has 2 sons.It won't be TLE.

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

      at the end of each query I am comparing vectors (tp and p) both are of size n + 1. Comparing then will take O(n) hence it will be O(n * q)

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

        Maybe vector's constant is very small,so it can run fast.

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

          Maybe in most of the cases the vector might differ at some smaller indices

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hum, when i solved C it's too late for me to solve D, i waste so much time in problem C

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

There's an intuitively incorrect but acceptable solution for F2, which made it difficult for the problem setters to create counterexamples:

Assume we can reach $$$(h - 100, i)$$$ and $$$(w-100, i)$$$, then perform DP on the subgrid $$$\{(x, y) : x \in [h - 100, h], y \in [w - 100, w]\}$$$.

I asked the problem setters, and they all think it's really hard to hack because they spent several days trying to construct hack cases. However, as we've seen, this solution can get an AC on F2. So, can it be hacked or formally proven?

  • »
    »
    3 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    le0n has proposed a solution concept:

    Let's consider the blue fold-line and the red fold-line that it encloses. If we determine that the red line is reachable, then it is correct to assume that the blue line is also reachable. This allows us to simplify the problem to the following question:

    For each red line, is it possible for the set $$$\{(h - 99, i) : w - 100 < i \le w\} \cup \{(i, w - 99) : h - 100 < i \le h\}$$$, which represents the blue line, to enclose it?

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

there was obvious cheating in last DIV 1 + 2 , this blog explains it — https://codeforces.me/blog/entry/132571

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

s_mtCF hope you reach the grandmaster after the next context.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi everybody, can someone please explain me the score distribution system? Example: why the first problem should be "500" difficulty but in reality the lowest is like 800?

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i recieved message from the system that my solution to the problem B at the last round is matched with another solution and my answers have been skipped

it ask me to evidence that i don't share my solution but i don't have any what can i do to make to retrieve my submitions

»
3 months ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

It's no useful

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello sir, I have got an email saying my solution coincides [contest:2002][submission:275819490][user:aditya_kh7503] with someone, although i did the whole problem myself, i have attached the proof of my code on the platform, please don't remove my rating and please remove plag from my solutions.

Your text to link here...

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

    Your link is private, consider including the reason/proof in comment itself

    • »
      »
      »
      3 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      https://drive.google.com/drive/folders/1fdqu0NhDIFz5XSr6JjJbZ-UegxsHFSmd

      Here i have attached a link which clearly shows the code i submitted three days ago because i was learning the similar concept and you can match the code i have used here and in my submission, I just changed the code little bit in my contest and solved the problem. It can be a coincidence or anything else but yes i have been wrongly accused of cheating.

      Please remove plag from my code and consider the rating also remove the message which says i have been caught cheating. MikeMirzayanov

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

    Your submission for D2 as well as D1 is exactly the same (you only changed the names of variables, chatgpted into python, and gave values to random things which had nothing to do with the solution) as this one, which was copy pasted from this video on Youtube which 1000 people saw.

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

      I don't know the video you are talking about and if i would have used the code seen by 1000 users then i would have gotten the message that my solution is coinciding with many users but i have a coinciding solution with only one user which can be a coincidence or anything else. I have provided the proof that i used that code before my contest. If that's not enough then i don't know what proof codeforces need, i have provided everything that can prove me right. Codeforces itself says if you can show that you have used the code before the contest then that's a valid reason.

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

      Also my solution for d2 was not even accepted then i am sure what are you trying to say that both my solution are same .

»
3 months ago, # |
Rev. 2   Vote: I like it -44 Vote: I do not like it

Hello Codeforces,

In the last contest, I was accused of cheating in it, specifically for tasks D1 and D2. In that contest, I solved the first 5 tasks. I saw that I was accused with many other people. I see that the way I solved the task is similar, but my way of typing the code is different. This is my 10th contest and in each one I used full names for the variables because it's easier for me to understand and I also use the same template from the beginning. I have not cheated in any of the previous contests, nor in this one, nor do I intend to. According to my submissions, I practiced the tasks in order to improve myself in coding, I did 2 virtual contests where I solved the entire Div 3 and Pinely Round 4 (Div 1 + Div 2) did 5 tasks. Even my first contest was from Epic Institute of Technology where I solved 4 tasks. I don't know how to prove my innocence. So please MikeMirzayanov look at this.

Thanks in advance!

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Your submission for D2 as well as D1 is exactly the same (you only changed the names of variables) as this one, which was copy pasted from this video on Youtube which 1000 people saw.

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it -26 Vote: I do not like it

      Of course, the submission for D2 and D1 will be the same when I solved D2 and saw that the solution for D2 can also pass for D1. I didn't change anything because, as I said, I didn't cheat. If you look at my coding style I always use full names for variables because it's easier to understand.

      • »
        »
        »
        »
        3 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        You mean you always cheat? Bro please quit, why tf would you tag Mike, he doesn't deserve that. Literally the same code for a problem 244mhq didn't do, ur only changing the name of the variables, at this point admit it please. U ain't slick my guy

        • »
          »
          »
          »
          »
          3 months ago, # ^ |
            Vote: I like it -19 Vote: I do not like it

          Do not use alt accounts. First i will tag Mike because i did not cheat. Second why do you think that if someone who has at this moment higher rating than you and if he does not solve it that does not mean you can not solve that problem. Third like i said i did not copy the code because i coded it.

          • »
            »
            »
            »
            »
            »
            3 months ago, # ^ |
              Vote: I like it +25 Vote: I do not like it

            I asked ChatGPT to change the code from the leaker, and it produced a version very similar to yours. Please stop clowning, it's obvious that your code is line by line identical with leakers.

            • »
              »
              »
              »
              »
              »
              »
              3 months ago, # ^ |
                Vote: I like it -16 Vote: I do not like it

              I am not clowning. I know that i wrote the code myself.

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

    Don't know why so many downvotes when someone try to defend themselves.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Dear Codeforces Team,

I trust this message makes you well. Regarding allegations of plagiarism in my solutions to Problem 2002D1 — DFS Checker (Easy Version) and Problem 2002D2 — DFS Checker (Hard Version ). These are My Solution of Problem D1 Submission #275824981 and Problem D2 Submission #275825300 regarding Div 2.

Rest assured, I made every attempt to resolve each issue in isolation. I have solved to the best of understanding I can and did not copy or knowingly replicate any other users codes. Like I said, while my solutions might seem similar to how someone else achieved a solution coincedently as well. The problem was such that it is possible others might have landed at the same approach. But the my code is completely different from what others you have flagged. submissions

Now I know though that possibly having my code seen by the public due to using Ideone as it is also might have made similar coincidences happen. That was not my intention and I do apologize if its come out as a mix-up.

I wholeheartedly admit that this was my fault and I'm grateful to the Codeforces people for monitoring such nefarious ways of obtaining high rating positions. I will be more cautious about my code in the future, as well to protect myself and ensure that what I submit is truly a work of utmost individual effort.

Apologies again for any confusion here, and I fully committed to upholding the standards of the Codeforces community. MikeMirzayanov

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I love rounds that don't require any special knowledge on most tasks.

I planned to merge the rating, but eventually turned yellow (when I told the girl, she thought that there were liver problems).

»
3 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Dear Codeforces team,

I'm writing regarding the plagiarism warning I received for my solution to problem 2002B - Removals Game. I want to sincerely apologize for any concern this has caused. I assure you that I did not intentionally copy anyone's code or violate any rules.

The similarity in code is likely due to the straightforward nature of the problem and the concise logic required in Python. I came up with this solution independently and was not aware of any other identical submissions.

I understand the importance of maintaining the integrity of the competition. In the future, I will be extra careful to ensure my solutions are unique, even for simpler problems.

If possible, I kindly request that my rating not be affected by this incident. I am committed to participating fairly and ethically in all Codeforces contests.

Thank you for your understanding and consideration.

my sub :275819126 plag sub : 275775923 MikeMirzayanov

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I want to go back to Newbie...

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

I was falsely accused of cheating in this Codeforces contest.

In the previous contest, I achieved a rank of 32 — Can someone who has this rank really be a cheater? These accusations are both baseless and incredibly frustrating, especially considering that my previous account was banned for a similar reason, which was also unjust.

I have always approached competitive programming with integrity, and being labeled as a cheater after all my hard work is deeply disheartening.

I hope the Codeforces team will take a closer look at this situation and recognize the unfairness of these accusations.

»
3 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Hey MikeMirzayanov,

My solution[submission:275840267] for Problem 2002D1 was flagged as similar to many others. I believe this happened because the problem had very few possible approaches, and I used an AI tool (LLM) to help write some functions because as far as I know there isn't any restriction on using AI generated code on Codeforces. This might have caused some similarities.

I’ve solved similar problems in other contests too, and I’m confident that my solution is unique. I kindly request that my solution be reviewed again.

This blog also states this : Solutions and test generators can only use source code completely written by you, with the following two exceptions: 1. the code was written and published/distributed before the start of the round, 2. the code is generated using tools that were written and published/distributed before the start of the round.

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

    The plagiarism checker in codeforces is getting very strict.

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

Rating rollback???