MikeMirzayanov's blog

Codeforces Round 923 (Div. 3)
By MikeMirzayanov, 11 months 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://mirror.codeforces.com/blog/entry/125597 (thank you, Vladosiya).

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

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

As a Participant, I would recommend to participate.

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

omg MikeMirzayanov round

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it -137 Vote: I do not like it

fdgdfg

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

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

    → Reply
  • »
    »
    11 months 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.

    → Reply
    • »
      »
      »
      11 months ago, # ^ |
      ← Rev. 2   Vote: I like it -49 Vote: I do not like it

      dfsdf

      → Reply
      • »
        »
        »
        »
        11 months 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

        → Reply
      • »
        »
        »
        »
        10 months 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

        → Reply
»
11 months 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

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

My last rated Div 3

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

My first unrated div3

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

First time testing :D, wish you high delta.

→ Reply
»
11 months 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!

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

    Even if you win the contest that is impossible.

    → Reply
    • »
      »
      »
      11 months 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)

      → Reply
  • »
    »
    10 months 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

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

I think it's the 100th div3.

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

good luck!

→ Reply
»
11 months 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 :)

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

GOOD LUCK ! everyone

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

MikeMirzayanov is a Barcelona fan

→ Reply
  • »
    »
    11 months 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.

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

    That t-shirt says "Barcelona University".

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

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

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

hope reach pupil after the round

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

Did you use divide and conquer algorithm before eating ?

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

that burger looks yum

→ Reply
»
11 months 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

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

    Sir, this is a Wendy's

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

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

    → Reply
    • »
      »
      »
      11 months 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

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

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

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

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

      → Reply
»
11 months 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!

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

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

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

gemrielad miirtvit, MikeMirzayanov

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

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

→ Reply
»
11 months 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!

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

Can't wait to become an Expert

→ Reply
»
11 months 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!

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

Good luck! Rating increase!

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

go georgia!

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

As a Participant , i love burger

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

