DS007's blog

By DS007, 3 months ago,

Hello Codeforces!

I am pleased to invite you to my first contest Codeforces Round #695 (Div. 2), which will take place on Jan/08/2021 17:35 (Moscow time). The problems were written by alimq and DS007. The round is rated for all users with rating less than 2100, while other users can participate unofficially.

You will be given 5 problems and 2 hours to solve them. You are strongly advised to read all the problems.

I would really like to thank:

• BledDest for his amazing coordination of the round.
• Aggu_01000101 and infinitepro for helping me in shortening the problem statements and solving one of the problems.
• MikeMirzayanov for creating the Codeforces and Polygon systems.
• The following people for testing the round:

We hope you will enjoy the problem set! Good luck!

The scoring distribution will be added shortly.

UPD: Also thanks to nooinenoojno for testing the round.

UPD: The scoring distribution is: $500 - 1000 - 1500 - 1750 - 2500$.

UPD: Congratulations to the winners

Of div 1:
1. kort0n
2. Suiseiseki
3. peti1234
4. fastmath
5. wrinx

And of div 2:
1. raingirl
2. xsdns
3. Mister5
4. o.a
5. wudi2016

Thank you all for participating! My apologies for misjudging the difficulty of B.
Editorial

• +424

 » 3 months ago, # |   +722 As a tester, I have a proof that upvoting this comment will lead to positive delta. But the proof is too long to fit the margin.
•  » » 3 months ago, # ^ |   +198 Is the proof left as an exercise for the reader?
•  » » » 3 months ago, # ^ |   +2 This is the way
•  » » » 3 months ago, # ^ |   0 yes
•  » » 3 months ago, # ^ |   +116 Will we get a video of DS007 dancing if this comment gets more upvotes than the blog itself? saarang123
•  » » » 3 months ago, # ^ | ← Rev. 4 →   -48 Meow wants it
•  » » 3 months ago, # ^ |   +172 As a tester I upvoted and demand my positive delta
•  » » » 3 months ago, # ^ |   +23 Runtime Error
•  » » » » 3 months ago, # ^ |   +24 Output Limit Exceeded
•  » » 3 months ago, # ^ |   -46 manish.17 I am one of those who are trusting you. Let's see what happens.
•  » » 3 months ago, # ^ |   +5 It seems like replying to this comment can lead to upvotes.
•  » » 3 months ago, # ^ |   -31 what if I downvote?
•  » » 3 months ago, # ^ | ← Rev. 13 →   -8 ‎‎
•  » » 3 months ago, # ^ |   +25 Feature Request : "Downvote an upvoted comment".
•  » » 3 months ago, # ^ |   -14 I want my upvote back please.
•  » » 3 months ago, # ^ |   +54 T(HE)Y BE(LIE)VE(D)
•  » » » 3 months ago, # ^ |   +5 LOL. This comment totally made up for any rating fall.
•  » » 3 months ago, # ^ |   0 It seems like I'll have a counterexample soon.
•  » » 3 months ago, # ^ |   +7 it actually worked!
 » 3 months ago, # | ← Rev. 2 →   +184 As a tester there are 1 AI and 4 DS problems SpoilerSpoilerDS=Dhruv Saraff AI=Alim Imanmalik
 » 3 months ago, # |   +104 As a tester, I Can confirm that DS007 is a wonderful dancer.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +31 As a participant, I think it would be safe to assume that the order of difficulty of the problems wouldn't dance as well,XD!!
•  » » 3 months ago, # ^ |   +4 As a non-tester, I can also confirm DS007 is a wonderful dancer.What do you think BRCode?
•  » » » 3 months ago, # ^ |   +9 As a tester, I agree!
•  » » 3 months ago, # ^ | ← Rev. 3 →   -27 .
•  » » 3 months ago, # ^ |   -26 But not a wonderful author.
 » 3 months ago, # |   +92 As a tester, I'll edit this comment later and add something witty.
•  » » 3 months ago, # ^ |   +9 Seems like it was quite difficult for DS007 to fit you in the above tester arrangement, which itself is pretty cool, I hope there would have been more diversity in color(given we have new year magic)
•  » » » 3 months ago, # ^ |   +44 Isn't the colour arrangement pretty cool though? It's the CodeForces logo!
•  » » » » 3 months ago, # ^ |   +14 Indeed it is, but would be much better if we can have you also in that arrangement :P
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +14 I'm 6th from the top in the middle column :P
•  » » » » » » 3 months ago, # ^ |   +22 I must say, that was a trap!!!
•  » » » » 3 months ago, # ^ |   +5 Ahh my bad, seems like you are already there in expert's color :P
•  » » » » » 3 months ago, # ^ |   +14 Yes :( The real CodeForces magic was that the website somehow detected my true skill level :(
•  » » » » » » 3 months ago, # ^ |   -22 As a tester, I can confirm I'm actually red
•  » » » » » » 3 months ago, # ^ |   0 As a tester i also agree with you all. All the best everyone and do tell me if my testing was worth it
 » 3 months ago, # |   -75 Indian round means unrated round
 » 3 months ago, # |   -7 This should be great contest. Good luck to everyone!
