### Wind_Eagle's blog

By Wind_Eagle, 5 weeks ago, translation,

Hello, Codeforces!

I am very glad to invite you to the Codeforces Round #672 (Div. 2), which will take place in Sep/24/2020 17:35 (Moscow time). This round will be rated for the participants with rating lower than 2100.

All tasks were made by me, but gepardo helped me a lot with the last two tasks, probably these tasks wouldn't have appeared if he didn't help me.

My thanks to:

• antontrygubO_o for coordinating this round. With this great coordination only good tasks remained in the contest.

• gepardo made a lot, there wouldn't have been this contest if he didn't help me. He not only helped me with making last two tasks, but also helped me to understand how to make tasks for Codeforces rounds. Thanks!

• EIK this is the person who teached me competitive programming — my Informatics teacher. Thanks!

• programmer228, Hacktafly, K1ppy inspired me to make this round, listened for the every task idea, provided feedback and testing. Thanks!

• Osama_Alkhodairy, vamaddur, thenymphsofdelphi, Devil, Ari, SleepyShashwat, csani, Monogon, guptapratham42, Kavit_Kheni for testing the round and the tasks. Thanks!

• MikeMirzayanov for Codeforces and Polygon platforms. Thanks!

• You for participating in this round. Thanks!

You will have 2 hours for solving 5 tasks, one of which will be divided into easy and hard verions. I hope you will enjoy the round, I tried to make short statements and strong pretests interesting tasks.

Score distribution: 500 — 1000 — (1000 + 1250) — 2000 — 3000

UPD: The editorial is available. English version will be ready after the system testing is over.

UPD2: The english version of the editorial is ready.

• +929

 » 4 weeks ago, # |   +91 As a tester, ask me anything.