I`m sigma

→ Reply
»
11 months 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.........

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

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

    → Reply
  • »
    »
    11 months 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)

    → Reply
  • »
    »
    11 months 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

    → Reply
    • »
      »
      »
      10 months 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

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

GIGACHAD Mike Mirzayanov round HOLY PogU

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

time to become pupil!

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

n

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

Damn that Burger looks good!

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

what a juicy burger in this morning i woke up

→ Reply
  • »
    »
    10 months 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 ?

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

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

      → Reply
»
11 months 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.

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

    Then they would be inaccessible to European and Asian students.

    → Reply
»
11 months 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.

→ Reply
»
11 months 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
→ Reply
  • »
    »
    11 months 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.

    → Reply
»
11 months 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!

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

My first unrated Div3

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

pedrolino GOAT

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

No way, 74TrAkToR comeback

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

Calling specialist.I need 14 point.

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

The burger looks delicious

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

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

→ Reply
»
11 months 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.

→ Reply
»
11 months 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)

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

I hope to get a good score.

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

hope i can reach pupil this time :p

→ Reply
»
11 months 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!

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

hopefully this will be my come back contest

→ Reply
»
11 months 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

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

I want to eat burger too.

→ Reply
»
11 months 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)

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

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

→ Reply
»
11 months 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.

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

Eden Hazard round.

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

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

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

This will be my first rated round.

→ Reply
»
11 months 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..

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

UPD: I found great burgers in Tbilisi!

So where? :) Bon appetit!

→ Reply
»
11 months 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

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

@ZettaByte

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

Yeah MikeMirzayanov Round!!

→ Reply
»
11 months 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!

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

DelayForces.

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

1 Refresh = 10 minutes delay

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

Ah shit, here we go again

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

DelayForces... Again

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

10 minutes delay?

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

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

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

Again and again and again.

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

fr!?

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

Beginning time 22:35 -> 22:45?

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

Delayforces again :(

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

delay:<

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

why delayed

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

Why the ten minute delay?

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

Not a 10 min delay again!

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

Wow, is the man who eating hanburgers MikeMirzayanov?

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

Delayyyyy

Anyways, hope to become a green lantern today

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

Nah, I'd win.

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

delayForces

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

wait what?? 40k participants??

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

The contest is going to be QueueForces

→ Reply
»
11 months 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?

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

41k+ participation ?

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

Queueueueueueueueueueueueueue...

→ Reply
»
11 months 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 :(

→ Reply
  • »
    »
    11 months 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

    → Reply
  • »
    »
    11 months 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

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

omg you were in Georgia?

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

Good contest, Good Problems.

→ Reply
»
11 months 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?

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

It was a wonderful contest

→ Reply
»
11 months 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.

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

What's the best way for construction E?

→ Reply
  • »
    »
    11 months 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

    → Reply
  • »
    »
    11 months 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, ...}$$$

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

How to solve E ?

→ Reply
  • »
    »
    11 months 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$$$

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

      Helpful Explanation.

      Code's Here:
      → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

    I solved F but couldn't solve E

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

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

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

Why does Mo TLE for D ?

→ Reply
  • »
    »
    11 months 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.

    → Reply
    • »
      »
      »
      11 months 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.

      → Reply
      • »
        »
        »
        »
        11 months 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)$$$.

        → Reply
        • »
          »
          »
          »
          »
          11 months 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

          → Reply
    • »
      »
      »
      11 months 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.

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

        Oh yeah, you are right. Sorry.

        → Reply
      • »
        »
        »
        »
        10 months 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 ?

        → Reply
        • »
          »
          »
          »
          »
          10 months ago, # ^ |
          ← Rev. 2   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_r >= l$$$ answer is $$$[nxt_r, r]$$$ , otherwise answer is $$$[-1,-1]$$$

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

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

      → Reply
  • »
    »
    11 months 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 :(

    → Reply
  • »
    »
    11 months 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).

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

speedforces

→ Reply
»
11 months 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

→ Reply
  • »
    »
    11 months 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.

    → Reply
    • »
      »
      »
      11 months 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

      → Reply
      • »
        »
        »
        »
        11 months 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

        → Reply
        • »
          »
          »
          »
          »
          11 months 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

          → Reply
    • »
      »
      »
      11 months 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

      → Reply
»
11 months 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 💩

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

    i used two pointers but got TLE

    → Reply
    • »
      »
      »
      11 months 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)

      → Reply
  • »
    »
    11 months 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

    :<(

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

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

→ Reply
  • »
    »
    11 months 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

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

→ Reply
  • »
    »
    11 months 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.

    → Reply
    • »
      »
      »
      11 months 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

      → Reply
      • »
        »
        »
        »
        11 months 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.

        → Reply
    • »
      »
      »
      11 months 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?

      → Reply
      • »
        »
        »
        »
        11 months 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.

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

    Thanks bro ! Appreciate it.

    → Reply
  • »
    »
    10 months 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

    → Reply
    • »
      »
      »
      10 months 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.

      → Reply
      • »
        »
        »
        »
        10 months 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.

        → Reply
  • »
    »
    10 months 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://mirror.codeforces.com/contest/1927/submission/245472637

    → Reply
»
11 months 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

→ Reply
  • »
    »
    11 months 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.

    → Reply
  • »
    »
    11 months 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

    → Reply
  • »
    »
    11 months 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.

    → Reply
»
11 months 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

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

How to solve E?

→ Reply
  • »
    »
    11 months 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)

    → Reply
  • »
    »
    11 months 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 :).

    → Reply
»
11 months 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.

→ Reply
»
11 months 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.

→ Reply
»
11 months 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

→ Reply
  • »
    »
    11 months 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

    → Reply
    • »
      »
      »
      10 months 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?

      → Reply
      • »
        »
        »
        »
        10 months 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.

        → Reply
    • »
      »
      »
      10 months ago, # ^ |
      ← Rev. 6   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).

      → Reply
  • »
    »
    11 months 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.

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

Very nice G, thanks for this problem!

→ Reply
»
11 months 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?

→ Reply
  • »
    »
    11 months 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.)

    → Reply
  • »
    »
    11 months 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'

    → Reply
    • »
      »
      »
      10 months 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

      → Reply
  • »
    »
    11 months 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.

    → Reply
  • »
    »
    10 months 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)

    → Reply
»
11 months 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?

→ Reply
»
11 months 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.

→ Reply
»
11 months 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

→ Reply
»
11 months ago, # |
  Vote: I like it +29 Vote: I do not like it
My solution for problem D
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +35 Vote: I do not like it
    Wait till you find out that guys have used...
    and...
    → Reply
»
11 months 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";

}

→ Reply
  • »
    »
    11 months 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?

    → Reply
    • »
      »
      »
      10 months 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:(

      → Reply
  • »
    »
    10 months 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
    → Reply
    • »
      »
      »
      10 months 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:(

      → Reply
      • »
        »
        »
        »
        10 months 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++;
        → Reply
»
11 months 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 ?

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

Solved F at 20:02 :(

→ Reply
»
11 months 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

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

This is one of the wonderful div3 rounds ever!

→ Reply
»
11 months 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.

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

    can u explain your solution for problem F please?

    → Reply
    • »
      »
      »
      11 months 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.

      → Reply
»
11 months 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.

→ Reply
  • »
    »
    11 months 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.

    → Reply
»
11 months 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?

→ Reply
  • »
    »
    11 months 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

    → Reply
    • »
      »
      »
      10 months 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?

      → Reply
      • »
        »
        »
        »
        10 months 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}$$$

        → Reply
»
11 months 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.

→ Reply
  • »
    »
    11 months 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

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

      That's usually not a problem

      → Reply
      • »
        »
        »
        »
        11 months 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!

        → Reply
        • »
          »
          »
          »
          »
          11 months 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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months 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

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

              downvoted for being correct ?! my condolences

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

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

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

Problems were too easy lol

→ Reply
»
11 months 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://mirror.codeforces.com/contest/1927/submission/245228008
Python3 -> https://mirror.codeforces.com/contest/1927/submission/245231853

It happened during the Contest. Could someone please explain?

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

This contest was awesome!

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

Is this round rated or not ?

→ Reply
»
11 months 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.

→ Reply
»
11 months 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

→ Reply
»
11 months 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. ;)

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

Glad to see you in our city!

→ Reply
»
11 months 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?

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

Why K is even in E?

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

    Ignore.

    → Reply
    • »
      »
      »
      11 months 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

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

        Can you give example of a impossible case?

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

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

          → Reply
          • »
            »
            »
            »
            »
            »
            10 months 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.

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

    to make sure equal amount of elements come from each array

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

One Burger versus many potatoes

→ Reply
»
10 months 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 ?

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

i liked this round a lot.

→ Reply
»
10 months 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?

→ Reply
»
10 months 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

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

The contest was as great as Mike

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

题目很好，下次继续

→ Reply
»
10 months 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;
}
→ Reply
  • »
    »
    10 months 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

    → Reply
»
10 months 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.

→ Reply
  • »
    »
    10 months 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 proof is based on the idea that if the edge you are adding to a component already has both of its endpoints, then it must be part of a cycle. Since, we want the minimum weight edge to be in a cycle, we go over the edges in decreasing order of their weights.

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

I solved abcd. I hope to become specialist in this round. Fingers crossed.

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

Wait I have just missed a MikeMirzayanov round?

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

Problem G was fantastic problem!!!

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

TestCase for D were really not good. During contest my q*n solution got accepted. And after that someone hacked it. I didn't realise during the contest that what I was coding was q*n, if I would have got TLE, it would have been fairly easy to code up O(q) solution.

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

    try binary search next time,that will give you good luck ^v^

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

One useless assert case in my code make me unable to AC problem $$$F$$$ :( poor me forget to not check for assert when there is no cycle.

RTE submission

AC submission

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

What's the approach for G?

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

is that coffee ?

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

look at those lemons are so juicy

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

Hello my friends Since the contest does not have a tutorial yet, I am very curious to know What's in MikeMirzayanov's cup? He is drinking coffee with hamburger!!! Should we use dp or data structures to solve this problem?

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

Can someone answer for me: why do I get the wrong result in problem F by determining whether the points of an edge are on the same edge-connected component after ordering the edges by their weights?

Here is my code: https://mirror.codeforces.com/contest/1927/submission/245298631

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

Rating update when ?

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

For D, we can report the index with the minimum value and the index with the maximum value as a general answer. If the values stored at both these indices are same we report (-1, -1). We can maintain two sparse tables to answer queries in O(1) time (just like range minima queries). Overall time complexity would be O(nlog(n) + q)

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

    There exist a much easier linear time solution using dp.
    Let dp[i]:= minimum index j such that j>i and a[i]!=a[j].
    Now transitions are
    If a[i]!=a[i+1]
    dp[i]=i+1
    else dp[i]=dp[i+1].

    Now to answer each query just check if dp[l]<=r then answer is {l,dp[l]} else {-1,-1}

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

Mike, I suggest you to taste 'Khinkali', really amazing Georgian dumpling.

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

who can help me with problem B plz !! i need source code :<<

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

    you can maintain an array b[26] of length 26 for each alphabet a-z and initialize it with 0. This will contain the frequency of the alphabets till now.. for every new a[i] you need to find the first alphabet with the a[i] frequency and add that alphabet to your answer. then you need to increase the frequency for the alphabet in the array b. Doing this for all i 0-n, you will get the required answer. (sorry for bad English. Hope you understand.)

    here is my solution for problem B

    https://mirror.codeforces.com/contest/1927/submission/245106024

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

me too barcelona fan.

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

My first rated competition. I have solve A~F problems. It's a good experience for me.

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

    u funny

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

    How I envy you! At first, I thought I could solve all A-F too, but my D question was FST because of my carelessness about time complexity.

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

      Oh, in fact, my F has been hacked beacause I used a segment tree and it's to slow/

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

My solution to problem B was accepted during the contest but now it says "In Queue" why is it?

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

    its going to be judged again against more test cases, its a normal thing

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

      how long until its done testing?

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

        for now its already taking much longer than the usual but you can see the percentage done if you entered the contest page

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

Too much slow system testing

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

Can you please tell me the name of the place you got the burger?

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

Slowest System Testing in the history of codeforces?

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

why there is no rating change even after a day of the contest? is this normal or there is something wrong?

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

    There is system testing after the contest. And it will finish in a moment.

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

      but normally system testing takes an hour or something why it is taking so long this time?

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

why there is no change in rating even though the system testing is done?

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

    seems there are multiple users above 1600 rating so it might be a reason that rating changes is taking time as they are not going to be considered.

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

Can someone tell me the solution of problem G. After a busy day and solving the first A-F, my mind stop working and I didn't got any ideas for it.

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

Can someone Explain F?

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

    The key point is that: How to judge if an edge is in (at least) a cycle.
    Firstly, we sort all edges by there weight, descending. And we suppose that there is no edge in a graph.
    DSU is also used. At first each vertice's father is their own.
    Then, we add the edges to the graph one by one. As we have sorted it, lighter one will be added later. And each time we add an edge to the graph, we use DSU to judge if the two vertices have been belong to the same unit. If not, unite them, or we know that if we add this edge we will build a cycle.
    Once we build a cycle, we record this edge. As we sort all edges descending, after we doing this to all of the edges, we will record the lightest edge in a cycle. The edges have less weight than it are not included by cycle so we don't need to consider them.
    After this, using dfs to find a cycle. It's easy.
    Sorry if my explain is bad.

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

Thanks Mike, my rating increased a lot

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

it is hard for me！

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

Why my rating is decreased although I solved 2 questions(A,C)

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

    Your performance is below that expected for a contestant at your rating

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

      But someone has also solved same questions. Also my rating is less than him and his rank is lower then me

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

I received a message and it states that my solution was same with the some other participants. I have used ideone as I recently changes my browser from "GOOGLE CHROME" to "BRAVE BROWSER" and I didn't change the status public to private. I use many functions so that when the code of others may not be similar to mine but I don't know how my code matched with them. But I am sure I can explain the code that I have written and very confident about it. So, I request to not block my account or penalize my rating. I am very confident that I can explain my every line of code I have written and every method I used.

So, I kindly request to dont block my account and dont give a penalty. I can give my word that again I dont use ideone anymore in my entire life.

thank you

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

I recently received a message stating that my solution matched with some other participants', likely due to inadvertently leaving my code's status as public on Ideone after switching browsers. Despite this, I am confident in my code's originality and can explain every aspect thoroughly. I kindly ask not to have my account blocked or receive a penalty, as I assure you of my commitment to avoiding similar incidents in the future. Thank you for your understanding.

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

hello i just got a message from codeforces that my solution matches with my friend.I just want to clarify that we have studied from the same course (https://vimeo.com/channels/demuxwinter21/page:3) offered by a startup named demux academy where we have studied the logic of oredered map and lower bound and discussed similar examples in theroy while being in same class...but now as the startup has been closed i cant share the class videos but we have same notes..so thats why our solution matches somewhat i guess...plz look forward in this matter as it really affects me.

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

Hello! I recently received a message stating that my solution(E) matches with some others. I can assure you of the originality of the solution and can explain every part. It might be possible that the flow of my solution is similar to others' but as you can see with my account all my codes are my own creation. I kindly request to not block or impose penalty on this account as I really love giving contest here! (Plus My other solutions are good to go; why these are skipped?)

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

Hi MikeMirzayanov

I am using OnlineGDB common compiler source that why I recieve a cheat submission please help and get rid of this I will keep in mind next time i use that platform

It will release my code to public

thanks

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

I am my friend ambaliyashovardhan wrote from the same template but it says that they have detected from the plag check. I insist that we have have not done the same code and it has to be a pure coincidence please look into it. I really love giving contests here and i didnt not want to be flagged for this as i can explain each part of the code as it mine and i can strongly say that it is just a complete coincidence. Ill make sure to change the template and all thank you

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

Why my DFS in F TLE in Test19 https://mirror.codeforces.com/contest/1927/submission/245777873

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

[contest:923]Recently, I received a notification indicating that my solution matched with another participant’s. This likely occurred because I unintentionally left my code’s status as public on Ideone after switching browsers. However, I want to emphasize that my code is genuinely original, and I can provide a thorough explanation for every aspect of it. I kindly request that my account not be blocked or penalized, as I am committed to avoiding similar incidents in the future. Thank you for your understanding.

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

Where is my rating?? :(

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

Why #251324802 gives memory exceeded limit in Problem F

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

    At a glance, I think passing path by value (instead of referencing) into searchPoints() will cause the vector to multiply itself massively in deep recursive calls (specifically if the graph is a very long chain), causing MLE quickly since at worst memory consumption would quadratically rise.

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

Why just a dfs gives TLE on Test#35 since in test 35 the answer is 2 66666 that means i just have to find one cycle . https://mirror.codeforces.com/contest/1927/submission/251404664

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

I'm sorry to bother you, in the round 934(div 2) my rating is abnormal. Specifically, my C problem was missed in testing. I sent a private message for Mike, but it seems he didn't see it. So I published this comment hoping to get attention. I may not be very familiar with the evaluation mechanism of CodeForces. I don't know any other ways to solve that. excuse me, thanks. >_<

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

hey MikeMirzayanov what is this partial behaviour towards flagging solutions.

This user -> sjy is out of competition for the solution: https://mirror.codeforces.com/contest/1974/submission/261826313 but i also noticed the solution of this user -> frank11_sjy who is not out of the solution even having a very similar solution just variable name changed and some comments added and even submitted later; this is his solution https://mirror.codeforces.com/contest/1974/submission/261825867 the entire nested for loop is same with same indentation. Man he needs to get out of contest, you are doing very wrong and people's trust will reduce from this platform. Please get him out of competition.

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

    This kind of thing happened and I hope 945div3 doesn't give me a rating, but no one seems to care about this game anymore

    → Reply