•  » » 3 months ago, # ^ |   +1 Oh! Really?
 » 3 months ago, # | ← Rev. 8 →   +162 I'm the (official) meme supplier for this contest. For every 69 upvotes, I'll upload a new, original content, cp related meme. #1 Free Sample #1 #2See this post for latest memes.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +57 Free Sample #2 Free Sample #3When your solution is proved by Accepted.
•  » » 3 months ago, # ^ |   +7 I like the second meme.
 » 3 months ago, # |   -11 Good luck to everybody and to me also
 » 3 months ago, # |   0 Wow, no wonder you said, You had a lot of testers for this round earlier. Looks like a lot of effort went into the preparation of the round, looking forward to it. Also any authors of future rounds who are looking for testers, I would be happy to help.
 » 3 months ago, # |   +10 Let's wait till 11/01 to see the tester table messed up. Unless it will be changed later.
 » 3 months ago, # |   +119 SpoilerThe arrangement of testers is not random. SpoilerIt's the CF logo.
•  » » 3 months ago, # ^ |   0 Spoilerand it's beautiful
•  » » 3 months ago, # ^ |   +32 SpoilerSpoilerSpoilerSpoilerits_Atrap
•  » » » 3 months ago, # ^ |   +11 Recursion
•  » » 3 months ago, # ^ |   0 I thought it was the columbian flag
 » 3 months ago, # |   -7 only 192 more for pupil rank :D (lmao I'm not still good and I don't know why I'm happy)
•  » » 3 months ago, # ^ |   -7 Hi
•  » » 3 months ago, # ^ |   -6 Only 97 for specialist. But I know i'm gonna decrease again. :)
•  » » » 3 months ago, # ^ |   +11 You will stay at nutella. Don't worry.
 » 3 months ago, # |   +88 ()
•  » » 3 months ago, # ^ |   +24 Why do I have a feeling that you know the problemset?
•  » » » 3 months ago, # ^ |   0 Than offer him to be one of the tester :P
•  » » » » 3 months ago, # ^ |   0 Bro, according to my qualification, i can only test sugar in coffee. But, i love the idea.
•  » » » » » 3 months ago, # ^ |   0 You can also test sugar in tea :P
•  » » 3 months ago, # ^ |   +6 how did u predict that... kind a sus!!
•  » » » 3 months ago, # ^ |   +31 Now as a predictor, i want upvotes.
•  » » » » 3 months ago, # ^ |   0 Done!!
 » 3 months ago, # |   +22 I tested this contest and it was good.
 » 3 months ago, # |   0 Last round was great. Problem statements were short & crisp and without unnecessary stories to read. As you mention that the problem statements have been shortened, eagerly awaiting the next round :)
 » 3 months ago, # |   -81 As a tester, give me contribution! Also suggest me a new profile photo, I removed mine temporarily.
•  » » 3 months ago, # ^ |   +3 You got contribution even as a non-tester! Not positive though, but still you didn't specify what kind of contribution. May consider doing this in future myself.
 » 3 months ago, # |   -32 Your Ceiling is My Floor!
 » 3 months ago, # |   0 I like how the testers' names are arranged in order of the lights to the left of the logo!
•  » » 3 months ago, # ^ |   +15 Imagine getting rejected as contribution farmer tester just because cf logo will not look good in the announcement.
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 LMAO. Still, you gotta appreciate the effort though XD! For the testers to change their ratings so much and for DS007 to properly format it.
 » 3 months ago, # |   +7 Indian Round .
•  » » 3 months ago, # ^ |   +3 Was waiting for this comment!!!
•  » » 3 months ago, # ^ |   +6 Actually it's an Indian — Kazakhstani round ;)
•  » » » 3 months ago, # ^ |   0 OMG Kazakhstan!!! Hoping to see Borat themed problems
 » 3 months ago, # |   -9 pog
•  » » 3 months ago, # ^ |   -9 pawg
 » 3 months ago, # | ← Rev. 7 →   -51 Hello :)
 » 3 months ago, # |   -20 I hope everyone rating goes up in this contest
•  » » 3 months ago, # ^ |   +44 you seriously lack hoping skills
•  » » 3 months ago, # ^ |   +3 we don't do that here
•  » » 3 months ago, # ^ |   +2 Well its impossible. Someone's rating has to decrease for someone's rating to increase.
•  » » » 3 months ago, # ^ |   0 I have always wondered about this. After a codeforces contest, is the summation of every participant's delta 0?
•  » » » » 3 months ago, # ^ |   +48 It's less than 0.
•  » » » » » 3 months ago, # ^ |   0 Really?
•  » » 3 months ago, # ^ |   -7 You better never hope anything positive from the next time
 » 3 months ago, # |   -36 As a non tester Chaliye Fodte hai ;)
 » 3 months ago, # |   0 Hope a good result for everyone !
 » 3 months ago, # |   +2 It's advised in the post to read all the problem statements. Does that mean the problems won't necessarily be in increasing order of difficulty?
 » 3 months ago, # | ← Rev. 2 →   +5 As an idler, there are too many useless spoilers on this page, so one can use this script in the console to expand them all: \$(".spoiler-content").map((i,val)=>{val.style.display="block";}) 
 » 3 months ago, # |   +5 SPOILERFORCES
 » 3 months ago, # |   +9 Guys don't waste your time in B and C like me. There is always an easier approach and everytime I think of an overkilled solution.
