sevlll777's blog

Codeforces Round 860 (Div. 2)
By sevlll777, 20 months ago, translation, In English

Hello Codeforces!

I am happy to invite you to Codeforces Round 860 (Div. 2), which will be held on Mar/26/2023 17:35 (Moscow time).

This round will be rated for participants with rating lower than 2100. Participants with a higher rating are invited to participate in the round unofficially.

You will be given 6 problems and 120 minutes to solve them. All problems were authored and prepared by me.

The traditional thanks-list to everyone who took part in the creation of the round:

🤴 DishonoredRighteous for coordinating the round

🐞 gyh20 for black-red testing of the round

😈 feecIe6418, iakovlev.zakhar, Dart-Xeyter, Adam_GS, ShuiLaoshi, golikovnik, Gary2005 for red testing of the round

🐫 NemanjaSo2005, Alexdat2000, Kon567889, tem_shett for orange testing of the round

👾 SlavicG, Psychotic_D for purple testing of the round

🐳 C2A, Masha237, ayhan23, Khonshu08, Brahma_tet for blue testing of the round

👽 Lord_David for green testing of the round

🦄 mejiamejia for help with testers for the round

🤡 sevlll777 for the problem, without which the round would be unbalanced, and the problems that were not included in the final problemset

🎅 MikeMirzayanov for the amazing Codeforces and Polygon platforms
ㅤㅤㅤㅤ

Personal recommendations

I sincerely hope that you will find the problems interesting and you will enjoy solving them. Good luck!

Score Distribution:

500 — 750 — 1250 — 1750 — 2250 — 3000

UPD: Editorial

UPD2: Congrats CHAMPIONS!

Unofficially:

  1. jiangly

  2. A_G

  3. neal

  4. maspy

  5. turmax

Officially:

  1. satyam343

  2. Sunnatov

  3. RGB_ICPC7

  4. amirhoseinfar1385

  5. vbgladkikh

First AC:

A: nifek

B: AHappyPotato

C: AHappyPotato

D: aryan12

E: lebowski998

F: zihouzhong

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

Comments Comments (185)
| Write comment?
»
20 months ago, # |
  Vote: I like it +97 Vote: I do not like it

As a tester, I recommend you try every problem.

PS: sevlll777 tried a lot to make a good round for you guys.

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

It isn't at the main page after 7 hours, wow...

As a tester, I'm a little surprised :)

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

Cyan tester?

→ Reply
»
20 months ago, # |
  Vote: I like it -166 Vote: I do not like it
✅ Maximize your enjoyment of the contest, not your rating after it

Sounds like a bad round in advance.

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

    After my own participation in this contest, I found your statement wrong.

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

1750 problems are rather rare these days.
Kudos to authors for having them

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

    You know what it means right !!!!!!. It's now time to solve four questions this time. Hahaha

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

Red round

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

I have one rating point left to raise to Specialist, I sincerely hope that I will raise it this round.

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

    I was at that once. You can do it!

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

    Do not think about it during contest. I repeat don't. Just solve problems with accuracy. It's ez.

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

Since this round is rated for only participants below 2100, I don't see why legendary grandmasters are required for testing.

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

    Legendary grandmasters have more experience than anyone else. They will probably be much better at pointing out things like if a problem has appeared before, if there exists a stupid data structure brute force, if the authors' intended greedy is incorrect and the problem is actually unsolvable, etc.

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

Hopefully my CM contest

I followed the author long time ago because his codes are brilliant and clean so I'm expecting some great problems tomorrow < 3

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

This amount of emojis makes me die inside

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

Emoji round

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

How can one become a tester?

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

I am eagerly waiting for this contest...I think I will reach PUPIL by this contest....Let's Hope for the best....I will definitely never give up even I cant make my name green....

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

Early Score Distribution!

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

As a blue tester, best contest I have ever seen!

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

On the behalf of the specialist community i would like to say this time D is 1750. And you lot know what it means right!!

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

As this is my first testing round, I'd like to thank sevlll777 for giving me this opportunity. It was a lot of fun for me.

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