•  » » 4 weeks ago, # ^ |   +118 What's the solution to the last problem?
•  » » » 4 weeks ago, # ^ |   +267 I would tell you if I knew how to solve it :sob:
•  » » » » 4 weeks ago, # ^ |   +51 Now this seems entirely believable, it wasn't easy at all
•  » » 4 weeks ago, # ^ |   +188 Hi Monogon, How come you are getting downvotes?
•  » » » 4 weeks ago, # ^ |   +171 I don't know, I thought my formula for getting upvotes was foolproof. To become top contributor, maybe I'll just make another contest instead.
•  » » » » 4 weeks ago, # ^ |   +59 Are you sure you can become the real top contributor by just making another contest?
•  » » » » » 4 weeks ago, # ^ |   +104 Hmm, it might take 2 contests.
•  » » » » » » 4 weeks ago, # ^ |   +100 Errichto laughing in the corner.
•  » » » » » » » 4 weeks ago, # ^ |   +47 ![ ]()
•  » » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +5 .
•  » » » » 4 weeks ago, # ^ |   -21 Monogon Please consider me as one of the tester in your next round. Hopefully would be able to see your next round soon.
•  » » 4 weeks ago, # ^ |   +76 How so orz?
•  » » » 4 weeks ago, # ^ |   +90 I just memorized some stuff that's enough to solve puzzles.
•  » » » » 4 weeks ago, # ^ |   +64 I think this one comes from Um_nik's blog.
•  » » » » » 4 weeks ago, # ^ |   +76 Must be a notorious coincidence.
•  » » 4 weeks ago, # ^ |   +72 is this like the ecnerwala blog but in contest blog?
•  » » » 4 weeks ago, # ^ |   +67 Not at all. In ecnerwala's blog, you get to ask someone who's actually good.
•  » » » » 4 weeks ago, # ^ |   +50 so do you mean you are not good? if so why should we ask you when we can ask ecnerwala?
•  » » » » » 4 weeks ago, # ^ |   +56 I cannot say for sure whether you should ask me or ecnerwala, as it depends not only on the question you ask, but also on what you seek to gain from asking. If you ask ecnerwala, he may give a thoughtful reply. But such a reply might also come very late or never seeing that his AMA was posted some time ago. On the other hand, my replies are likely to be stupid, repeated jokes, but you will get them immediately.
•  » » » » » » 4 weeks ago, # ^ |   +11 Whenever I see Monogon in the list of testers, I immediately visit the comments section for his quick wit. The comments section, in general, is great fun. Or maybe it's the lockdown that's rendered me so aimless.
•  » » » » » » » 4 weeks ago, # ^ |   +9 Its more fun when either Monogon or vovuh are among round contributors.
•  » » 4 weeks ago, # ^ |   +33 How to become tester???!!!!
•  » » » 4 weeks ago, # ^ |   +51
•  » » » » 4 weeks ago, # ^ |   +5 I guess it was a joke.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +24 Oh wow. Didn't knew it was a joke. I wanted to help him become a tester once. :( Spoiler Spoiler Spoiler
•  » » » » » 4 weeks ago, # ^ |   +15 r/woooosh
•  » » » 4 weeks ago, # ^ |   +25 It's very simple. Just pick a random user from the "top rated" or "top contributors" box to the right, and send them a direct message asking to be a tester. They are all making contests right now, so they'll immediately let you see the upcoming problems and pay you to test them. Hope this helps!
•  » » » » 4 weeks ago, # ^ |   +52 they pay you to test or you pay them to test?
•  » » » » » 4 weeks ago, # ^ |   +15 It depends on how well you do. Testing is no different than a game of blackjack.
•  » » » » » 4 weeks ago, # ^ |   +71 You guys are getting paid?
•  » » » » » » 4 weeks ago, # ^ |   +14 why you are asking me? ive never been tester
•  » » » » 4 weeks ago, # ^ |   +6 I'm pretty sure Errichto isn't making any rated contest for cf right now.
•  » » » » 4 weeks ago, # ^ |   0 don't they judge me ??? I want to know what qualification need to be a tester?
•  » » 4 weeks ago, # ^ |   +11 How was the testing?
•  » » » 4 weeks ago, # ^ |   +57 Testing was good. I found that one problem had appeared before and so it was replaced. But then because it was replaced, I dropped in the standings, and other testers assumed I was even dumber than I really was.
•  » » 4 weeks ago, # ^ |   0 As a tester. You cannot participate in this round. Is this guaranteed by technical means or is it consciously? Do you know all the problems? Or only the parts?
•  » » » 4 weeks ago, # ^ |   +21 Yes, I know all the problems, and I'm not allowed to participate in the contest. I don't think there's anything in the system preventing testers from actually registering for the contest and submitting solutions, but obviously it would get caught by Mike Mirzayanov's omnipresence.
•  » » 4 weeks ago, # ^ |   -9 MR. Monogon , Why 5 problem in most of the recent contests ?
•  » » » 4 weeks ago, # ^ |   +32 This is a better question to ask coordinators. It could be a false pattern in random data.
•  » » 4 weeks ago, # ^ |   -6 Monogon Love the way you ask for upvotes. One upvote for you from my side. LOL
•  » » 4 weeks ago, # ^ |   +10 How is Monogon ?
•  » » » 4 weeks ago, # ^ |   +6 I'm doing ok. What about you?
•  » » » » 4 weeks ago, # ^ |   +3 Just started now need to explore the things !
•  » » 4 weeks ago, # ^ |   -18 What is the probability of solution getting accepted after passing of pretests in total.
•  » » » 4 weeks ago, # ^ |   +8 Hope it is not like previous contest. I know your pain brother.. :(
•  » » » » 4 weeks ago, # ^ |   +16 I've tried my best to make pretests strong enough. Hope it will be so.
•  » » » » » 4 weeks ago, # ^ |   +8 Thanks champ
•  » » » 4 weeks ago, # ^ |   +1 Given the large number of users, there have to be very few pretests on early problems to prevent a long queue. This is pretty limiting, even if each test has many test cases. So, it's very hard to write good pretests. Despite this, I think on average we're in a much better place than a few years ago.
•  » » 4 weeks ago, # ^ |   +8 As a tester, how much contribution do you want ?
•  » » » 4 weeks ago, # ^ |   +152 Errichto + 1
•  » » » » 4 weeks ago, # ^ |   0 Monogon,Seems like you will achieve those in this comment section itself, congrats.
•  » » » » 4 weeks ago, # ^ |   -8 Who is errichto???
•  » » » » » 4 weeks ago, # ^ |   0 look in the top contributors table , you will know
•  » » 4 weeks ago, # ^ |   0 how to get +195 contribution?
•  » » » 4 weeks ago, # ^ |   +69 Just set 2 contests solo, 1 contest on a team, write a tutorial, and hijack the comment section of all rounds you test as your personal upvote farm.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Your genius, it generates gravity. Really loved(and upvoted) every comment. errichto should have participated too.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Why does Errichto has two youtube channels?
•  » » » 4 weeks ago, # ^ |   +51 So he can say he has double the subscribers.
•  » » » » 4 weeks ago, # ^ |   0 Why don't you have a youtube channel?
•  » » » » » 4 weeks ago, # ^ |   +30 I've considered it. But I'm afraid doing screencasts will put pressure on me, and will negatively impact my performance. Especially if I provide commentary. Other content such as video tutorials is actually very time-consuming, and I don't think I could explain things better than existing resources for most topics. I admire those who do make videos and try to grow the competitive programming community because I understand it's a lot of work. Personally, I find problemsetting a better way for me to give to the community.
•  » » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 You can do DIV-2/3 if you're comfortable.. It will not put pressure on you as it would be unrated for you.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +31 Why does problem C have more point in total than problem D?
•  » » » 4 weeks ago, # ^ |   +27 To anger and confuse you.
•  » » 4 weeks ago, # ^ |   0 When are you becoming red ?
•  » » » 4 weeks ago, # ^ |   +12 Soon
•  » » » » 4 weeks ago, # ^ |   +10 This aged well
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 well played.. you should have told you true intentions lol XD
•  » » 4 weeks ago, # ^ |   0 Where is/are Mifafavov, is there some bigger conspiracy we are not aware of?
•  » » » 4 weeks ago, # ^ |   +11 If it's a conspiracy then I'm not a part of it. Although I suppose I'd say that even if I was in the conspiracy...
•  » » 4 weeks ago, # ^ |   0 how to get contribution??
•  » » » 4 weeks ago, # ^ |   +13 Host contest. Post announcement and editorial. Test a round and hijack its comment section. It's a known fact.
•  » » » » 4 weeks ago, # ^ |   0 Thanks luctivud
•  » » » » 4 weeks ago, # ^ |   0 You missed- "Make good memes and post in the comment section"
• »
»
4 weeks ago, # ^ |
-20

# include<bits/stdc++.h>

using namespace std; typedef long long ll;

int main(){ int t; cin>>t; while(t--){ ll n, count = 0, limit; cin>>n; ll a[n]; bool flag = true;

    limit = n*(n-1);
limit = limit/2;
limit -= 1;

for(ll i = 0; i < n; ++i){
cin>>a[i];
}

for(ll i = 0; i < n - 1 && flag; ++i){
for (ll j = i + 1; j < n && flag; j++){
if(a[i] > a[j]){
count++;
if(count > limit){
flag = false;
break;
}
}
}
}

if(count <= limit && flag)
cout<<"YES"<<endl;
else
cout<<"NO"<<endl;

}
return 0;


} Its the 1st sum: why did this kept exceeding pretest 2