•  » » 3 months ago, # ^ |   +3 You may consider rethinking your strategy after this contest...
•  » » » 3 months ago, # ^ |   +1 I told you!
•  » » » » 3 months ago, # ^ |   0 sed lyfe :(
•  » » 3 months ago, # ^ |   +2 I feel you bro :'(
•  » » 3 months ago, # ^ |   +1 ALways start from harderlike D or E onwards as cheaters can't ruin them easily. Also you may get first to solve award for a problem with that startegy, Last contest I would have solved Div2 D as the first person to solve but I got a silly error thus finished it after 7-8 people.
•  » » 3 months ago, # ^ |   0 Guys guess what?? Again I overkilled the solution of problem B. Although i solved it but wasted a lot of time. XD
•  » » » 3 months ago, # ^ |   0 I got 4 WA in A and 4 WA in B, but managed to solve both.
•  » » » 3 months ago, # ^ |   0 how to solve b?
 » 3 months ago, # | ← Rev. 2 →   +20 Love this comment section
 » 3 months ago, # |   -26 hello im from viet nam
 » 3 months ago, # |   +21 There are only 3 ratings left before I can be a Master(without using "magic")!Hope I can do it!
•  » » 3 months ago, # ^ |   +18 You can do it!
•  » » 3 months ago, # ^ |   0 All the best...
•  » » 3 months ago, # ^ |   0 You can make it. Best of Luck :)
•  » » 3 months ago, # ^ |   +6 I got rank58!Hope I would not Failed on System test.
•  » » » 3 months ago, # ^ |   +8 Congrats!!
 » 3 months ago, # |   0 I hope no one cheats in today's contest.
•  » » 3 months ago, # ^ |   +29 How to decrease mass cheating ?Problem Setters today: Keep the problemset out of their reach.
•  » » » 3 months ago, # ^ |   0 very good idea.
 » 3 months ago, # |   -10 Just two hours left in the contest and still not able to see the score distribution for problems.
 » 3 months ago, # |   -9 Ok
 » 3 months ago, # | ← Rev. 2 →   +28 If the contest gets 20k participants, I'm going to post 25 high quality memes.Plus, DS007 promises a div1+div2 contest in the near future if this contest is well received...
•  » » 3 months ago, # ^ |   0 Already get it.
•  » » 3 months ago, # ^ |   +47 He actually made a Div 1 contest and named it Div 2
 » 3 months ago, # |   0 F
 » 3 months ago, # |   +5 scoring PLS
 » 3 months ago, # | ← Rev. 2 →   -22 Is it rated for newbie?
•  » » 3 months ago, # ^ |   0 i think u did not read the contest announcement (The round is rated for all users with rating less than 2100)
 » 3 months ago, # | ← Rev. 2 →   -53 .
•  » » 3 months ago, # ^ |   +32 Don't generalize a bad deed to many people, especially when lots of them are helpful and honest :D
•  » » 3 months ago, # ^ |   +4 Indians aren't cheaters. Don't generalise something to whole community. It's not a good thing.
 » 3 months ago, # |   +2 good luck
 » 3 months ago, # | ← Rev. 4 →   -18 div2A is kind of diffcult >_
 » 3 months ago, # |   +1 it's been only 30 minutes and I already hate this contest.
•  » » 3 months ago, # ^ |   0 Even Masters are struggling, now that's tough
•  » » » 3 months ago, # ^ |   +27 No,masters just close the website and enjoy their life because they're unrated.
•  » » 3 months ago, # ^ |   -8 very long queue too!
 » 3 months ago, # |   0 Long queue?
 » 3 months ago, # |   -8 I think authors should not make problems anymore
 » 3 months ago, # |   +75 Describe the contest in 1 line: Wrong answer on pretest 3
•  » » 3 months ago, # ^ |   0 XD
 » 3 months ago, # |   +23 The round of Wrong answer
 » 3 months ago, # | ← Rev. 2 →   0 deleted
 » 3 months ago, # |   -30 Contests 2021 is so boring !!!
 » 3 months ago, # | ← Rev. 3 →   -52 Deleted
 » 3 months ago, # |   +21 I am in doubt this is a div2 round ...
•  » » 3 months ago, # ^ |   0 I have a similar doubt too. Looks like a DIV 1 I guess. One thing which presents always while submitting my code i.e--"W.A on pretest 3". Disappointed after giving today's contest. :(
 » 3 months ago, # |   +20 well there goes my expert