In div2 contest!

me BEFORE CONTEST
me AFTER CONTEST is over!
→ Reply
»
20 months ago, # |
  Vote: I like it -11 Vote: I do not like it

Wishing all the best to everyone,

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

Participants with a higher rating are invited to participate in the round unofficialy.

Should be:

Participants with a higher rating are invited to participate in the round unofficially.

Update:Fixed.

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

    ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡀⣀⣀⣀⣀⣀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣠⣴⣞⠉⠉⠀⠀⠀⠀⠀⠀⠀⠈⠉⢑⣶⣤⣀⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⣤⣶⣾⣿⣿⣿⣿⣧⠀⠀⠀⠀⠀⠀⠀⠀⠀⠰⣿⣿⣿⣿⣿⣶⣤⣀⢀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣤⣴⣤⣤⣤⣤⣤⣤⣤⣤⣤⣴⣶⣿⣿⣿⣿⣿⣿⣿⣿⣿⣥⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣽⣿⣿⣿⣿⣿⣿⣿⣿⣷⣦⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣤⣄ ⠈⠻⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⠋ ⠀⠀⠀⢹⣿⣿⣿⠛⠛⠛⠛⠛⠛⠛⢛⣛⣻⣟⣛⠛⠛⠛⠛⠛⠛⠛⢻⣿⣿⣿⣿⡟⠛⠛⠛⠛⠛⠛⠛⢛⣛⣿⣛⣛⠛⠛⠛⠛⠛⠛⠛⠛⣿⣿⣿⡏⠀⠀ ⠀⠀⠀⢘⣿⣿⣿⡀⠀⣠⠋⠉⣣⠾⣿⣿⣿⣿⣿⡟⠢⡀⠀⠀⠀⠀⣼⣿⣿⣿⣿⣿⠀⠀⠀⢠⠊⡩⢿⣿⣿⡀⠀⠀⠙⢦⡀⠀⠂⠀⠀⢸⣿⣿⣿⠀⠀⠀ ⠀⠀⠀⠀⢿⣿⣿⡇⠀⣇⠀⢰⣹⢁⣿⣿⣿⣿⣿⣿⣀⢹⠀⠀⠀⢠⣿⣿⣿⣿⣿⣿⣇⠀⠀⣇⡼⠁⣸⣿⣿⣷⣥⣀⠀⠀⢱⠀⠀⠀⠀⣾⣿⣿⡇⠀⠀⠀ ⠀⠀⠀⠀⢸⣿⣿⣷⠀⠈⠒⢺⣧⣼⣿⣿⣿⣿⣿⣿⣿⣿⠇⠀⠀⣼⣿⣿⣿⣿⣿⣿⣿⡀⠀⠈⣷⣿⣿⣿⣿⣿⣿⣿⣆⠀⢸⠀⠀⠀⢀⣿⣿⣿⠆⠀⠀⠀ ⠀⠀⠀⠀⠈⣿⣿⣿⣔⠀⠀⠘⢿⣿⣿⣿⣿⣿⣿⣿⣿⡟⠀⠀⢠⣿⣿⣿⣿⣿⣿⣿⣿⣧⠀⠀⠙⣿⣿⣿⣿⣿⣿⣿⣿⣧⠏⠀⠀⠀⣼⣿⣿⡿⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⢹⣿⣿⣿⣦⡠⠀⠀⠛⢿⣿⣿⣿⣿⡿⠋⠀⠀⣠⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣦⡀⠁⠘⢿⣿⣿⣿⣿⣿⠟⠁⠀⠀⢀⣼⣿⣿⡿⠃⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠙⣿⣿⣿⣿⣶⣤⣤⣤⣬⣽⣽⣁⣠⣦⣴⣾⣿⣿⣿⣿⣏⢉⣭⣽⣿⣿⣿⣿⣿⣶⣤⣤⣈⣩⣭⣭⣥⣤⣤⣴⣾⣿⣿⣿⠟⠁⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⡏⠙⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⢿⣿⣿⣿⣼⡏⢿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⡿⢿⠇⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢇⠀⠀⠀⣭⡙⠛⠛⠛⠛⠛⠛⠛⠛⠉⠉⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠉⠛⠛⠛⠛⠛⠛⢛⣟⠛⠉⠁⠀⢸⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⢸⡀⠀⠀⠙⠁⠀⠀⠀⠸⣿⡆⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢠⣶⠀⠀⡸⠿⠀⠀⠀⠀⡏⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⢧⠀⠀⠀⣤⡀⠀⠀⠀⠈⠀⠀⠀⢀⣴⣦⣤⠤⠤⠤⠤⠤⠤⠤⢤⣤⣶⣤⡀⠀⠀⠘⠋⠀⠀⠀⠀⠀⠀⠀⣸⠁⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠈⢇⠀⠐⠙⠃⠀⠀⠀⠀⠀⠀⠀⢻⣿⣿⡇⠀⠀⠀⠀⠀⠀⠀⠀⢹⣿⣿⡧⠀⠀⠀⠀⠀⠀⢠⡄⠀⠀⣰⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⢦⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠙⣇⠀⠀⠀⠀⠀⠀⠀⠀⣼⠋⠉⠀⠀⠀⠀⠀⠀⠀⠉⠀⠀⣰⠃⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠷⣄⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠋⠳⠶⠶⠶⠖⠒⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡜⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠈⠢⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⡴⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠳⣄⡀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣠⠔⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠉⠲⢤⣠⣀⣀⡀⠀⠀⣀⣠⡀⠀⡀⢀⡀⢀⣀⣦⣤⡾⠟⠋⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢰⣾⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⡖⠂⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠙⠛⠻⠿⠿⠿⣿⣿⣿⣿⣿⣿⣿⠿⠿⠿⠛⠋⠉⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀

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