•  » » » 4 weeks ago, # ^ |   0 This is quadratic, the constraints can go upto 10^5.
•  » » » » 4 weeks ago, # ^ |   0 Yes. I just figured it out. What's the solution to it?
•  » » » » » 4 weeks ago, # ^ |   0 An array can take atmost n*(n-1)/2 swaps to sort and that worst case is when the array is strictly decreasing.
 » 4 weeks ago, # |   -38 off-topic, how to be a tester for some round?
•  » » 4 weeks ago, # ^ |   -7 This was a genuine question but whatever...
•  » » » 4 weeks ago, # ^ |   +23 Genuine question asked on almost every other contest announcement blog. Again and again.
•  » » » » 4 weeks ago, # ^ |   +43 Well, I suppose I should've searched before posting here.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Usually you can connect with the coordinators or the author and they can allow you to test and discuss , mostly its yellows and reds because of their greater experience and knowledge they can find issues / judge difficulty better. Hope that helps :)
 » 4 weeks ago, # |   +57 I love rounds coordinated by antontrygubO_o.
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   +50 First of all, I'm not talking about the nature of the problems. Sometimes I like ad-hoc and constructive problems, and sometimes I don't.What I like and he delivers — short statement, strong pretests, normal readable English, coherent sentences (unlike the last round), understandable and unambiguous statements.I enjoy reading the clear statements in his rounds, and I never feel ripped off after the contest. I think that's a good enough reason to like his rounds...
•  » » » 4 weeks ago, # ^ |   0 No Adhoc/Constructive unfortunately :'(
 » 4 weeks ago, # |   +33 Legend says Monogon will reply to every comment on this blog
•  » » 4 weeks ago, # ^ |   +55 Well it would be kind of rude not to answer questions in my own AMA, wouldn't it?
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If you don't mind, what is the full form of "AMA"? Thanks!
•  » » » » 4 weeks ago, # ^ |   +57 "Ask Monogon Anything"
•  » » » » » 4 weeks ago, # ^ |   +14 Thanks for enlightening me!
 » 4 weeks ago, # |   +39 Is the apocalypse near? Why is Monogon getting downvotes?
•  » » 4 weeks ago, # ^ |   +10 Duh! It's 2020 after all.
 » 4 weeks ago, # |   +9 Hope there will be short statements and strong pretests .
 » 4 weeks ago, # |   +14 After a series of thanks by WIND_EAGLE,thanks from the contestants who will witness a positive rating change
 » 4 weeks ago, # |   +34 Interesting that most of testers for the Div2 round are orange or higher.
 » 4 weeks ago, # |   +39 Long statements is Boring :(
 » 4 weeks ago, # |   +7 Whenever I see the short statements and strong presets statement, I instantaneously imagine that I will be losing rating in this contest but then again most of the contest I take part in become unrated ://.
 » 4 weeks ago, # | ← Rev. 2 →   -20 We hope there will be interesting tasks with strong pretests.
•  » » 4 weeks ago, # ^ |   0 bro, what happend? why all coders dislike your comment!!!
 » 4 weeks ago, # |   +29 Monogon has earned a total of 652 upvotes in this blog alone where the blog post is sitting at 414. (Also, you might think how free am I to do count such dumb shit. Guess what, you are right)
 » 4 weeks ago, # |   0 I will get rating in this round.
 » 4 weeks ago, # |   +8 Interesting to see the total score of problem C greater than that of problem D ! I wonder how many times has this happened before ?
 » 4 weeks ago, # |   0 Best of luck everyone and hope u positive rating change
 » 4 weeks ago, # | ← Rev. 2 →   +10 Will Monogon Comment Here Or Has Mono Gone??!!
 » 4 weeks ago, # |   0 Are the problem statements clear? They can be long provided they are clear.
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 i wish,it Will be Clear:)
 » 4 weeks ago, # |   0 I'll do you one better: Why is Monogon?
 » 4 weeks ago, # |   -9 Is Mono gone?
 » 4 weeks ago, # |   -11 Who is monogon?