•  » » 3 months ago, # ^ |   +17 My expert already went last round, this round I lose my specialist.
•  » » 3 months ago, # ^ |   +5 You are not the only one. :(
•  » » 3 months ago, # ^ |   +3 And there goes my confidence!
•  » » 3 months ago, # ^ |   0 There goes my pupil successfully. I should have skipped this round maybe. :(
•  » » 3 months ago, # ^ |   0 .
 » 3 months ago, # |   0 As I can see from my friends standings this contest has been a total mess.
 » 3 months ago, # |   0 to the admin of this contest please don't do the same for the next time.
 » 3 months ago, # |   -9 it is been more than half of the contest and less than 3000 one solved b :o , i can say that this is a big mess
 » 3 months ago, # |   +20 Pretests for B are too damn strong. Kudos.
•  » » 3 months ago, # ^ |   0 Better strong than weak. Would you really want to fail a system test?
•  » » » 3 months ago, # ^ |   +10 I said kudos. Did you even read.
 » 3 months ago, # |   +9 Just waiting for time to end and someone tell me all I did was miss an edge case to get Wrong Answer on Pretest 3 :(
•  » » 3 months ago, # ^ |   +13 You can try this; 1 7 1 10 5 2 7 4 1 output:2
 » 3 months ago, # |   +22 I am actually curious to see the standing of the testers' virtual participation.
 » 3 months ago, # |   +98 CF #695 IN A NUTSHELL
 » 3 months ago, # |   -6 is it only me or is anyone else also struggling with pretests of DIV2 A?
•  » » 3 months ago, # ^ |   -6 Use patience there is a little trick in it. I have given 5 wrong answers for div2 B.
 » 3 months ago, # |   +17 Div2-B Pretest 3 is KILLER !!!
 » 3 months ago, # |   +14 What the hell is this Pretest 3 in B
 » 3 months ago, # |   0 SOLVED C but Failed B. this is CODEFORCES EFFECT
•  » » 3 months ago, # ^ |   +1 lol same pretest 3 is going to hell
 » 3 months ago, # |   +7 No way this was a DIV 2 round
 » 3 months ago, # |   +1 Too hard!!
 » 3 months ago, # |   -15 Really confusing statement for A, or so it appeared to me. Although they explicitly mentioned $|x-y|$, I had considered array to be circular in my mind. Even the examples satisfy the circular array assumption.
•  » » 3 months ago, # ^ |   0 Same, I to get WA on pretest 3, not able to solve a single question, RIP my ratings ;-; :( ;-;
 » 3 months ago, # |   +7 WA on pretest 3
•  » » 3 months ago, # ^ |   +2 WA on pretest 3
•  » » » 3 months ago, # ^ |   0 WA on pretest 3 :'( How to fix that problem? I couldn't do it
•  » » » » 3 months ago, # ^ |   0 WA on pretest 3
 » 3 months ago, # |   +7 The most evil: "Problem B pretest 3"
•  » » 3 months ago, # ^ |   0 Talking about B, Not able to solve even A
 » 3 months ago, # |   +11 I probably misread Div 2
•  » » 3 months ago, # ^ |   +3 I probably misread codeforces.
 » 3 months ago, # | ← Rev. 2 →   -7 To the people complaining — Div2B is all about a simple brute-force, so yes — you've read that right — perfectly suitable problem for Div2B. As for the Div2C I believe it has to do something with finding the two minimum elements and a few corner cases, but wasn't able to solve it fully.Overall a great contest! Really challenging and interesting problemset! Thanks to the authors for such an amazing contest!EDIT: Again downvoted for saying truth — newbies go be real mad. Y'all expect to solve 3 problems and stay pupil? No, that's not how it works. Back in the day, people who solved 2 problems fast could reach 1700 — because problems used to be tough. Trust me — no improvement if you do only easy problems.
•  » » 3 months ago, # ^ |   +1 I don't know about rest of the comment but yes challenging problems must be welcome
•  » » 3 months ago, # ^ |   +63 Downvoted, I don't like when D2B is bruteforce. Am I newbie?
•  » » » 3 months ago, # ^ |   +10 I didn't call people newbies for not liking D2B bruteforce — just not being able to figure it out in 2 hours really doesn't deserve any higher rank. I was very scared when It took me over 30 minutes to get such an easy problem right. It's really a standard thing these days to see D2B done using brute-force.
•  » » » 3 months ago, # ^ |   +32 D2B was not a bruteforce, it was $ifififelseifelseelseififelseelseififelse$.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +21 It was brute-force without many ifs if you are smart about it. Take a look at my code and compare it to yours.
•  » » » » 3 months ago, # ^ |   0
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 Writing a score function like this would have saved you a lot of time and efforts :  int score(const vector& a, int i) {  if (i <= 0 || i >= a.size() — 1)    return 0;  if (a[i] < a[i — 1] && a[i] < a[i + 1])    return 1;  if (a[i] > a[i — 1] && a[i] > a[i + 1])    return 1;  return 0;};
•  » » 3 months ago, # ^ | ← Rev. 2 →   -13 Agree that this was a nice contest. Couldn't complete finding C corner cases. It was a hard fight and annoying.
•  » » 3 months ago, # ^ |   0 In my opinion B was "hard" for the wrong reasons. Most people at the Div 2B level can definitely understand the solution for B. The most pleasant word I would use to describe today's B is not "hard", but "tedious": had the right idea and most of the details early on, took forever to find the missing corner case.Also, it wouldn't be such a big deal if the very next problem, C, wasn't yet another "figure out the cases" problem 0_0.
•  » » » 3 months ago, # ^ |   +9 Again i will say — no special case exists in Div2B. Take a look at my accepted code.
•  » » » » 3 months ago, # ^ |   +3 Ignoring template my code is shorter than yours .___.
•  » » » » » 3 months ago, # ^ |   +3 But it's more bug prone. I was 100% convinced my solution would not fail, while it took you more attempts to get it right.I'm not disapproving your knowledge in any way, just to be clear.
•  » » » 3 months ago, # ^ |   0 I don't think B had a special case... You just needed to implement it carefully.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +1 did you lost your mind??Div2 B are generally of rating 1200-1300 and this contest's div2B is of rating 1700. This is the most unbalanced contest.Its easy for you to say these things because simply you are expert.
 » 3 months ago, # |   +5 Got stuck even on B. As a result, return to the cyan :(How to solve B and C?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 B is brute force. Change each character so that it is equal to one of its neighbors and "carefully" calculate the change of cost for only the subarray where the change has an effect. Then do the same for the other neighbor.