Hope I'll turn CM soon :(

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

Leetcode went down today during the Weekly Contest. All in on codeforces now

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

As a tester. This is an actually good round. Try every problem.

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

Would it be an AI themed contest? sevlll777

Like Codeforces Round 770 (Div. 2)

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

Specialist day, I hope

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

hope rating++

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

NEW ICONS!!! Oh, wait....

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

When I am trying to login via my main account it says user is disabled by administrator? What does it mean? Is it a ban and if yes for how long or is it a bug? Like my main account wasn't being plagiarized too in recent rounds? Please do help.

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

    Please someone do help .I even registered from that account around 20 hours ago .Please help

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

      Please do look into the matter please MikeMirzayanov I have also sent you a personal message regarding this matter please do give it a read please

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

I think, C problem 3rd test case output is wrong. pack 1 and pack 5 can have same price tag.

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

    Yeah I also initially misunderstood the question wrong so that you can change the order of the candy types. Fortunately they then clarified.

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

    Price tags can only cover adjacent equal values. 1 and 5 are not adjacent.

    Even in the example the values reached are [4,4,2,4,4] and the answer is 3 not 2

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

Swap(C,D)

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

I literally took 3mins to solve D after reading it , & couldn't solve C , lol.

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

    Opposite, couldn't solve D but got the idea for C fairly quickly

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

D<<<C

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

Who else facepalmed when they saw the announcement reminding the condition that the price tags have to be continuous?

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

Ok, I obviously don't get it:)
What so obvious easy was about C and D?

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

    c is just gcd and lcm on continous segments. D is kadanes

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

My brute force solution passed the pretest of E. Weak pretest. Hope it will get FST.

Update: My solution passed system test. Weak system test. I'll uphack my solution later.

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