•  » » 4 weeks ago, # ^ |   0 A codeforce user, and sometimes a problems setter, and sometimes a problems tester.Greetings Monogon
•  » » » 4 weeks ago, # ^ |   -23 Hello Sir.
•  » » » » 4 weeks ago, # ^ |   -30 Hello, sir!!11!
•  » » » » 3 weeks ago, # ^ |   0 What a rare sight, Monogon being downvoted
 » 4 weeks ago, # | ← Rev. 2 →   +1 it's really amazing how he tried to appreciate every one..!!
 » 4 weeks ago, # |   +16 After seeing the long lists of upcoming contests...
 » 4 weeks ago, # |   +11 I think that this round will be amazing
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 But I won't take part in it :(It's toooooooooo late for me :(
•  » » » 4 weeks ago, # ^ |   +8 Ohh, it's really sad.I hope that virtual solve help you
 » 4 weeks ago, # |   -26 Adhoc shit incoming
 » 4 weeks ago, # |   +8 I hope that queue of testing solutions is not long on this round
•  » » 4 weeks ago, # ^ |   +8 That's what we need to hope for, not short statements
 » 4 weeks ago, # |   -9
 » 4 weeks ago, # |   0 I am not sure why this happened last time but the pretests were way too short as compared to other recent cf rounds. Quite a few failed system tests. Hope it is not the case this time around. :(
 » 4 weeks ago, # |   +13 i really started to love the comment section lol
 » 4 weeks ago, # |   +8 Best Of Luck to everybody for the round
 » 4 weeks ago, # |   -19 hello,MikeMirzayanov..plz..help me..i forgot to register in this contest..please..enable me to join the contest!.or anyone help me..(its bigger than ocean..)..plz..give me a chance..
•  » » 4 weeks ago, # ^ |   -13 or..Wind_Eagle..
 » 4 weeks ago, # |   +19 I still don't know who, or what Nibel is.
•  » » 4 weeks ago, # ^ |   +18 Nibel is a forest where Ori lives.
•  » » » 4 weeks ago, # ^ |   +10 Is the plot based on Ori and the Will of the Wisps? I had played Ori 1 and didn't recognize things in the statementnice problems btw
•  » » » » 4 weeks ago, # ^ |   +10 No, the statement is based on Ori and the Blind Forest.
•  » » » » » 4 weeks ago, # ^ |   0 Sorry I'm just dumb. I never played the game in English and never remembered the names of those things.
•  » » » » » » 4 weeks ago, # ^ |   0 Well, I understand you, I've never played this game in English too :)
•  » » » » » » » 4 weeks ago, # ^ |   -10 hey,can you please give me a chance to register..i forgot..and solved problem A 1 hour ago(maybe much)..
•  » » » » » » » » 4 weeks ago, # ^ |   +4 The contest is over now.
 » 4 weeks ago, # | ← Rev. 3 →   0 .
•  » » 4 weeks ago, # ^ |   +8 The last submission which passed pretests is considered, the others are ignored.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 .
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 .
 » 4 weeks ago, # |   +37 As a participant, I declare that this round was great.
•  » » 4 weeks ago, # ^ |   +36 Thank you!
 » 4 weeks ago, # |   -38 when you spend an hour debugging code because u forgot to set mod inverse factorial of 0 to 1 :(
•  » » 4 weeks ago, # ^ |   +15 The contest is still ongoing.
•  » » 4 weeks ago, # ^ |   +4 when you spend an hour first trying to fit python solution into the constraints and getting +4 rejected and then giving up and rewriting it in c++
•  » » 4 weeks ago, # ^ |   -7 Dude, what is wrong with you ? why are you posting such things during contest ? MikeMirzayanov
 » 4 weeks ago, # |   +1 Nice Round! What's the solution for D?
•  » » 4 weeks ago, # ^ |   0 Just sorting ends of the intervals and then a bit of combinatorics
•  » » » 4 weeks ago, # ^ |   +11 Come on, answer the question or ignore it. But do not act like a dick.
•  » » » » 4 weeks ago, # ^ |   0 Come on. I did answer it. Without giving details, but nevertheless.
•  » » » » » 4 weeks ago, # ^ |   +32 That "answer" did not help at all. You just did tell that is was easy for you.
•  » » » » » » 4 weeks ago, # ^ |   0 I'm pretty sure that knowing that you need to put ends of the intervals in the array and then use combinatorics is quite a huge hint
 » 4 weeks ago, # |   +1 nice round .. thank you how to solve C2 ?
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +3 reconsider (check for peak or bottom) only adjacent elements of swapped ones. (and the swapped elements too of course)
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +16 Answer is sum of max(a[i] — a[i + 1], 0) (a[0] = 0). Change in answer can be calculated in O(1).
•  » » » 4 weeks ago, # ^ |   0 Can you pls explain the reasoning behind this? Thanks!
•  » » » » 4 weeks ago, # ^ | ← Rev. 4 →   0 If we take two numbers, first number should be larger than second. So if there is some decreasing sequence $a_1, a_2, a_3, ..., a_k$, value of $a_1$ — $a_k$ is same as $(a_1 - a_2) + (a_3 - a_4) + (a_i - a_{i+1})$. So we will always add two numbers(add zero to end of array a answer doesn't change).
•  » » 4 weeks ago, # ^ |   +12 Seems like I massively overkilled but my solution would work for any changes, not just swaps:Keep a segment tree where each node store the maximum value of a sequence with the following properties: (starting with pos, ending with neg), (starting with pos, ending with pos), (starting with neg, ending with pos), (starting with neg, ending with neg)The merge is trivial to do in O(1).
•  » » » 4 weeks ago, # ^ |   0 Using the observation that as long as numbers are distinct, the contribution of $i$th term to the final answer depends only on $a_{i - 1}, a_i, a_{i + 1}$, you can arbitrarily update any index trivially in $O(1)$. Full SolutionSince only minima's and maxima's contribute to the final solution. The contribution of $i$'th term is $a_i$ if it's maxima (i.e, $a_i > a_{i- 1}, a_{i + 1}$), and $-a_i$ if it's minima ($a_i < a_{i - 1}, a_{i + 1}$).Now to update some index $i$, delete from answer the contribution of $i - 1, i, i + 1$'th term, update $i$th term, and add the contributions of $i - 1, i, i + 1$.
 » 4 weeks ago, # |   +5 As a participant, I declare that this round was nice
•  » » 4 weeks ago, # ^ |   +4 As non-monogon, you might get downvoted!
 » 4 weeks ago, # |   +1 Hint for C2?
•  » » 4 weeks ago, # ^ |   0 If a[i] is greater than a[i-1] and a[i+1], add a[i] to the answer. If a[i] is less than a[i-1] and a[i+1], subtract a[i] from the answer. And let a[0]=a[n+1]=0. Change the contribution of up to 6 positions per exchange. Complexity: O(n).
•  » » 4 weeks ago, # ^ |   0
 » 4 weeks ago, # |   +21
•  » » 4 weeks ago, # ^ | ← Rev. 15 →   +1 I tried to do the same approach but got WA. here is my submission https://codeforces.com/contest/1420/submission/93713635 . Can you tell me what went wrong? Edit: Got AC.
•  » » » 4 weeks ago, # ^ |   0 THe gfg soln is wrong, you have to add value to the total.
 » 4 weeks ago, # |   0 Time limit on C2 was too tight. I wrote up a Segment Tree and got TLE on pretest 6...
•  » » 4 weeks ago, # ^ |   0 No, I also wrote a segment tree, got AC in 1.2s, it's 16*N only.
•  » » » 4 weeks ago, # ^ |   0 Actually it's 8*N since you can reduce the size of the tree to 2*N with a well known trick. Still, my seg tree implementation must be bad, because I still got TLE. Very sad :(
•  » » 4 weeks ago, # ^ |   0 The same, wrote a solution with sets O(QlogN) and got TLE.
•  » » 4 weeks ago, # ^ |   +1 How did you use a segment tree to solve that?
 » 4 weeks ago, # |   0 Can someone give a hint for C2?
•  » » 4 weeks ago, # ^ |   -9 Wait for editorial, it will appear very soon.
•  » » 4 weeks ago, # ^ |   +14 Keep track of maximas and minimas in an array, and see how answer can easily be computed only from the sums and indices of maximas and minimas.
 » 4 weeks ago, # |   +4
 » 4 weeks ago, # |   0 Most common mistake made in those 3500 failed submissions of problem D in this round %9982444353.
 » 4 weeks ago, # |   -7 I solved A using mergesort lol how did u count inversions so easily ? isn't it counting inversions ?
•  » » 4 weeks ago, # ^ |   0 Total number of swap needed for sorting a strictly decreasing array are $n * (n - 1) / 2$. That means if the array is not strictly decreasing answer is YES, else NO.
•  » » » 4 weeks ago, # ^ |   +11 OMG I'm so stupid
•  » » » » 4 weeks ago, # ^ |   0 me too lol. spent so much time
•  » » » 4 weeks ago, # ^ |   0 And here I am! Applied bubble sort logic and was counting the number of swaps. I'm so dumb!!!! Received TLE.
•  » » 4 weeks ago, # ^ |   0 well the number of inversions required will be maximum when the array is sorted in decreasing order and all elements are distinct and it will be equal to : n*(n-1)/2. Since we are given 1 operation less then this count so answer will be no only when all elements are distinct and sorted in decreasing order.
•  » » 4 weeks ago, # ^ |   0 When listening to your college teacher actually pays off lol..
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 { a1 > a2 > a3 > a4 > ... > an } is the only case that you need to make exactly n*(n-1)/2 operations
•  » » 4 weeks ago, # ^ |   0 It was bubble sort, and in worst case number of swaps are (n*(n-1))/2. So we just need to check if it was the worst case of bubble sort i.e strictly decreasing array.
•  » » 4 weeks ago, # ^ |   0 You don't need inversions, you have to check if atleast one pair i < j with a[i] <= a[j], you can just store minimum
•  » » 4 weeks ago, # ^ |   +5 You write so unreadable code man :(
•  » » » 4 weeks ago, # ^ |   0 if you mean mergesort code I didn't write it just copied it from some site I don't even how it's working
•  » » » » 4 weeks ago, # ^ |   0 The merge sort part in your code is something which looks close to actual code, the rest looks like some cryptic code written to burn someone's eyes. No offense.
•  » » 4 weeks ago, # ^ |   0 By the way you can also solve it (count inversions) using a segment tree
 » 4 weeks ago, # |   +14 My favorite room is the one with 3 * 10^5 lamps
 » 4 weeks ago, # | ← Rev. 2 →   0 Really Nice problems. tnx :)
 » 4 weeks ago, # | ← Rev. 4 →   +1 Can anyone please tell how to calculate binomial coefficient C(n,r)%Prime when n<=10^9 ? (or n<=10^18 maybe)!(Please don't give Links of blogs. I went through many of them during the contest. Please provide a link to the Code)Also, can anyone please tell why my solution for Problem D gave TLE on Test-11 (Gave me PTSD)? Thanks.
•  » » 4 weeks ago, # ^ |   0 I don't think you need C(n, r) for n <= 10^9 for problem D, I did it with C(n, r) for n <= 10^6.
•  » » » 4 weeks ago, # ^ |   0 I did the exact same. Can you please tell why it's giving TLE on test 11? Thanks
•  » » » » 4 weeks ago, # ^ |   0 Your ncr_mod function looks too slow (seems to be O(n+r))
•  » » 4 weeks ago, # ^ |   0 Specify the modulo or range of 'r'. If r <= 10^6, we can do it or if modulo is <= 10^6 we can still do it, else I don't think it is possible.
•  » » 4 weeks ago, # ^ |   0 Precompute all factorials and their inverses under N then O(1) multiply for each querynot sure about 1e9
 » 4 weeks ago, # | ← Rev. 2 →   +11 I solved C2 with a segment tree to maintain the product of matrices. It feels so dumb to write such a monster to solve a d2C.
•  » » 4 weeks ago, # ^ |   0 Can you please explain the basic idea? I can't think of a way to merge nodes, support updates, and queries.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +10 Sorry for the late reply.First we redefine the multiplication of matricies. Here $C_{i,j} = \max { A_{i,k} + B_{k,j} }$. Consider the dp solution of C1: $f_{i,0} = \max ( f_{i-1,0}, f_{i-1,1} + a_i) , f_{i,1} = \max ( f_{i-1,1}, f_{i-1,0} - a_i)$. It can be represented as a matrix multiplication. We have $\quad \begin{bmatrix} f_{i-1,0} & f_{i-1,1} \end{bmatrix} \quad \times\quad \begin{bmatrix} 0 & a_i \\ -a_i & 0 \end{bmatrix} \quad=\quad \begin{bmatrix} f_{i,0} & f_{i,1} \end{bmatrix} \quad$You can use a segment tree to maintain the product of the matricies. Check my submission for better understanding
 » 4 weeks ago, # | ← Rev. 3 →   0 for problem D, Time Complexity of my Python 3 solution is O(NlogN) but still getting TLE.can anybody help. link of My solution
•  » » 4 weeks ago, # ^ |   0 You don't seem to use any recursion in your code, it should work with pypy (without all the setrecursionlimit, threading etc code)
•  » » » 4 weeks ago, # ^ |   0 I don't think there is any need for recursion. here is my solution in pypy which was also getting TLE.
 » 4 weeks ago, # |   0 How to solve E?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +5 If we fix number of zeros between adjacent ones (let's denote it as $g_i$), then answer is sum of $g_i$ * (sum $g_j$ where $j$ < $i$). So now this can be easily calculated with dp[i][last][moves], each transition is O(N), overall complexity is O(N^5), but there is a lot of unreachable states so it should pass.
•  » » » 4 weeks ago, # ^ |   +8 Yes, my solution was something about n^5/27.
 » 4 weeks ago, # |   +1 what the hell is that quotations in starting of each question??
 » 4 weeks ago, # |   0 Can someone tell me what wrong in my code? 93694586
 » 4 weeks ago, # |   -17 The problems were great but for heavens sake you didn't have to set such tight constraints for DReally annoying when solution with the correct asymptotic does not fit into constraints just because it is written in the wrong language and/or lacks some microoptimisationsI understand that there are plenty c++ lovers here, but still, don't do it. It is div2 after all
•  » » 4 weeks ago, # ^ |   0 I implemented counting the overlapping intervals. That needs to sort an array of size N*2 which should be possible in all languages. The other loop is then O(n).
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +4 That's the same thing I didExcept that just sorting 3*10^5 tuples in pypy can take nearly a second. Much faster in cpython though.Note that even your c++ solution with all io-tricks takes half a second. 10^5 would be enough to cut off ineffective c++ solutions
 » 4 weeks ago, # |   0 Really, Enjoyed the contest! Thanks to all the testers and problem setters who made such a fantastic contest. You guys are legends. Love you all.. :)
 » 4 weeks ago, # |   -8 problems were nice but is it too hard for problem setters to understand that we don't want any lame story along with the problems.
•  » » 4 weeks ago, # ^ |   +21 Why? The stories were short and nice :)
•  » » » 4 weeks ago, # ^ |   0 Atleast I agree with Wind_Eagle, they were actually nice and short :)
•  » » » » 4 weeks ago, # ^ |   -9 prabhAmbrose then go and read novels if you like stories
•  » » » 4 weeks ago, # ^ |   0 Usually, you guys say that you don't like stories now you are liking his comment just because he is yellow
•  » » 4 weeks ago, # ^ |   +8 adding the stories is something that gives happiness to the problem setters. If one doesn't know the game the story doesn't feel awesome(maybe lame) but just bear with it for the setters.
 » 4 weeks ago, # |   0 Hi, I tried to use segment tree to maintain maximum and minimum for alternating sequence with odd and even length for C1 and C2, it passes the sample test but failed on pretest 2? Could someone have a look and help me figure out what is wrong? Tks a lot!My Submission
•  » » 4 weeks ago, # ^ |   0 Problem C1 solution explanationhttps://youtu.be/skRw0pSNwS4
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I used a similar recursive implementation and got TLE on pretest 5. I'll try this blog when I get time. BTW I used your CP templates to make mine, thanks for putting it on Github!
 » 4 weeks ago, # |   0 about long long. Is it okay to use long long everytime, because I forget sometimes when to use it, and today, I wasted my time thinking my logic to B is wrong.
 » 4 weeks ago, # |   0 Problem D How to get (Cmn mod M) when m is big
•  » » 4 weeks ago, # ^ |   0
•  » » » 4 weeks ago, # ^ |   0 Thanks!
 » 4 weeks ago, # | ← Rev. 2 →   -6 Nice problems.
 » 4 weeks ago, # |   0 can someone explain me whats wrong with my code? 93695276 Its giving WA in pretest 6
•  » » 4 weeks ago, # ^ |   0 In the best case scenario you always choose an odd number of Pokemon so sometimes your code will needlessly subtract the last element I think.
•  » » 4 weeks ago, # ^ |   0 are you sure your code is ignoring even index (in reference to the subsequence) value if that is situated at last index?
•  » » » 4 weeks ago, # ^ |   0 yes,I think so..my friend wrote similar code.only difference was I wrote a[n]=a[n-1]-1; and he wrote a[n]=0;
 » 4 weeks ago, # |   0 I think I solved B 30 seconds after the contest so unlucky...
 » 4 weeks ago, # |   0 why do you need to sort the array in problem B?
•  » » 4 weeks ago, # ^ |   0 not needed
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   0 You don't need to sort the array. To see if x & y >= x ^ y, just look at the most significant bit of each number. Only if these two numbers have the same most significant bit, then we have x & y >= x ^ y (because in the xor operation, this most significant bit is destroyed, while in the and` operation it is preserved).
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 deleted
•  » » » » 4 weeks ago, # ^ |   0 It is because of the log function, you will get wrong answers when you will do log of bigger values.
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Issue was integer overflow not that log function.
 » 4 weeks ago, # |   0 Realy like it. Waiting for your next contest.
 » 4 weeks ago, # |   +1 What are your guys' approaches to solve B ? I'm really curious since the only one I can think of is using brute force.
•  » » 4 weeks ago, # ^ |   0 Hint:-$a[i]$ $and$ $a[j]$ $>=$ $a[i]$ $xor$ $a[j]$ if highest bit set in a[i] and a[j] are same
•  » » » 4 weeks ago, # ^ |   0 But we still have to use the brute force approach with a nested loop right ? Please help me since I've got 2 TLEs in a row.
•  » » » » 4 weeks ago, # ^ |   0 store the highest bit in a map or something. Then for each unique value k of highest bit add (k choose 2) to the total.
•  » » 4 weeks ago, # ^ |   0 Definitely no need for sorting as it will disturb the order of calculation of answer in the first place..just calculate the position of highest set bit in all numbers and notice the following : AND of 2 number will be greater or equal then XOR iff the position of highest set bit in a[i] and a[j] are the same, else XOR will always be greater.Store these positions of highest bits of all numbers in an array and iterate to find all such indices which are equal. Can use a map for it.
•  » » 4 weeks ago, # ^ |   0 I think you can solve it with brute force I am not sure because I optimized it 20 seconds before the contest ended but what you need to use is this to optimize it. https://www.geeksforgeeks.org/sum-product-pairs-array-elements/ I am not 100% sure my approach is correct as I can't submit now but I got TLE and not WA before the optimization.
•  » » 4 weeks ago, # ^ |   0 Consider two numbers a and b. If both of them have highest bit on the same position, then a&b > a^b. Otherwise a&b < a^b. The rest should be easy (if not, i can explain).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 I took a time to think this (especially to use long long instead of int). see the numbers as its binary form. now AND of 2 numbers will be one always less than or equal to the minimum of the two. XOR of 2 numbers can be more or less than any of the two. sol- count all the numbers whose highest precedence bit is set and those bit are in the respective positions of the array. do this for all the positions from 0 to 33, and add the number of ways you can choose 2 numbers at ith(higest precedence) postion as set. (pos[i]C2) my solNote that the answer depends only on higest precedence bit
 » 4 weeks ago, # |   0 Can someone please tell me what was the solution to A. I'm new and this was my 2nd contest. I applied bubble sort logic and counted the number of swaps but got TLE on pretest 2.
•  » » 4 weeks ago, # ^ |   0 I used merge sort just coz I had a prepared file for finding inversions ... it works but there must be so much easier ways as well
•  » » » 4 weeks ago, # ^ |   +7 The total number of swaps needed for sorting a strictly decreasing array is n∗(n−1)/2. That means if the array is not strictly decreasing answer is YES, else NO.-- by some guy whose name was in blue..
•  » » 4 weeks ago, # ^ |   +1 Actually the intuition of inversion count actually makes sense, but the worst case of such is when the array is in strictly decreasing manner. This case takes the no of swaps = (n * (n — 1)) / 2 and hence if the array is in any other manner it will take less than this much swaps which is the intended limit given to us. So if the array is strictly decreasing we need more than the given limit of swaps and answer is no else yes. Hope this helps and wwelcome to cf community :)
•  » » » 4 weeks ago, # ^ |   +5 Thanks for explaining so nicely.
 » 4 weeks ago, # | ← Rev. 3 →   0 .
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +1 5 6the expected answer to this is 0 but ur solution gives 1. it s one of many special cases where "If the number of bits of 2 integers are same, it's a valid pair" isn't correct.
 » 4 weeks ago, # |   +8 I solved my first official dp problem ever but struggled with A and B... so basically my rating just raised from newbie to happy newbie xDxDxD
 » 4 weeks ago, # |   +25 C was nice observation based : ans = sum(max(0,a[i] — a[i+1])), where a[N+1] = 0D was standard problem if you know the range overlap relation, ie, max(L1,L2,L3.....LK) <= min(R1,R2,R3,R4....Rk) So fix Li, as max of all L's for a set of choices of K intervals, then if M intervals overlap with such an Li, then add to the answer:ncr(M,k) — ncr(M-D,k) , where D is the number of intervals with left boundry = Li
 » 4 weeks ago, # |   0 Anyone explain in problem A why there are 0 exchanges for values 2,1?
 » 4 weeks ago, # |   0 I am just wondering if the C2 is more difficult than D.I completed D very fast but still has less idea for C2.
•  » » 4 weeks ago, # ^ |   +6 When I came to the task C, I thought that it will be good task D. But I had current task D which could not be a task C. So I decided to make C1 and C2.
•  » » » 4 weeks ago, # ^ |   +3 Alright,I am thinking about a solution based on dp and never think that: $ans=\sum\limits_{i=1}^{n}max(0,a[i]-a[i-1])$This conclusion is not difficult to prove but I'm always think abount dp dp dp dp dp.I am still have a lot to improveQAQ
•  » » » » 4 weeks ago, # ^ |   0 Can you prove why the above solution works? I too spent a lot of time coming up with dp solution but failed and submitted the wrong greedy.
•  » » » » » 4 weeks ago, # ^ |   +3 If your dp[i][0/1] means that the previous number to the i-th number is subtracted(0) or added(1),You will have a simple equation: $dp[i][0] = max(dp[i-1][0],dp[i-1][1]-a[i])$ $dp[i][1] = max(dp[i-1][1],dp[i-1][0]-a[i])$Notice that dp will be add only if $a[i] > a[i-1]$. Also dp will add a[i] — a[i — 1]so this is why that solution works.
•  » » » 4 weeks ago, # ^ |   +9 Should've put C1 -> D -> C2 if possible LOLmaybe
•  » » » » 4 weeks ago, # ^ |   0 Problem C1 solution explanationhttps://youtu.be/skRw0pSNwS4
 » 4 weeks ago, # |   0 Can anyone explain why in problem A there are 0 exchanges for values 2,1?
•  » » 4 weeks ago, # ^ |   0 using formula in A max exchnages allowed = (n * (n − 1)) / 2 − 1 for n = 2 , max exchanges allowed = 0
•  » » » 4 weeks ago, # ^ |   0 Thanks I misunderstood question
 » 4 weeks ago, # |   +3 Did anyone solve E using flows?
•  » » 4 weeks ago, # ^ |   0 Please, let me know your solution with flows, I am very interested!
•  » » » 4 weeks ago, # ^ |   +3 Actually I misinterpreted the question and allowed all 1 positions to move by a single step in one chance. So for each chance I made a layer of nodes corresponding to the gaps between 1s, and connected the final layer with the sink, with edges with cost (i-1) for each flow so that they add upto (gap*(gap-1)/2). Applying MinCostMaxFlow will give the answer. Without the restriction of a single move in a chance we can easily add edges between the layers but I am unable to figure out how to impose this restriction.
 » 4 weeks ago, # | ← Rev. 4 →   +3 I like this kind of contest with strong pretests. For problem D, enumerate the ending points of all values, and then count the number of new values $a$ each time, and the number of values that are still ending before $b$. The added contribution of the answer is: COMB(a + b, k) — COMB(b, k).
 » 4 weeks ago, # |   -32 is it DIV 2 or DIV 1 ? please reply !!
•  » » 4 weeks ago, # ^ |   -8 div 1
•  » » » 4 weeks ago, # ^ |   0 contest was good ... although keep it up Wind_Eagle
 » 4 weeks ago, # |   0 Can anyone prove why this solution for C1 is correct?
•  » » 4 weeks ago, # ^ |   0 He took local maximas for addition in the sum and local minimas for the subtrating values. This would always greedily prove best for u
•  » » » 4 weeks ago, # ^ |   0 You too have solved like this. I'm not getting why this will give an optimal answer.
•  » » » » 4 weeks ago, # ^ |   +10 Check the editorial, the solution for C2 uses exactly this idea.
 » 4 weeks ago, # |   0 Problem A: To sort an array of size n, we need n * log n moves. But the sad part is the problem wasn't go though this solution.
 » 4 weeks ago, # | ← Rev. 2 →   0 Sorry, I commented Twice
 » 4 weeks ago, # |   0 It went well. Very cool contest
 » 4 weeks ago, # |   0 Can anyone tell me where I did wrong with the solution for D? https://codeforces.com/contest/1420/submission/93711225
 » 4 weeks ago, # |   0 can anybody tell me why it is important to use long long in problem B ? (as I wasted 3 submissions before getting it correct D: ).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 If all numbers are same and n = 1e5 then the answer (n * (n — 1)) / 2 will overflow int.
 » 4 weeks ago, # |   0 I want to say that problem C1 is not new. Check this
•  » » 4 weeks ago, # ^ |   +4 In this problem you need to choose a segment, not a subsequence.
•  » » » 4 weeks ago, # ^ |   0 Sorry, my bad
•  » » » 4 weeks ago, # ^ |   0 can you explain the difference?
•  » » » » 4 weeks ago, # ^ |   0 Segment is something like [2,3,4,5,6], all elements are neighboring, subsequence is something like [2,3,5,7,10].
 » 4 weeks ago, # |   +1 Good to see the editorial has the hint part.
 » 4 weeks ago, # | ← Rev. 4 →   -8 Can we solve C2 with some dp and breaking array into $sqrt(n)$ part ??and then find this values for each part with dp: maximum sum if we start with a negative and end with a positive maximum sum if we start with a positive and end with a positive maximum sum if we start with a negative and end with a negative maximum sum if we start with a positive and end with a negative and then we need another dp to calculate the final answer witch can be done in $O(sqrt(n))$each time we just need to recalculate dp values for 2 part(the ones witch the L and R are inside them)i tried the above solution and i know that the time complexity is really bad( $O((n + q) sqrt(n))$ and got TLE on test 5 with long long and WA on test 5 with int because of overflow)i just want to know if my solution gives the correct answer or not(i don't care about the time, just want to know if the algorithm is correct or not) ??EDIT: i submitted my code witch got TLE on pretest 5 with GNU C++17 (64) and got AC :( the time complexity isn't so bad :)
•  » » 4 weeks ago, # ^ |   +5 Well my solution is kinda similar, just with segment tree 93668816.
•  » » » 4 weeks ago, # ^ |   0 thanks
 » 4 weeks ago, # |   0 The best thing about this contest was the stories were short!! Hope this stays for a longer run
 » 4 weeks ago, # |   0 Thanks a lot for preparing for this contests.Although problems are a little easy.
 » 4 weeks ago, # |   0 Couldnt even solve A!!
•  » » 4 weeks ago, # ^ |   +1 I can understand it, task A was a little bit difficult for task A.
 » 4 weeks ago, # |   0 Greedy solution for problem C1:Iterate from left to right.Find decreasing segments. (a[i] > a[i+1] > a[i+2] > ... > a[j])Take first and last number of the segments. (a[i] — a[j])Sum up every segments.
 » 4 weeks ago, # |   -7 i know that A can be done in less than 5 line of code easily but the harder solution can be done in n log n with just a search in googlethe same thing with c1, just a google searchother problems were nice, but its not good to see problems witch their solution is "just google things" in a CF contest :)
 » 4 weeks ago, # |   0 Problem similar to C1 was already on internet. Check this Wind_Eagle .https://tkramesh.wordpress.com/2009/10/08/maximum-alternating-sum-subsequence/
 » 4 weeks ago, # |   0 If there were 36 pretests in problem D and my solution 93708784 passed all the pretests, how can I get TLE on test 17 during system testing?
•  » » 4 weeks ago, # ^ |   +3 If your solution tightly fits into the time limit, it might happen that it worked a little longer on system tests and got TLE.
•  » » » 4 weeks ago, # ^ |   0 Such strict time limit that O(nlogn) solution did not fit.
•  » » » » 4 weeks ago, # ^ |   +1 The intended solution is also $O(n\log n)$ and fits into time limits twice on Java. But those sets and maps significantly show down your solution, while you may use only sorting.
•  » » » » » 4 weeks ago, # ^ |   +1 Just added another map for storing calculated inverse mod values and it worked 93729552.
 » 4 weeks ago, # |