•  » » » 3 months ago, # ^ |   +3 Change the character $a_i$ to previous $a_i$ or to the next $a_i$? I did so, and got WA 3 :(
•  » » » » 3 months ago, # ^ |   0 I got a nasty bug where I did not check if the neighbors that were previously not a hill/valley became a hill/valley after changing the value of a[i]
•  » » » » 3 months ago, # ^ |   0 Change to both, and see which one gives you a better result.
•  » » » » 3 months ago, # ^ |   +3 Also, if $a_{i-1} \neq a_{i+1}$ you might try something between them, like $\frac{a_{i-1} + a_{i+1}}{2}$
•  » » » » » 3 months ago, # ^ |   +5 No, it is never an optimal step.
•  » » » » » » 3 months ago, # ^ |   0 yeah, my bad
•  » » » 3 months ago, # ^ |   0 With this exact approach I submitted 7 wrong answers, still unsolved. Can you share a clean implementation?
•  » » » » 3 months ago, # ^ |   0 Brother you might be missing that after changing A[i] to A[i-1] what is the impact of A[i-1] on A[i+1]. initially I was also missing this but got AC after i checked it.
•  » » » » » 3 months ago, # ^ |   0 I did realize this later but i guess i suck at implementing. Thanks
 » 3 months ago, # |   0 getting wrong answer on pretest 3 for B question ,can anyone give any test case
•  » » 3 months ago, # ^ |   0 same :(
 » 3 months ago, # |   +1 quite a peculiar contest many people had the first problem wrong in the first attempt and even the second question. loved the contest by the way
 » 3 months ago, # |   +20 Those who failed B, try this Testcase261 5 10 4 6 12610 8 5 15 7 6Answer should be 1 1
•  » » 3 months ago, # ^ |   +3 My answer is 1 1 and still getting Wrong answer on pretest 3.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +4 Got 1 to both, for the incorrect submission of B. Any other Test Case?
•  » » 3 months ago, # ^ | ← Rev. 2 →   +6 My solution passed these tests and got WA 3 :(
•  » » 3 months ago, # ^ |   0 Ah, got it. Thanks mate! Was trying to find the mistake for 1.5 hours!
•  » » 3 months ago, # ^ |   0 thanks, good testcase
•  » » 3 months ago, # ^ |   0 thanks !!! was thinking along the same lines but then decided to move on to question 3
•  » » 3 months ago, # ^ |   0 My Solution is correct while failed on pretest3
•  » » 3 months ago, # ^ |   0 How 1 1 can you explain please
•  » » 3 months ago, # ^ |   +1 Try this also: Spoiler1 7 1 10 5 2 7 4 1 output: 2
•  » » 3 months ago, # ^ |   0 thanks it worked for me
 » 3 months ago, # |   -72 fuck you mother fuckers[user:alimq][user:DS007]
 » 3 months ago, # |   +40 Who made these problems is an evil person ...
 » 3 months ago, # |   0 Since contest is over, may I get some hints on how to solve problem C?