Anyone else thought that you can change the order of types of candies on the shelf? I wasted too much time on that :(

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

    yeah, I initially thought so too, but I reread and they specifically had [4, 4, 2, 4, 4] example.

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

    Yes and the given constraints made the problem impossible to solve if you can change the order.

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

    Yes, I thought so too, but then the announcement help me to understand!

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

    same here,but I didn't read announcement or examples :)

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

So how to solve problem D?

Construction is so hard. :(

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

    Just greedy in a somewhat stupid way. It is easy to find this way but it is not instantly obvious why it works.

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it 
      while(i<pos.size()&&j<neg.size())
		{
			if (ok==0)
			{
				int res=0;
				while(j<neg.size()&&sum>=0&&abs(res+neg[j])<k) ans[++cnt]=neg[j],sum+=neg[j],res+=neg[j],j++;
				ok^=1;
			}
			else
			{
				int res=0;
				while(i<pos.size()&&sum<=0&&abs(res+pos[i])<k) ans[++cnt]=pos[i],sum+=pos[i],res+=pos[i],i++;
				ok^=1;
			}
		}

      It is my greedy... But wrong at pretest 2...

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

        Sorry, I did not read your code but my solution was:

        First, split array to pos and neg. Also calculate number of zeros.

        Then this greedy

          ll ssum = 0, p0 = 0, p1 = 0;
  while(p0 < sz(pos) && p1 < sz(neg)) {
    if (ssum + pos[p0] < MAX) {
      ssum += pos[p0];
 
      cout << pos[p0] << ' ';
      p0++;
    } else {
      ssum += neg[p1];
 
      cout << neg[p1] << ' ';
      p1++;
    }
  }
 
  while(p0 < sz(pos)) {
    cout << pos[p0++] << ' ';
  }
  while(p1 < sz(neg)) {
    cout << neg[p1++] << ' ';
  }
  rep(i, 0, zeros) {
    cout << "0 ";
  }
        → Reply
      • »
        »
        »
        »
        20 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Input can be all zeros.

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

          oh yes, sorry, also check if is there any non-zero elements first. But I think if you don't do it you will get WA on the sample.

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

      Pretty sure it was something about Kadane's algorithm but I got too cought up in c too much

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

        So what is Kadane's algorithm?

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

          Basically a greedy algorithm that lets you find the maximum sum subarray when negative numbers are present. You keep a current score and iterate through the full array while also keeping the max score somewhere. If a number is positive, you take it and add it cause it makes score better. If there is a negative number you have 2 cases. Case one is if the score would be negative then you simply set score to 0 (because taking the number would be worse than having nothing) case 2 is if the score after adding the number would be more than zero, in that case you just add it to the score because it might be worth it later

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

          It gives the maximum sum among all of the subarray from an array.

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

    If every element is equal to zero -> no answer.

    Otherwise, group elements in two vectors: positive+zero and negative.

    You build the final array as follows: Keep a variable sum denoting the sum of all elements used up to this point.

    if sum > 0 you append the next negative value to the final array

    if sum =< 0 you append the next positive or zero to the final array

    Largest absolute value of a subarray sum is the largest absolute difference between any two prefix sums. Let max equal the largest value and let min equal the smallest value of the array. You can notice that if currently sum > 0, the next prefix sum will satisfy sum > min and if currently sum <= 0, the next prefix sum will satisfy sum <= max. This means that all prefix sums satisfy min < sum <= max. The largest possible prefix sum is thus max and the smallest possible is min + 1. The absolute difference of these is less than max - min which satisfies the problem statement.

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

      Can u tell what's wrong in my approach: What I am doing is just instead of 0, I am storing max(A) — min(A) into a variable r, then whenever abs(sum of elements + new_element) > r, then start storing elements of opposite sign and so on

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

        The maximum value of prefix sum in your case is going to be r — 1 while the minimum value of prefix sum will be -r + 1.

        The difference between both will be greater than r, which means there might be some subarray that will exceed the allowed sum r.

        I don't know how you implement it but yeah seems like this will definitely fail.

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

    Thanks all above :)

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

Was there any specific tricky case in E? I think I had an almost correct solution (with precalculation of how many correct tests we will have starting from position i using dp with memoization and maximums on suffix on result of this dp) but I have always got WA 3 :(

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

"Shocking Arrangement" is the title of problem D. Yes, indeed.

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

Did anyone else FST B on test 6?

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

    No.

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

    bruh you took an array of 50,000 elements instead of 50,001. Also it is not advisable to create that big of an array for each test case, instead use maps.

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

      Thanks for pointing out my mistake... that is so embarrassing

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

Can anyone explain how they quickly proved D? I thought about the correct greedy solution but couldn't prove it.

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

    Copied fom my previous comment:

    If every element is equal to zero -> no answer (trivial to prove).

    Otherwise, group elements in two vectors: positive+zero and negative.

    You build the final array as follows: Keep a variable sum denoting the sum of all elements used up to this point.

    if sum > 0 you append the next negative value to the final array

    if sum =< 0 you append the next positive or zero to the final array

    Largest absolute value of a subarray sum is the largest absolute difference between any two prefix sums. Let max equal the largest value and let min equal the smallest value of the array. You can notice that if currently sum > 0, the next prefix sum will satisfy sum > min and if currently sum <= 0, the next prefix sum will satisfy sum <= max. This means that all prefix sums satisfy min < sum <= max. The largest possible prefix sum is thus max and the smallest possible is min + 1. The absolute difference of these is less than max - min which satisfies the problem statement.

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

      " if sum > 0 you append the next negative value to the final array "

      What if next negative value is not available? And then only positive values are there? The sum might cross mx-mn

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

        It is guranteed that the sum of the whole array is 0.

        If currently sum > 0, we know that for the remaining elements sum < 0. This means that there must be at least one negative element left.

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

    I didn't lol. It just kinda made sense :/

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

I am not sure if this is the solution for F (didn't implement on time) but it rests on this key claim which I cant really prove or disprove: If I have a class of size k and I have at least 2*k-1 bags, I can always find a knapsack of size k divisible by k.

Suppose this is true, then its always possible and I can just take knapsack from small to big. Can anyone prove or disprove the claim?

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

My solution on C 199304839 gets TL7. I have no idea how to speed up it (without writing more optimal solution).

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

    You don't need factorization at all.

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

      I know, but I want to submit this solution.

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

        I think that it's pretty much impossible because the solution would be n*sqrt(1000000000) worst case (each ai is close to 1000000000) and since you have to do modulo it's not possible to push it that far with dirty tricks

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

          Factorization works in O(n ^ (1 / 3) * log n)

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

            Oh, that's my bad for some reason I was thinking about getting the divisors rather than factorization. But, correct me if I'm wrong, let's say you have a perfect square of a prime number isn't the factorization just sqrt(n) then

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

              In my solution I get all divisors. Number of them is O(n^(1/3)) and log from sorting

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

                Have to admit, your code is a bit confusing cause I have never seen recusrive factorization before. How exactly does recursive factorization avoid an sqrt(n) worst case?

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

        If you are interested, I have solved this problem with factorization + dynamic programming during the contest.

        My fresh 1762 ms submission after the contest

        My 2074 ms submission during the contest

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

Anyone knows why my submission for E is wrong?

https://mirror.codeforces.com/contest/1798/submission/199302004

My algorithm:

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

    Take a look at Ticket 16777 from CF Stress for a counter example.

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

So big gaps between B and C...

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

very hard problems

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

Amazing round! Really cool problems.

Screencast with commentary

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

what was the proof for problem D ..

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

    depend on your algorithm :)

    for "sort pos & |neg|, take pos and when possible take neg such that sum >= 0" consider situation when sum become too big, easy to see that it is impossible, because prev sum is at least (cur_sum — max) which is greater than |min|, therefore we could use min instead of some pos number now

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

Why is D in this position?

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

Problems were really hard. D was easier than C and C was hell of a hard problem (I understand that C was lcm and gcd, but you still had to think how to fit this operations into problem, which was not an easy task).

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

    I did solved C within 30 minutes, D costed me entire time though :(

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

    Exactly totally waste time on thinking on C :<

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

Great contest, but I personally found D easier than C. Anyone share the same thought?

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

A: For 1<=i<=n-1 check for every pair of (a[i], b[i]) if one of the following is true: (a[i]<=a[n] && b[i]<=b[n]) or (b[i]<=a[n] && a[i]<=b[n]), which is equivalent to min(a[i], b[i])<=min(a[n], b[n]) && max(a[i], b[i])<=max(a[n], b[n]).

B: Check participants reversely. We need to maintain a set of participants in the future, and from today's participants we need to find a participant which is not in the set.

C: The equivalent condition of "we can use same price tag for [L, R]" is gcd(a[L]*b[L], a[L+1]*b[L+1], ..., a[R]*b[R]) % lcm(b[L], b[L+1], ..., b[R])==0. Thus we can solve by dp: let i be the minimum index that we can use same price tag for [i, j], we let dp[j]=dp[i-1]+1. We can find such i by binary search, and we need to process range query by some data structures like sparse table.

  • Note that lcm(b[L], b[L+1], ..., b[R]) could be very large. But since the condition we check need it to be less that max(a[i])*max(b[i])=10^13, we can regard all large values as 10^13+1.

D: If all of a[i] is zero, there's no solution. Otherwise, we can ignore zeros (since they don't contribute to sum of subarrays and can be placed everywhere) and maintain the current prefix-sum. If sum<=0 we append a positive number to the array, otherwise we append a negative number until we used all numbers. Because the total sum is zero, we always have unused number with the sign we want, and every prefix-sum of the array we build is in the range [-min+1, max].

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

    C can be done with greedy. Just greedily include the next candy in the same group if gcd of all ai*bi is a multiple of lcm of all bi. This can be proven.

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

I proof by AC-d problem D lol

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

One of the best contest !

In Problem C, One fine observation can convert Binary Search Solution to Linear Solution.

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

Hello, may I ask why my D get punished while submitting again after AC

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

    That is how codeforces rules work. The following is taken from here:

    If a contestant submits several times a problem's solution that passes all pretests, then the last solution is considered as the contestant's verified solution for this problem. All other solutions will be considered as unsuccessful attempts.

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

Why does the pretset data of D not have 3e5 so I got fst?

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

    Why it must?

    → Reply
    • »
      »
      »
      20 months ago, # ^ |
      ← Rev. 4   Vote: I like it +15 Vote: I do not like it

      I think it is necessary to set extreme data on borderline cases in pretest, especially oj with hack mechanism like codeforces

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

Can someone please help explain why my code doesn't work for C? I spent over an hour debugging but it still doesn't pass the first test case.

https://mirror.codeforces.com/contest/1798/submission/199296745

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

    You literally have everything correct except for redefining R inside the loop once again...

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

      Oh wait you're right. Bruh this pisses me off so much, if I just fixed that I could've gotten C an hour in.

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

D was wayyy easier than C.

I feel dumb for not taking the 2nd suggestion seriously TwT
→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

D got FST(RE) because of the weak pretest:(

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

    It is not "weak pretest" if you write #define MAXN 200010, but n can be 300000 :)

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

      I've read the guide for problem setting on CodeForces, and it said every problem should have a pretest with maximum input size.

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

      it is my fault but I would have been corrected if the pretest had contained the boundary case

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

Problem D has weak pretest (no testcase with maximum input size)

Problem E has weak system test (allow brute force solutions)

How did they tested this contest

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

    B also doesn't have a pretest containing $$$50000$$$.

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

    Your bruteforce solution of E is non-obvious at all (to come up with). Of course it is my fault and I apologize for this, but it is really unpredictable what kind of solution human brain can come up with.

    For D there is no excuse for me, I thought I had it in pretests and not double-checked it, sorry.

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

satyam343 Orz.

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

Anyone knows why my solution to B is giving TLE?

https://mirror.codeforces.com/contest/1798/submission/199298313

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

I came up with a nlogn solution for D but unfortunately could not prove it. Can anybody please take a look? Feel free to hack if it is wrong. I just want to know whether it is correct.

https://mirror.codeforces.com/contest/1798/submission/199291200

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

In Problem B I got AC in contest but now it is showing WA on test case 12

Why?

https://mirror.codeforces.com/contest/1798/submission/199291886

it seems to be fine for me

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

    oh so Now I got AC so basically have to used long long sum instead of int sum

    but why they didnt show me WA in contest time if this was the issue

    my rating now will be highly affected by this

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

      You didn't get WA during contest because your code is only ran on pretests during a contest. This doesn't include all tests that your solution will be run on after contest, so you can only assume that your solution is probably correct.

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

I solved C with three segment tree and didn't solve D. These turn out that I don't have brain.

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

    what was your approach for C?

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

      First, consider when $$$c_l=c_{l+1}=\cdots = c_{r}$$$. The optimal $$$d$$$ is $$$d_i = \dfrac{\text{lcm}(b_l,b_{l+1},\cdots,b_r)}{b_i}$$$(according to the definition of $$$\text{lcm}$$$). Then if $$$\forall l \le i \le r ,d_i | a_i$$$, it meets the condition. Let $$$l=\text{lcm}(b_l,b_{l+1},\cdots,b_r)$$$. $$$\forall l \le i \le r ,\dfrac{\text{lcm}(b_l,b_{l+1},\cdots,b_r)}{b_i} | a_i \iff \forall l \le i \le r ,\dfrac{l}{b_i} | a_i \iff \forall l \le i \le r ,l | a_i \cdot b_i \iff l | \gcd(a_l \cdot b_l,a_{l+1} \cdot b_{l+1}, \cdots , a_r \cdot b_r)$$$. So we can use two segment trees maintain $$$\text{lcm}(b_l,b_{l+1},\cdots,b_r)$$$ and $$$\gcd(a_l \cdot b_l,a_{l+1} \cdot b_{l+1}, \cdots , a_r \cdot b_r)$$$.

      Second, consider how to get the answer. Let $$$dp_i$$$ means the answer of $$$[1,i]$$$. We can use binary search to get the minimum $$$j$$$ that $$$c_j = c_{j+1} = \cdots = c_i$$$. Then $$$dp_i = \min\limits_{k=j}^i dp_{k-1}+1$$$. We can use another segment tree to maintain the minimum $$$dp_i$$$ in a range.

      Finally, $$$dp_n$$$ is the answer. (Sorry to my poor English and expression)

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

Though C is too hard for it's position, CD are great and E is very beautiful! Thanks for the problemset!

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

.

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

✅ Maximize your enjoyment of the contest, not your rating after it

Agree, 100% (delta=-100), absolutely loved C! I guess problems C and D could have been swapped. Although that probably would've given away the solution to the current D, if it were C.

Thanks again for the amazing contest!

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

https://mirror.codeforces.com/contest/1798/submission/199317662

Can someone explain why this solution of c got a runtime error?

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

satyam343 orz comment. Satyam is a legendary grandmaster in disguise.

He is the women's pet, men's regret and if you bet against him, it is a bad bet.

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

Good contest! Finally reached specialist

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

Well at least i solved C alone, although it was after round ended.

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

Can anyone tell me why in Problem D they said that the sum of all elements is $$$0$$$? The way I proved my solution didn't use this fact at all.

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

    could you please share your idea? I didn't gave much attention to the first line during contest so i failed to come up with a construction, I only know(not sure if true though) that a construction will always exist if abs(sum(all elements)) < max. — min.

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

A great contest,problems are interesting and educational!

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

it was a great round!

greetings to everyone who worked on this round <3

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

Finally became specialist... Codeforces Round 860 (Div. 2) was great overall

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

    Great job! Congratulations on your achievement. It's inspiring to see cute and talented individuals excel in competitive programming

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

Today I got a message of code copying with someone named VRSancheti. I even don't know him/her and our code is also different to a great extent and only logic is same. I had just copied boilerplate from Internet which may have resulted in same code(as he/she might have copied the same boilerplate from Internet). Yet my all questions have been made wrong. I honestly wrote my code on VScode and submitted it. Please look into this matter and take necessary action.

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

Your solution 199301914 for the problem 1798C significantly coincides with solutions Ultraspeedforces2/199298118, madhurgupta185/199301914. My ratings of this contest have been reverted back. It was a simple problem. Why would I take code from someone who is a newbie.I have been using the same template for a long time. Please look into the matter and take necessary action. Please do look into the matter MikeMirzayanov

→ Reply