MikeMirzayanov's blog

By MikeMirzayanov, 3 weeks ago, In English

Gamarjoba, Codeforces!

On Feb/06/2024 17:45 (Moscow time) will start Codeforces Round 923 (Div. 3), the next Codeforces round for the Div.3.

Lately, I've been coming up with problem ideas less frequently, but I don't want to lose this skill. Welcome to the round where all problems are my own creation! I hope you'll enjoy them.

A huge thank you to Vladosiya for preparing the majority of problems in Polygon. Also, thanks to pashka and KAN for helping with the discussion of problem ideas.

Thank you very much 74TrAkToR, CLown1331, EternalAlexander, Jostic11, Killever, KoT_OsKaR, LoveWX, MADE_IN_HEAVEN, dan_dolmatov, jnmtz111__, pedrolino, theRealChainman, yorky for testing the round.

As usual for the Div.3 rounds:

  • There will be 6-8 tasks in a round.
  • The round duration is 2 hours and 15 minutes.
  • The round follows the ICPC rules, with a penalty for an incorrect submission being 10 minutes.
  • The round is rated for participants with ratings up to 1600.
  • After the round, there will be a 12-hour open hacking phase.

Remember that only the trusted participants of the Div.3 will be included in the official standings table. As it is written in the link, this is a compulsory measure to combat unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • Participate in at least five rated rounds (and solve at least one problem in each of them).
  • Not have a rating of 1900 or higher.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Good luck to all!

I really like it when the round announcement includes a photo of the authors. I plan to add one if I can take a suitable photo.

UPD 1: I found great burgers in Tbilisi!

UPD 2: The editorial is published: https://codeforces.com/blog/entry/125597 (thank you, Vladosiya).

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

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

As a Participant, I would recommend to participate.

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

omg MikeMirzayanov round

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

fdgdfg

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

    can people like you not to spam appeals everywhere to catch attention

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

    can you shut up, your "main" account has nothing and you cheated twice in a row, lol.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it -49 Vote: I do not like it

      dfsdf

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

        then either not cheat on an account of "importance" or reach the admins of those groups and tell them how big of a cheater you are and beg for your second account to be on the group. Also, why would you cheat on codeforces anyways, the only benefit is rating which doesn't matter if you cheated for it. And having two accounts for submitting same solution doesn't make sence either, you will get same delta regardless. So don't cheat or don't exist in codeforces

        • »
          »
          »
          »
          »
          5 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          sdjcndscd

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

        Don't you know that one can also see your comment before the edit? lol

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

Guys the abcdef plan is cancelled, set goals on abcd

PS The questions mike comes up with are wonderful, mind challenging, and Unique

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

My last rated Div 3

»
3 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

My first unrated div3

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

First time testing :D, wish you high delta.

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

This is the first time I participate in a contest. Hope to become pupil!

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

    Even if you win the contest that is impossible.

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

      yep, see MakaPakka which was the 1st in his first contest which also is a div2 not div3. (Just wanted to prove your point)

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

    you'll need a few more contests before getting pupil. don't worry soon you will become a pupil. even if you don't you'll learn a lot

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

I think it's the 100th div3.

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

good luck!

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

Good luck to everyone and hope positive delta for all. I wish i get +100 at least in this contest :)

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

GOOD LUCK ! everyone

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

MikeMirzayanov is a Barcelona fan

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

    But I am a Real Madrid fan. So I must take part in this round to get cyan.

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

    That t-shirt says "Barcelona University".

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

Seems like you really enjoyed the burger , cant wait to participate

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

hope reach pupil after the round

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

Did you use divide and conquer algorithm before eating ?

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

that burger looks yum

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