•  » » 3 months ago, # ^ |   0 I replaced a[i] for 1
•  » » » 3 months ago, # ^ |   +1 He is talking about Problem C.
•  » » » 3 months ago, # ^ |   0 That's what I did but I got WA on 3 :(
•  » » 3 months ago, # ^ |   +5 Without loss of generality, lets assume that the final element will belong to bag A.Now, think of the problem as ans = a1 + a2 + ...an + -b1 + b2 + ...bn + -c1 + c2 + ... cn(Move all but 1 element in A to B. Move all but 1 in C to B. Move all but one in B to C. Now move all back to A. So all the elements except the ones unmoved in B and C will have a -(-) positive contribution to the sum. There is one more possibility. Assume c1 was infinite, so a -c1 is not affordable. So we move all Cs to B and then to A, and ignore moving B twice.Answer in this case will be Sum(A) + Sum(C) — Sum(B).Swap A, B, C and find the max case. 103801386
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +4 This outline makes complete sense. Such a short solution for such difficult problem! Beautiful
 » 3 months ago, # |   -9 My mistake from past 30 or so minutes if(!isValley(idx, arr) && !isValley(idx, arr)){ } instead of if(!isValley(idx, arr) && !isPeak(idx, arr)){ } and that happens despite using an IDE that warns against this :)
 » 3 months ago, # | ← Rev. 2 →   +135 Who wants to hear how we, the testers, trolled the cheating telegram group? Lot's of WA are cause of our efforts.To those who want to help: Search for solutions of B that have a -25 anywhere in the code. Post their names here, they are all cheaters...Reason why? Will make a blog post "soon".
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Upvote for calling testers of this round to be called batmen/women
•  » » 3 months ago, # ^ |   +1 Yes, interested to hear that.
•  » » 3 months ago, # ^ |   -50 Couldn't you have made some good problems instead of doing this? Many masters have struggled to solve A, B?? The problems were too random. The setters of this contest should not be allowed for any further rounds.
•  » » » 3 months ago, # ^ |   +7 No they weren't. The problems were actually on easier side as later ones were standard. But it was diverse round.
 » 3 months ago, # |   +4 Some thoughts after solving B:If you wrote exactly once in bold why couldn't you write or let the sequence remain unchanged in bold as well?Why can't n be just greater than 2?
•  » » 3 months ago, # ^ |   +1 Agreed. Why would you want us to handle n = 1,2 separately? Just make n > 2.
•  » » 3 months ago, # ^ |   +8 "In the second test case, the best answer is just to leave the array as it is." This is the sample explanation so it was mentioned there.
•  » » » 3 months ago, # ^ |   0 The second test case will give the same answer when you do exactly one change (change the last 2 to 3). I agree that we should be more careful while reading the problem statement but I just thought it would have been better if it would have also been mentioned in bold that we can perform no changes also...
•  » » » » 3 months ago, # ^ |   0 spooky's comment would make more sense then. It was still mentioned in the explanation of sample cases.
•  » » » » 3 months ago, # ^ |   0 why is mentioning that no change is allowed sush a big issue. if u really wanted to do that you could just increase or decrease a particular number such that it does not make any difference. it was asking to print the minimum intimidation number not the steps required for that
•  » » 3 months ago, # ^ |   0 It says "You can change exactly one integer...", which has the meaning you can do, or do not.
•  » » 3 months ago, # ^ |   +3 LMAO lol I had no idea what was wrong with my program and yeah, it was the fact I did not account for n = 1 and since I now use c++ instead of Java it did not say index out of bounds.... That's honestly stupid.
 » 3 months ago, # |   -16 Why were almost all of the wrong answers related to test case 3 in Problem B ?!
•  » » 3 months ago, # ^ |   0 same bro
•  » » 3 months ago, # ^ |   0 I don't understand what's wrong with my question that I got 8 downvotes ! I just was curious about it And I just asked a question
 » 3 months ago, # | ← Rev. 2 →   -12 .
 » 3 months ago, # | ← Rev. 2 →   -33 tricky contest XD
 » 3 months ago, # |   0 Div2 C I think I figured out... I was not sure though: is it just total — 2*(smallest + second_smallest) ? D was easier I thought...
•  » » 3 months ago, # ^ | ← Rev. 2 →   +4 Nope for C counter example 1 1 1 3 4 5 Answer 6
•  » » » 3 months ago, # ^ |   0 What is the counter-example? Like which ones belong to which list?
•  » » » » 3 months ago, # ^ |   0 It's like each list is of length 1. Take 3, 4 and 5 as elements of different lists.
•  » » » » 3 months ago, # ^ |   0 i dont know how to put "newline" in this comments. You have 1 element in each bag,in the first one is 3,the second 4 and the last one si 5.
•  » » » » » 3 months ago, # ^ |   +6 Two spaces after line is newline here
•  » » » » » 3 months ago, # ^ |   0 All good — I understand your test. Looking at the submissions that seem to be passing for problem C, it seems like they used what I mentioned but adjusted it a bit for the edge cases :(
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 No, I did that and failed test 3.Counter example can also be:1 1 11 1 1Correct answer 1, we print -1.
•  » » » 3 months ago, # ^ |   0 Fudge.
•  » » 3 months ago, # ^ |   +1 will fail on this 1 1 1 1 2 3 
•  » » 3 months ago, # ^ |   +1 except when smallest and second smallest are from same bag. In that case its min of that and total-2*(min sum in any bag). correct me If am wrong.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 You have two cases. total sum-2*(smallest + second smallest) (as you said). (Find the minimum of all 3 sets and take the smallest and second smallest) sum of two largest sets — the smallest set sum. Take the maximum of both cases
•  » » » 3 months ago, # ^ |   0 smallest and second smallest have to be from different sets I assume?
•  » » » » 3 months ago, # ^ | ← Rev. 3 →   0 Yes, Thanks Fixed my comment
 » 3 months ago, # | ← Rev. 2 →   +28
 » 3 months ago, # | ← Rev. 3 →   -6 In my opinion only fault was it was of 2 hrs . It should have been half or 1 hour more.Problems weren't straight forward and samples didn't gave any hint and that's why accuracy in this contest was low. But contest wasn't that bad.
•  » » 3 months ago, # ^ |   -41 This is the worst contest I have ever seen
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +12 Problems were difficult thus i think more time would have worked. Except difficulty was there any other issue ?Please don't down vote the blog , no one intentionally wants people to perform bad . At least we can appreciate that it was not typing test.
•  » » » » 3 months ago, # ^ |   -41 F**k constructive algorithms.
•  » » » » 3 months ago, # ^ |   +2 It deserves down-vote.
•  » » 3 months ago, # ^ |   0 Ya, even i solved the third problem exactly 2 minutes before the end of the contest and couldn't even read problem D
 » 3 months ago, # |   +1 I am eagerly waiting to see the 3rd test case of problem "B".
 » 3 months ago, # | ← Rev. 5 →   0 Problem solved
•  » » 3 months ago, # ^ |   0 I am getting 1 but still WA on pretest 3
•  » » » 3 months ago, # ^ |   +1 yeah, there is also one test: Test case 22 6 1 5 10 4 6 12 6 10 8 5 15 7 6 Answer should be 1 1 
•  » » » » 3 months ago, # ^ |   0 How is this 1 1
•  » » » » » 3 months ago, # ^ | ← Rev. 2 →   +6 I checked this out on the paper and that's true. Just because in both cases you can not rid of all from 1 mountain or hill. You can try to do it on the first test picture:
•  » » » » 3 months ago, # ^ |   0 andrews3 my code print correct in all your test cases but WA on 3
•  » » » » » 3 months ago, # ^ |   0 don't worry, I also have WA on 3 test. P. S. I just found some tests :D
•  » » » » » » 3 months ago, # ^ |   0 awesome XD
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Also Test Case1 7 1 5 6 4 5 6 1 Answer should be 2(I guess?)
•  » » » 3 months ago, # ^ |   0 yeah, you are right
 » 3 months ago, # | ← Rev. 3 →   +14 I'm not exactly in a position to say this, but I think pretests for E were too weak. Let's define an array occ[1e9], where occ[i] represents the number of nodes with assigned number equal to i. Then my solution worked in O(sum(occ[i] ^ 2)), which on worst case is O(n ^ 2), and for some reason pass the pretests without much problem. I guess that's because my solution is too counter-intuitive to even think of, but allowing any kind of O(n ^ 2) to pass is in my opinion a sign of very weak testcases.Note: I'm not saying anything about the main tests, I do hope that some in-contest hacks will be added to break my solution (post-contest hacks will surely break it). However, I suspect this is not the case since there were only around 100 accepted solutions for E, and I've not seen a hacked solution in-contest.UPDATE: So thankfully (or not?), a new test was introduced to break my solution. My opinion holds though.
 » 3 months ago, # |   0 My wait for cyan continues....
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 A my waiting for Expert too...
 » 3 months ago, # | ← Rev. 2 →   0 ;(
 » 3 months ago, # |   +6 Respect ! To those who solved B from the first submission !
•  » » 3 months ago, # ^ |   +7 Also true for 'A' (:
 » 3 months ago, # | ← Rev. 3 →   -10 Excuse me for saying this .. There are two points that make this contest bad : You have underestimated it as Div2 ,,,, The tests were not enough to fully understand problems
•  » » 3 months ago, # ^ |   0 exactly
 » 3 months ago, # | ← Rev. 4 →   -14 Very interesting round, first time I've had to write a brute-force for A and B to debug my fast-but-WA code.For those facing WA in B, here is a brute-force solution and a test harness in python. Brute-force solutiondef is_hv(A, i): if not (0 <= i-1 < i+1 < len(A)): return False if A[i] > max(A[i-1], A[i+1]): return True if A[i] < min(A[i-1], A[i+1]): return True return False def count_hv(A): ret = 0 for i in range(len(A)): if is_hv(A, i): ret += 1 return ret def ans_slow(A): ret = count_hv(A) for d in range(min(A), max(A)+1): for i in range(len(A)): new_A = A[:] new_A[i] = d ret = min(ret, count_hv(new_A)) return ret  Test harnessimport random for _ in range(10000): N = random.randint(1, 50) tc = [random.randint(1, 20) for _ in range(N)] assert(ans(tc) == ans_slow(tc)) 
 » 3 months ago, # |   -12 And we all thought 2021 will bring us happiness and positive delta
 » 3 months ago, # |   +33 On the positive side, fast system testing.
•  » » 3 months ago, # ^ |   +8 Less Accepted solutions
 » 3 months ago, # |   0 system testing on nitros. so much lesser submissions relatively.
 » 3 months ago, # | ← Rev. 2 →   0 In C, can we take a and b from the same bag? The problem statement makes it sound like we can't, but then I don't really see how the answer to the second test can be 29...