can i have a mikeburger and uhh 1 mike fries and uuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuuh 1 cup of mikeflurry please

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

    Sir, this is a Wendy's

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

    😂 😂 So you shifted from negative contribution farming to positive farming xD?

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

      why do you care about contribution so much, that's all you ever talk about, well that and the cheaters

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

        This account is designed / created for those aspects especially busting cheaters.

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

      I thought the joke was unfunny but appatently you like it >:(

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

Wait, Mike is in Tbilisi? I live here! Hope you have a nice stay!

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

Time to farm some ratings. Hope to become specialist after this round.

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

gemrielad miirtvit, MikeMirzayanov

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

A Mike contest! Hope that I can get to expert this round

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

Hey! Hey! Hey! I am also a big fan of burgers as well, although you must try Adjaruli Khachapuri! If you have time maybe you want to meet up with the Georgian CP community? (If you have not tried Adjaruli Khachapuri yet, maybe we can go together?). Anyway, have fun in Georgia!

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

Can't wait to become an Expert

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

hope that will be my last rated div3 and also best wishes for you!

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

Good luck! Rating increase!

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

go georgia!

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

As a Participant , i love burger

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

I`m sigma

»
3 weeks ago, # |
Rev. 5   Vote: I like it -21 Vote: I do not like it

. All the newbies out there, Don't loose hope Never under estimate the power of a newbie, the newbies make history. Newbies are the real fighters, they fight even after loosing a lot, I am a newbie too, but history repeats itself, newbies become pupil then blue then eventually red.

Not today, not tomorrow, maybe not even after a month, but one day , mark my words, one day you gonna be happy for not giving up.

Let me tell you something-----> Once upon a time a newbie said "I'm gonna be at No.1 at the CodeForces", everyone laughed expert the guy who was at No.1 , cause he knew a warm blooded newbie can do what he says.........

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

    LONG LIVE THE NEWBIES! DOWN WITH THE GRANDMASTERS!!!

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

    I am a newbie fighter, most determined man on the planet earth. Mark my words!. I will one day reach my dream rating (800) , then I will reach spectralist rank , then glandmaster . I will beat Sundar pichai and become Ceo of Goggle and get $500 bullion USD wealth . Never give up!! (never gonna let you down)

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

    Everyone was a newbie at once.

    Except some veterans who got 1500 initial rating XD

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

      how does codeforces know someone is a veteran and give them 1500 rating XD

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

GIGACHAD Mike Mirzayanov round HOLY PogU

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

time to become pupil!

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

n

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

Damn that Burger looks good!

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

what a juicy burger in this morning i woke up

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

    what is the mean of burger ? I guess the original mean of word is changed by folks of codeforce. could you tell me ?

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

      oh , I see! His burger is juicy ^_^!

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

I feel like all the Div. 3/4 rounds are inaccessible to US students, is this normal or are there going to be more Div 3/4 rounds that are at a good time for US students (afternoon/evening in Pacific-Eastern time)?

But the problems will definitely be great — thanks for writing the round! I will probably virtual participate or solve problems individually.

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

    Then they would be inaccessible to European and Asian students.

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

Div3 by Mike and a delicious burger! Surely gonna be a round of all times.

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

Well, I've just found that Mike is also a Barcelona fan!

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

    Barcelona can also mean a city, we can't be sure because it doesn't have Barcelona football team's logo on it.

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

As a Tester, I really like this round and recommend to participate. Happy Spring Festival!

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

My first unrated Div3

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it
»
3 weeks ago, # |
  Vote: I like it -49 Vote: I do not like it

No way, 74TrAkToR comeback

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

Calling specialist.I need 14 point.

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

The burger looks delicious

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

First rated Div 3. as a specialist! Hope to not lose rating!

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

Nice. I'm always worried that I'll lose points if I participate in div2, but I don't have to worry about div3.

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

A good day starts with seeing the game (did the author take this picture with permission)

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

I hope to get a good score.

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

hope i can reach pupil this time :p

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

Expecting some great problems as Mike Orz has prepared them! All the best, everyone!

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

hopefully this will be my come back contest

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

This is my 6th rated contest and I feel like lucky to be able to farm on Div.3 before all my 1400 initial rating is used up. If everything goes well this will be my last rated Div.3

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

I want to eat burger too.

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

M I K E C O N T E S T

(Very excited, the first mike contest I'll participate in)

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

An interesting Div. 3 contest by Mike, sounds great!

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

I was waiting for this round. Because during 1 week was only round div2. And we have chance to improve our rating.

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

Eden Hazard round.

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

No one could stop me from eating a burger when coding!

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

This will be my first rated round.

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

THE LEGEND @MikeMirzayanov !! himself has set the questions...really excited to attempt the questions and enjoy the contest..

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

UPD: I found great burgers in Tbilisi!

So where? :) Bon appetit!

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

Waiting to finish my round the next Div.3 round MikeMirzayanov

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

@ZettaByte

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

Yeah MikeMirzayanov Round!!

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

Thank you for a yet again amazing round! You look quite handsome, by the way wink!

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

DelayForces.

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

1 Refresh = 10 minutes delay

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

Ah shit, here we go again

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

DelayForces... Again

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

10 minutes delay?

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

whenever there is a delay, there is 74Traktor :(

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

Again and again and again.

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

fr!?

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

Beginning time 22:35 -> 22:45?

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

Delayforces again :(

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

delay:<

»
3 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

why delayed

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

Why the ten minute delay?

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

Not a 10 min delay again!

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

Wow, is the man who eating hanburgers MikeMirzayanov?

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

Delayyyyy

Anyways, hope to become a green lantern today

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

Nah, I'd win.

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

delayForces

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

wait what?? 40k participants??

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

The contest is going to be QueueForces

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

Does someone have a reason that why are they postponing for 10 minutes?

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

41k+ participation ?

»
3 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

Queueueueueueueueueueueueueue...

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

Is problem B not solvable in Python? Had to switch to c++ to get accepted with the same implementation. Got 7 tle :(

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

    I'm the opposite lol, 6 tle with c++ but ac when switch to python

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

    Same here. I got multiple TLEs with PyPy before optimizing my solution and getting AC.

    Seems like time limit per test should've been 3 seconds instead of 2

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

omg you were in Georgia?

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

Good contest, Good Problems.

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

My rank will be updated or not since there are several participants above 1600 rating in contest?

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

It was a wonderful contest

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

cool contest with a cool problemset!! I felt D was easier than C, at least in terms of implementation.

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

What's the best way for construction E?

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

    So the idea was that elements as i and i+k differ by atmost 1.

    One way to do this was you put consecutive elements starting from 1 and take jumps of k, and wrap around to the array to start again from last unfilled index.

    But the subarray sums would be increasing by 1 in each case.

    Instead, we can alternate between putting elements from 1 onwards in increasing order, and in decreasing order from n the other time. This way the subarray sum differs by atmost 1.

    Code

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

    for $$$k = 4$$$ it always have to be either

    $$${x, y, z, w, x - 1, y + 1, z - 1, w + 1, x - 2, y + 2, z - 2, w + 2, ...}$$$

    $$$or$$$

    $$${x, y, z, w, x + 1, y - 1, z + 1, w - 1, x + 2, y - 2, z + 2, w - 2, ...}$$$

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

How to solve E ?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it
    For Problem E

    (overexcited because first E solve in 3yrs)
    observation: elements $$$a[i]$$$ and $$$a[i+k]$$$ can differ by only 1. Now, this means $$$a[i+k]$$$ can be bigger or smaller than $$$a[i]$$$, but only by one.
    Reason: if this is not maintained, then the sum of two immediately neighbouring permutations itself goes out of constraint, let alone thinking about the relationship about relations between all such permutations.
    Proof-ish: If we say $$$S(x)$$$ is sum of permutation starting at position x, then $$$S(x) - S(x+1) = a[x] - a[x+k]$$$. Thus, all $$$a[i]$$$ and $$$a[i+k]$$$ must not differ by more than $$$1$$$. (Also, they can't differ by zero because we only have one available occurrence of any integer. So, that means they must differ by exactly $$$1$$$).
    Construction: For all $$$even$$$ positioned elements: maintain $$$a[i] - a[i+k] = 1$$$. Similarly for all $$$odd$$$ positioned elements maintain the opposite, i.e $$$a[i] - a[i+k] = -1$$$.
    We can see that doing so, means the sums of permutations will keep alternating by $$$1$$$. That is the list of sums of permutations will look like $$$(A),(A+1),(A),(A+1),\ldots$$$

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

      Helpful Explanation.

      Code's Here:
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved $$$G$$$ but couldn't solve $$$F$$$

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

    I solved F but couldn't solve E

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

      I solved E in 10-15 minutes but couldn’t solve D

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

Why does Mo TLE for D ?

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

    What? The solution is just to form rle array and binsearch it for each query. There is no complex structures needed.

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

      Yeah i know that. Even Binary search is not the best approach as you can do it in $$$O(n)$$$ using stack.That's not the point.

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

        Wait what? Stack? It is much simpler: Define $$$nxt_i$$$ as the smallest number $$$j$$$ such that $$$i < j$$$ and $$$a_i \neq a_j$$$. If there is no such $$$j$$$ then $$$nxt_i=n+1$$$. Figuring out array $$$nxt$$$ is trivial and can be done in $$$O(n)$$$. Then for a query with $$$l$$$ and $$$r$$$, if $$$nxt_l$$$ is higher than $$$r$$$ then the answer is -1, otherwise the answer is $$$(l,nxt_l)$$$.

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

          i instinctively used stack to calculate $$$nxt_i$$$ but yea that was unecessary.My bad

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

      What? The solution is just storing index of the last not equal element. There is no binary search needed.

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

        Oh yeah, you are right. Sorry.

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

        how to look for that stored index fast without binary search or map or set ?

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

          create an array $$$nxt$$$ of size $$$n$$$, initially filled with $$$-1$$$ values. $$$nxt_i$$$ will store index of the last element which is not equal to $$$a_i$$$

          Transition looks like:

          $$$ \text{nxt}_i = \left\{ \begin{array}{ll} -1 & \text{if } i = 1 \\ i - 1 & \text{if } a_i \neq a_{i-1} \\ \text{nxt}_{i-1} & \text{if } a_i = a_{i-1} \end{array} \right. $$$

          we can calculate it in $$$O(n)$$$ .

          for $$$[l, r]$$$ query, if $$$nxt_i >= l$$$ answer is $$$[nxt_r, r]$$$ , otherwise answer is $$$[-1,-1]$$$

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

      rle array, whats that? I used 2 segment trees lol

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

    I also tried Mo on D... I learned it today so when I saw the problem I immediately thought of it, though it seems there was a much better way :(

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

    It doesn't TLE, the problem is that you are using a map to store the elements of the current range, and as you make $$$O(n\sqrt n)$$$ insertions and deletions on this map (because mo does $$$O(n\sqrt n)$$$ updates), your code ends up being $$$O(n\sqrt n\ log\ n)$$$ which is too much for $$$n\leq 2*10^5$$$. In fact, there exists a solution with mo for this problem, which got AC in 1528ms, here it is. Tell me if you want me to explain the idea behind that solution (the key is to keep updates in $$$O(1)$$$ and you can still do queries in $$$O(\sqrt n)$$$, as there are only $$$n$$$ queries).

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

speedforces

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

The contest was too easy, especially D with a simple segment tree implementation

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

    You could also solve it using binary search over the indices where the next element is different.

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

      I tried implementing this but my code fails somewhere, would you mind taking a look and telling me where I might have made a mistake? Thanks in advance. Here's the submission

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

        I made the same mistake. :)

        diff might be diffs.size() in the case when l is greater than all the values in diffs[], lower_bound would return diffs.end() here

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

          Welp, my previous submission tried to address that problem, but It's funny I still couldn't get it right, take a look here. And here for the accepted one. I just combined two incomplete submissions into a single good one >:D

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

      You can also solve it in O(n) time by calculating the closest non mathing pair for all indices

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

waste an hours on D for messing with segtree (TLE) and ask for help to cheageepeetee with no gain until realize it's simple two-pointer problem 💩

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

    i used two pointers but got TLE

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

      for each position i save the first index j (i < j) where a[i] != a[j], then it's O(n + q)

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

    same wasted 1 full hour implementing segtree(was implementing segtree for the first time in contest and 4-5 times otherwise ) where as i could just store all unique indexes and do binary search or something like that

    :<(

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

The contest was too easy, especially E with a simple observation

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

    I could find the pattern and prove why it works too.

    But I finished my implementation a couple of minutes after the contest. But, thankfully it was WA on test 2. Some implementation bug maybe. Submission

    UPD: AC

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it
:(
»
3 weeks ago, # |
Rev. 2   Vote: I like it +20 Vote: I do not like it

F.
How to find the edge with the smallest weight that can be part of a cycle? If an edge is not a part of a cycle, then it must be a bridge, and vice versa. So we have to find the edge with the smallest weight that's not a bridge. Bridges are explained here
After choosing the edge, we can just use DFS (BFS can be used too) to find any cycle that contains this edge, by DFSing from one end of the edge and setting parent as the other end so it won't come back immediately.

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

    You can just sort the edges in decreasing order and unite with DSU. To check whether there exists a cycle containing an edge, check whether the endpoints are in the same component just before adding this edge.

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

      Bruh — I started writing exactly that, but then I thought it wouldn't work for some reason... yea your solution is much better

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

        Yeah, I came up with that about 5min after reading the problem but later on I realized, "what if the order of edges matters?" because perhaps other edges of the same weight would be needed to complete the cycle.

        But actually it doesn't matter, because such a cycle will be found when considering the last of these edges in the sorting.

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

      after finding the optimal edge how did you construct the simple ycle where the edge exists?

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

        Same as drdilyor mentioned, you remove the edge then run BFS to find a path.

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

    Thanks bro ! Appreciate it.

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

    drdilyor, I have one doubt if you can please help.

    Can the problem F can also be solved using binary search. Predicate : Can we find a cycle in the graph in which the minimum edge weight atmost x. And delete all the edges weight greater than X and then consider the remaining graph.

    I think it will also follow monotonicity.

    If you can reply please reply will be very helpful. Thank you

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

      Unfortunately that won't really work, it's asking the minimum of the weights in cycle to be minimum. Consider this graph

      Spoiler

      We want to find the cycle with weights (1, 4, 4), and not (2,2,2). So you see, this doesn't fit the "minimum of maximum" pattern of binary search. We would need predicate to be able to find if there are cycles that have smaller minimum weight than $$$X$$$, which I think is just as hard as the original problem.

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

        drdilyor, Thank you very much for your help and explaining so much clearly. Thanks again for devoting your time to solve the doubt.

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

    You can find an edge with the smallest weight that sits on a cycle with 1 DFS in $$$O(m)$$$, no concept of bridge necessary. If you track visited time you can figure out that you encountered a cycle when ins[child]<ins[x]. Keep a count C[u] of when the node u formed a cycle and the number of cycles currently not closed by dfs cycle_count. When you leave a node x in dfs, you check if any cycles were opened on it C[x] and if so, you close the cycles cycle_count -= C[x].

    Now if the cycle_count > cycle_count_when_node_was_visited you know that the edge from x to its parent needs to be considered for the minimum weight edge.

    https://codeforces.com/contest/1927/submission/245472637

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

For Div 3. do we get rankings on no. of problems solved? coz I can't see any points for problems

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

    it might be based on penalty. for ex: you have 200 penalty and I have 246 penalty.

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

    this is an ICPC-style round. The rules are so: if participant 1 solved more tasks(no matter their order) than participant 2, he will be higher. If they solved equal N of problems, the one having less penalty, will be placed higher. Penalty is given based on sum of time of submissions

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

    The participants are sorted in descending order of number problems solved, in case of a tie, the participant with lower penalty comes before.

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

Do I have to find all bridges in the graph for Problem F? It would be a ton of code if I have to use DSU and LCA for judging bridges and I have been working on it for 70mins.

Edit 2: RecursiveCo has proposed a simple solution and it seems to be a div.3 standard sol

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

How to solve E?

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

    A constructive. My solution was (and i guess Mike's one was the same) noticing that iterating on array of sums, elements keep +1 and -1. So we may distribute permutation's numbers this way: first, we fill all elements on positions 0, k, 2k, ... . Second, we fill elements on positions ..., 2k+1, k+1, 1. Repeat while we have empty places in permutation. We fill with numbers starting from N to 1. (look 245191801 if my explanation was messy, the code is quite understandable)

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

    What I did was alternating between values I could "shift" up and down (basically increasing or decreasing by 1) for the initial k elements, so that when a value exits the range sum I can calculate another one that replaces it so that the sum alternates between 2 sum numbers with a difference of 1 between them.

    For example if n = 13 and k = 4, I would always first set n as the first element in the permutation and then 1 as the second, then for constructing the initial k elements range I would calculate how many times the previous element that shifts in the same direction of the current element would appear in the resulting permutation, so if I have

    13 1 ? ?

    The next element would be then 9, since 13 would shift down 3 times in total in this permutation:

    13 1 ? ? 12 ? ? ? 11 ? ? ? 10

    For elements that shift up it's the same process, but in this case 1 does shift up only 2 times in total in this permutation:

    13 1 ? ? 12 2 ? ? 11 3 ? ? 10

    So the next number must be 4, at this point you will have:

    13 1 9 4 ? ? ? ? ? ? ? ? ?

    From here is just matter of sliding the range through the array and the next element will be the element that last exited the range increased or decreased by one depending if it shift up or down. So if we were to do this operation for the next 4 elements we would have.

    13 1 9 4 12 2 8 5 ? ? ? ? ?

    One way I use to determine if a number shifts up or down is checking if the position is even or not.

    Hope this helps you understand the process behind solving the problem :).

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

Didn't do as well as I wished, but I enjoyed the problems.

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

Solution to D: It's easy to compute prefix sums like: If A[i — 1] != A[i] then prefix_sums[i] = prefix_sums[i — 1] + 1 Else prefix_sums[i] = prefix_sums[i — 1]

Then for each query we compute the value: prefix_sums[l — 1] — prefix_sums[r — 1]. If its 0 then obviously there is no pair of different elements so the answer is -1. Else there is a pair with different first element and second element so we take l as the first element in our answer and when prefix_sums[l] is smaller than prefix_sums of some index j (j > l) this means there was a pair of different elements so we just binary search for first j.

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

how to solve F and G? G looks like n^3 DP.. Don't know how to implement though

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +46 Vote: I do not like it

    G Solution:

    Define the dp state to be $$$dp(i, j, k)$$$ which holds the minimum number of paint moves we can make from the first $$$i$$$ cells such that the $$$j$$$'th cell is the leftmost unpainted cell, and the $$$k$$$'th is the rightmost painted cell. Transitions are trivial, and it runs in $$$O(n^3)$$$.

    What is the meaning behind these states?

    Let's say we perform moves in increasing order of their positions. It's never optimal to paint to the left, if the current moves left painting range doesn't paint the currently leftmost unpainted cell. So, this is why we store the position of this as a parameter in our state.

    As for the rightmost painted cell, we store this because some moves cover cells to their right. If the rightmost painted cell $$$k$$$ is $$$> i$$$, then all cells in $$$[i, k]$$$ will already be painted, so its suboptimal to paint to the right if we dont paint beyond $$$k$$$.

    245121073

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

      If the rightmost painted cell $$$k$$$ is $$$>i$$$, then all cells in $$$[i, k]$$$ will already be painted

      Why is that so? If $$$k$$$ is the rightmost painted cell, doesn't that mean all cells between $$$i$$$ and $$$k$$$ are unpainted?

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

        We perform moves in increasing order of cell position. If cell $$$k$$$ ($$$> i$$$) is the rightmost painted cell when we reach cell $$$i$$$, this means that the cell $$$k$$$ was painted due to us performing a "right paint" move at some cell $$$l$$$. $$$l < i$$$ must hold because of the increasing order restriction. This means that $$$min(n, l + a_l - 1) = k$$$, and we painted the range $$$[l, k]$$$. Since $$$l < i < k$$$, all cells in $$$[i, k]$$$ must be painted.

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

      Can we do that in O(N^2)? dp(i,j) is the answer for the first i cells such that you don't need to care about the last j cells ( it's already painted by some magic). My alt account submission: 245230420

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

    F Solution : It's obvious that we check for each edge if it is contained in any cycle. Then take the minimum.
    Here's how to find. Sort the edges by descending order of weight. Then using DSU. If u and v are from same component, edge u -> v will be contained in a cycle. Just take the minimum of all edges and do a simple DFS.

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

Very nice G, thanks for this problem!

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

Could anyone please explain how to do problem D? Is it a segment tree problem, or there is another way to solve it?

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

    kind of "prefix sums" is the way to go. I iterated thru array, saving last element before ith which is different from ith. (remember: you do not need a segment tree 99% sure UNLESS you have problem in which there both change and ask queries.)

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

    one idea is to pre-calculate the 'nearest distinct' left and right element for every index 'i'

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

      Only calculating distinct rights is enough. Then, for L to R query. check if the right[L] is <= R. If yes then you got your answer at a[L] and a[right[L]]. Else, -1

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

    Consider forming an array $$$s$$$, where $$$s[i]$$$ represents the starting index of $$$i$$$'th segment of input array with all same sequential numbers. Then, for each query binsearch $$$l$$$ and $$$r$$$ in $$$s$$$, to get the segments in which this indecies are located. Let the starting positions of our segments be $$$li$$$ and $$$ri$$$. If $$$li = ri$$$, there is no different elements in this range and the answer should be -1 -1. In other case, we just take positions $$$ri-1$$$ and $$$r$$$. This will guarantee us to choose two different elements.

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

    u can use mono stack to calculate the nearest greater and smaller element from right for every element then u only need to pick l and nearest greater element for l or l and nearest smaller element than l from right (if possible)

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

In problem E I saw that we have to make arrange in following way:- at ith pos place x and at i+kth pos place x+1 but how do we implement this? am i thinking in the right way?

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

Don't want to say it but todays CF Site was crashing so badly, the lag was too much.

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

Can someone explain why my D submission is getting "Idleness limit exceed"? 245216005

»
3 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it
My solution for problem D
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +35 Vote: I do not like it
    Wait till you find out that guys have used...
    and...
»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I dont understand why WA on C??? Gosh!!

void sol() {

cin >> n >> m >> k;
for(int i=1;i<=k;i++) ha[i] = hb[i] = 0;
int siza = 0, sizb = 0, sizq = 0;

for(int i=1;i<=n;i++){
    cin >> a[i];
    if(a[i]>=1 && a[i]<=k && !ha[a[i]]) ha[a[i]]++, siza++, sizq++;
}

for(int i=1;i<=m;i++){
    cin >> b[i];
    if(b[i]>=1 && b[i]<=k && !hb[b[i]]) hb[b[i]]++, sizb++;
    if(b[i]>=1 && b[i]<=k && !ha[b[i]]) sizq++;
}
if(sizq == k){
    if(siza>=k/2 && sizb>=k/2) cout <<"YES\n";
    else cout << "NO\n";
}else cout << "NO\n";

}

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

    Your code seems to be incomplete hard to tell what's wrong. What is ha? A hashmap?

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

      yep, I use ha[i] to note down whether i has appeared in the a sequence, and then i use the siza/sizb to count the numbers of the elements ranging from 1~k that appeared in the a/b sequence. sizq is the tot number of the appeared 1~k. I think this would work:(

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

    Your code will fail in this test case.

    1
    6 6 2
    1 1 1 1 1 1
    2 2 2 2 2 2
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The result comes to NO, I think this is not a hack, I still dont understand why my code will fail:(

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

        You don't update the ha[b[i]] so it may be add to sizq more than once.

        For example in this test case your code will assign sizq = 7 but the correct value is 2 so your code will print NO but the correct answer is YES....

        1
        6 6 2
        1 1 1 1 1 1
        2 2 2 2 2 2
        

        to solve this problem only you need to update ha[b[i]]

        if(b[i]>=1 && b[i]<=k && !ha[b[i]]) ha[b[i]]++, sizq++;
        
»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

Why my solution of D didn't pass , its time complexity was (N^3)*Q , which would be 10^19 operations , which i think can be performed in 5 seconds ?

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

Solved F at 20:02 :(

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

my solution for G:

First I call dp[i][k] is the minimum number of charges we need to painted all cells from 1 to i without using charge in k_th cell

dp[0][k] = 0 (k in range(1 to n)), and I calculate dp from left to right

Suppose that we are considering position i , there are two cases :

*. We using charge in this current cell i:

  • the answer for this case is min(dp[j][k]) <for j from min(0 , i — a[i]) to i-1 ,and for any k>

  • this answer contribute to any dp[i][k] with k!= i

*. We not using charge in this current cell i:

  • we consider only j < i which j + a[j] — 1 >= i , so the answer for this one is dp[j-1][with any k] or dp[j' from j to i-1][j]
  • this answer contribute to any dp[i][k] with k != j

The final answer is min(dp[n][k]) with k from 1 to n

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

This is one of the wonderful div3 rounds ever!

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

A possible solution for F.

The edge we're looking for is the lightest edge not in the maximum spanning forest.

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

    can u explain your solution for problem F please?

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

      The main idea is that if you put in an edge into a tree then you would create a loop. Try to greedily create a forest using the heavy edges so that you can "put in" the light edge after to create a loop.

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

Great contest! But unfortunately I struggled with problem F because I wasn't familiar with finding bridges using biconnected components. As a result, I couldn't solve problem G, which required a complexity of $$$O(n^4)$$$ for interval dynamic programming during the contest.

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

    Using DSU to enumerate the minimum edge and reconstruct the entire graph would provide a better approach to determine if a specific edge is not a bridge.

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

Can anyone give an upper bound on total number of cycles in a graph if number of nodes are 2e5 and edges are also 2e5?

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

    a complete graph on $$$\sqrt {2 \cdot 10^5}$$$ vertices with about $$$2 \cdot 10^5$$$ edges, number of simple cycles will be something like $$$\sqrt{2 \cdot 10^5}!$$$ i guess

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

      And what would be an upper bound on total sum of length of all simple cycles?

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

        every cycle has length $$$\le \sqrt {2 \cdot 10^5}$$$, and the average lenght is $$$\frac{\sqrt {2 \cdot 10^5}}{2} = \sqrt {5 \cdot 10^4}$$$, so i think it will be something like $$$\sqrt {2 \cdot 10^5}! \cdot \sqrt {5 \cdot 10^4}$$$

»
3 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Problem C sucked.I did a solution with O(k) which K can be min(n,m) and it gave time limit.

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

    I think your solution got TLE because you init a vector of size 1e6 for every test case

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

      That's usually not a problem

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

        Well, it should be, if you have $$$10^4$$$ test cases and in each one you're initializing a vector of size $$$10^6$$$, that's going to be about $$$10^{10}$$$ operations in total. Way too much!

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

          Oops, my bad, there's usually a constraint along the lines of: The sum of k over all test cases does not exceed 2e5, and it seems like that is not the case in problem C

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

            Actually it's not about that constraint at all, even if k = 2 for every test case then his code will still get TLE

            In his code, he is using the constant 1e6 to init a vector of that size

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

Can G be solved with linear dp in O(n ^ 2)?

»
3 weeks ago, # |
  Vote: I like it -42 Vote: I do not like it

Problems were too easy lol

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

Code for Problem-B using (PyPy 3.9.10 (7.3.9,64bit)) gives TLE but The same code using (Python — 3) gets Accepted

PYPY -> https://codeforces.com/contest/1927/submission/245228008
Python3 -> https://codeforces.com/contest/1927/submission/245231853

It happened during the Contest. Could someone please explain?

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

This contest was awesome!

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Is this round rated or not ?

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

It is very nice round for me. I want there to be more such rounds. MarkMirzayanov you made the best platform for coders.

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

Can't Figure out why my solutions failed in test 34 in G :"

IF anyone may helppp

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

Thank you for the round, and all youve done for CP. The questions were great, solved 5 out of 7. Hopefully ill expert after this round. ;)

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

Glad to see you in our city!

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

I wonder why I was not marked as "qualified" participant. I participated in at least 6 rated rounds, solved at least one problem in each of them and yet this round is not rated for me. Why is that?

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

Why K is even in E?

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

    Ignore.

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

      Not impossible exactly but not always possible
      $$$[1,6,3,2,5,4]$$$ $$$k=3$$$
      The constraint was probably put to make it suitable for Div3 E

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

        Can you give example of a impossible case?

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

          $$$n=7$$$ , $$$ k=3$$$

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

            Ahh , now i get it for odd length 2 increase will come consecutively , where in even length +-+-.... will continue.

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

    to make sure equal amount of elements come from each array

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

One Burger versus many potatoes

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

If I succesfuly hack a submission made after the contest finished, will the testcase be used for testing later ?

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

i liked this round a lot.

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

Timing! I'm visiting Georgia with a friend next month. That burger indeed looks delicious! Any food/travel suggestions Mike? What's that burger called by the way? The place/ restaurant name?

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

Mike, please Consider one suggestion. Earlier codeforces was very good in terms of no. of contests per week but now it is becoming close to 1 contest a week. please improve this. we want 3 contests per week atleast....please... this would also increase the participation of many users on Codeforces. Kindly consider this suggestion and do the needfull

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

The contest was as great as Mike

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

题目很好,下次继续

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

C:Choose the Different Ones!

If I don't add 'for(int i=1;i<=k;i++) a[i]=b[i]=0;', I will encounter the error 'Time limit exceeded on test 2'.I am a beginner, and I would like to understand the reasons behind it.Thanks.

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e6 + 10;
int main() {
    int t;
    scanf("%d", &t);
    while(t--){
        int a[N],b[N];
        int n,m,k,x;
        scanf("%d%d%d",&n,&m,&k);
        for(int i=1;i<=k;i++) a[i]=b[i]=0;
        for(int i=1;i<=n;i++){
            scanf("%d",&x);
            a[x]=1;
        }
        for(int i=1;i<=m;i++){
            scanf("%d",&x);
            b[x]=1;
        }
        bool flag=false;
        int at=0,bt=0;
        for(int i=1,j=k;i<j;i++,j--){
            //printf("%d ",a[i]);
            if(a[i]==1){at++;}
            if(a[j]==1){at++;}
            if(b[i]==1){bt++;}
            if(b[j]==1){bt++;}
            if((b[i]!=1&&a[i]!=1)||(b[j]!=1&&a[j]!=1)){
                flag=true;
                break;
            }
        }
        //cout<<at<<" "<<bt<<endl;
        if(at<k/2||bt<k/2){
            flag=true;
        }
        if(flag){
            puts("NO");
        }else{
            puts("YES");
        }
    }
    return 0;
}
  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Generally, there may be some optimizations from the compiler that can make the code run much faster

    In this case, I'm guessing that in the AC version of your code, the compiler doesn't allocate new arrays a and b for every test case (It allocates once, then uses them for every test case)

    And in the TLE version of your code, the compiler does allocate new arrays for every test case

    In my opinion, to avoid this kind of issue, you shouldn't do int a[N],b[N]; for every test case, but rather just allocate it once first (Before the while loop), then at each test case, you just need to initialize the arrays, from index 1 to k

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

I have an approach for F but I've been unable to prove/disprove it... Can somebody please help me out?

My idea is to first negate all edges and find the Minimum Spanning Forest using Kruskal's algorithm. After that, I go through the edges with maximum negative weights (i.e. min weight edges of the original graph) and check if both vertices of the edge lie in the same component or not (using the disjoint sets resulting from Kruskal's)

Is this correct? I intuitively feel it's right but I'm unable to mathematically prove this.

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

    You are actually doing the same thing as the approach mentioned here

    The pr