•  » » 3 months ago, # ^ |   +1 (7 5 4) (7 1) (2 9)(7 5) (7 (1 — 4)) (2 9)(7) (7 (1 — 4 — 5)) (2 9)(7) (7 (1 — 4 — 5 — 9)) (2)(7) ((1 — 4 — 5 — 9)) (2 — 7)((7 — (1 — 4 — 5 — 9))) () (2 — 7)((7 — (1 — 4 — 5 — 9) — (2 — 7))) () ()(7 — (-17) — (-5)) () ()(29) () ()
•  » » » 3 months ago, # ^ |   +8 Wow. I'm dumb. Thank you very much!
•  » » 3 months ago, # ^ | ← Rev. 2 →   +1 Put the 9 in 2nd bag with the 1 in 3rd bag making it -8Put the 7 in 3rd bag with the 2 in 2nd bag making it -5So the bags now have 7 5 4-5-8I think you will be able to make 29 from here.
 » 3 months ago, # | ← Rev. 2 →   0 For Task $B$ The maximum no of hill/valley we can destroy by changing a number is $3$ right?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 The best possible case is when changing an element, the answer decreases by 3, however, you have to be careful because many corner cases may exist.What I did was: for each position $i$, I have some options. Keep the value of $v[i]$ the same or for each $j$ $(i - 2 \le j \le i + 2)$, assign $v[i] = v[j] + 1$ or $v[i] = v[j] - 1$ or $v[i] = v[j]$.Therefore, I just have to iterate over all these possibilities and see which one is the best.Note that for each possibilty, I just need to recalculate the answer in the interval $[i - 2, i + 2]$.
 » 3 months ago, # |   +1 is my idea for B totally wrong ? We can at most decrease the hills and valleys by 3 because at most we can affect 2 hills and one valley or 2 valleys and one hill how could I be wrong about that
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 Can most decrease by 3 — correct.Code with too much ifs must not exist never. Sure thing either one case is missing or misprinted.
•  » » » 3 months ago, # ^ |   0 I guess there's a stupid bug in my code that I didn't notice the idea is correct
•  » » 3 months ago, # ^ |   0 yes but when you have a hill and valley adjacent, flattening a valley may give rise to a new valley eg: 15 10 5 20 17, here when you try to get rid of valley 5 , you must make it >=20 but that would make 10 a new valley
•  » » » 3 months ago, # ^ |   0 Yeah I tried to change the hill or valley to one of the two adjacent values and took the best change my code is just terrible I should have found a better way to code it
•  » » 3 months ago, # ^ |   0 Well that part isn't wrong
•  » » 3 months ago, # ^ |   0 Your code is so beautiful.
 » 3 months ago, # |   +19 This contest was a trap. :))
 » 3 months ago, # |   +3 Another Div 1.5 Contest. Those who submitted A and B in one go without wrong answer on pretest 3. Hats off to their accuracy.
 » 3 months ago, # |   +11 Rozen Maiden one-two finish with Suiseiseki :)
•  » » 3 months ago, # ^ |   +10 :)
 » 3 months ago, # |   -9 Next time Don't believe on a new setter too Quickly!!!:(
•  » » 3 months ago, # ^ |   0 Dude, he is making contests, actually making actual contribution to the community. What have you done to do the same? It's pathetic to see the entitlement which participants seem to have. Even I had a terrible contest, but I wouldn't take it out on the authors. Try to give constructive criticism, if possible or don't comment at all :)
•  » » » 3 months ago, # ^ |   0 Ok Agreed,but then the new POSITIVE criticism is it was not a DIV2 atleast!!
 » 3 months ago, # |   0 Very weak pretests for C :(
 » 3 months ago, # | ← Rev. 2 →   0 The contest is fun and annoying at the same time as "WA on pretest 3", corner cases killed my rating :)) Anyway, I like it :D
 » 3 months ago, # |   -15 why contest div2 was too hard ???
 » 3 months ago, # |   -85 Petition to not allow these setters ever again. The problems were too random and confusing.
 » 3 months ago, # |   0 What type of div2B has <30% passing rate smh
•  » » 3 months ago, # ^ |   +9 Yeah, many people got stuck on QB... QC is relatively easier imo
•  » » » 3 months ago, # ^ |   0 If you don't spend a lot of time on B, that is...
 » 3 months ago, # |   +21 Fastest system testing.
 » 3 months ago, # |   -8 Just asking, did the testers give no feedback about the difficulty? It would be much better if there were one more problem between A and B.
 » 3 months ago, # |   +7 Problem B WA3: When you replace a number, you may not improve the answer, but rather make it worse. Most likely, you only checked the destruction of valleys/hills.Example: 1 66 7 10 5 7 9answer(1), your answer(0)Your program will replace the number 10 with a smaller number X. Then most likely there will be a hill (6, 7, X). It was necessary to make a separate check for this
•  » » 3 months ago, # ^ |   +3 can u please tell why my sol is wrong?_https://codeforces.com/contest/1467/submission/103821246