### ch_egor's blog

By ch_egor, 5 months ago, translation,

Hello!

Right now happens the first tour of the Open Olympiad in Informatics, and tomorrow will be the second one. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Team Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567, 583, 594, 622, 626, 657, 680, 704).

Open Olympiad consists of the most interesting and hard problems that are proposed by a wide community of authors, so we decided to conduct a Codeforces regular round based on it, which will happen on Mar/13/2021 12:05 (Moscow time) and will be based on both days of the Olympiad. Each division will have 6 problems and 2 and a half hours to solve them.

We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification.

Problems of this competition were prepared by Akulyat, KiKoS, wrg0ababd, Nebuchadnezzar, biection, alexX512 isaf27, ismagilov.code, DebNatkh, Siberian, NiceClock guided by cdkrot, vintage_Vlad_Makeev, GlebsHP, Zlobober, meshanya, ch_egor, grphil, voidmax, Endagorion and Helen Andreeva.

Thanks to adedalic and KAN for the round coordination, statement translation and preparation of problems for the second division, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Also thanks to 4qqqq and Aleks5d for providing an additional problems that helped to create (I hope) a balanced problem set for the round, and Um_nik for testing!

Good luck everybody!

Due to the official competition source codes of other participants will not be available for an hour after the end of the round.

UPD1:

Please do not discuss problems publicly until 12:30 UTC.

The scoring distribution for both divisions is not standard:

• div1: 750 — 750 — 1500 — 2000 — 2500 — 3000
• div2: 500 — 1000 — 1750 — 1750 — 2500 — 3000

UPD2: Editorial

UPD3: Winners!

Div. 1:

Div. 2:

• -695

 » 5 months ago, # | ← Rev. 3 →   +35 amazing fact：in the first few minutes after the announcement is published，the announcement‘s rating is negative（？？？
•  » » 5 months ago, # ^ |   +299 sorry to make the first comment meaningless
•  » » » 5 months ago, # ^ |   +45 Nice redemption arc!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -44 np!!!:)
•  » » » 5 months ago, # ^ |   +23 makes meaning now
•  » » 5 months ago, # ^ |   +10 Why it's getting a lot of downvotes? Currently it has -246!!
•  » » » 5 months ago, # ^ |   0 Task's are too hard for their positions + low TLs.
 » 5 months ago, # |   +4 During the last contest, I performed really poorly, and I finally got a negative rating change. So I really hope I can do better this time.I expect my rank<1000, to do this, maybe solving the first four problems are needed.Hope everyone enjoy the fun of coding(and get a good result), stay Cheeki Breeki! >_<
•  » » 5 months ago, # ^ |   +99 sorry to make the second comment meaningless too:<
•  » » 5 months ago, # ^ | ← Rev. 2 →   +20 Don't worry about your rating! It really hurts the process of problem solving and having fun.If you start to really care about it, in NO TIME you discover you are trying your best just to get that $+ \Delta$ instead of learning real CP, which is pretty toxic.
•  » » » 5 months ago, # ^ |   +23 ?
•  » » » 5 months ago, # ^ |   +10 In my opinion, i suggest to virtual participation a contest so that you can enjoy the fun of problem solving and avoid $- \Delta$
•  » » » 5 months ago, # ^ |   +2 I don't think people so CP for fun only, rating is an integral part of it. It gives the thrill of winning and losing and having ranks. I love it.
 » 5 months ago, # |   0 Wish I can get perfect ranking and rating change.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +6 Dude, is your profile picture from Yosuga no sora? If that's so, do you know this guy — nitesh.dtu?Edit: I checked the picture, it really is Sora Kasugano. Man of culture!
•  » » » 5 months ago, # ^ |   0 Sorry, I don't know him/her.
 » 5 months ago, # |   +66 Really liked this point, We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner . I think we should have this in each contest.
 » 5 months ago, # |   +35 Notice the unusual start time!
 » 5 months ago, # | ← Rev. 2 →   -91 As a contestant, I want to become a tester :) Why to many down votes
•  » » 5 months ago, # ^ |   +21 What's the problem with my comment
•  » » » 5 months ago, # ^ |   +6 No one knows!
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -7 -69
•  » » » » 5 months ago, # ^ |   -12 I voted !!
 » 5 months ago, # | ← Rev. 2 →   -23 We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner, in particular, by trying to figure out problem statements from the onsite participants. If you end up knowing some of the problems of Moscow Open Olympiad (by participating in it, from some of the onsite contestants or in any other way), please do not participate in the round. We also ask onsite contestants to not discuss problems in public. Failure to comply with any of the rules above may result in a disqualification. That's the point what I like. As for sure, fair competition is very important for a round or the competition will be meaningless.btw, the time of this round is very great for Chinese users. I will partcipate in it and try my best solving problems. Good luck to all of the participants! :)
 » 5 months ago, # | ← Rev. 2 →   +9 Amazing starting time. I can finally get rid of my regular 'drink coffee and have a stomachache during contest' cycle. Yay!
 » 5 months ago, # |   +1 Change my opinion-Pacific time zone sucks for almost all types of schedule, either contests are 1AM in the night, or they are 6:30AM in the morning.
 » 5 months ago, # |   +89 From the past few weeks the unusual timing became usual to us.
•  » » 5 months ago, # ^ |   0 But they have different timing each contest lol. Seems they are doing something inorder to accomodate americans who have contests at 6 in the morning.
•  » » » 5 months ago, # ^ |   +1 Wow, Americans must be doing contests with a fresh mind.. Nice
 » 5 months ago, # |   -40 Why are some contests held at different times than usual? I think the usual timing is right for everyone!
•  » » 5 months ago, # ^ |   +48 I think the usual timing is right for everyone ! Sad American Noises from the corner
•  » » » 5 months ago, # ^ |   0 Man, us in Australia have it way tougher
•  » » 5 months ago, # ^ |   +12 Because some contests are mirrors of Russian OIs, like Open Olympiade or Technocup which held some hours before CF round.
•  » » 5 months ago, # ^ |   0 Happy Indian Noises Intensifies
•  » » 5 months ago, # ^ |   +18 The usual timing is right for someone, not everyone.As we all know, the particpants of Codeforces Rounds are from many different countries and areas, so that they live in different time zones. For example, for Chinese, the Codeforces rounds are usually held at 22:35 (local time) or even later. That's why "Codeforces Round #706" was held 2.5 hours earlier than usual.
 » 5 months ago, # |   +4 Olympiad rounds are challenging and fun!
 » 5 months ago, # |   -16 There are 22 writers in this contest. Can't believe it!!
 » 5 months ago, # |   +14 I can bet this won't be an easy codeforces round. Expecting Div-2 to be Div-1.5 by the length of contest.
 » 5 months ago, # |   -25 Notice the unusual start time :)
 » 5 months ago, # | ← Rev. 2 →   +17 Your last 2 contests had weak pretests. Hoping for strong pretests this time.
 » 5 months ago, # |   +19 Due to the official competition source codes of other participants will not be available for an hour after the end of the round. This means that we cannot discuss the problems here or anywhere for one hour after the end of the round?
•  » » 5 months ago, # ^ |   -6 Yes, it means that
 » 5 months ago, # |   0 Hopefully it will be a great round.
 » 5 months ago, # |   0 where are the "as a tester" comments!
•  » » 5 months ago, # ^ |   +39 Matured testers
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +5 I guess it means the round is gonna be challenging. :)
 » 5 months ago, # | ← Rev. 2 →   +18 Too many reds means too many problems to upsolve :v (to learn) !
 » 5 months ago, # |   -32 After see the author list and contest length. I am scaring about my rating :v
•  » » 5 months ago, # ^ |   +13 You need not be scared about much rating loss. As a matter of fact, you can always use alt accounts to avoid penalties and consequently a major rating loss. :vHere are 2 of many examples how it's done:
•  » » » 5 months ago, # ^ |   0 if u copy-paste the same code on different id's wouldn't that leads to plagiarism?
•  » » » » 5 months ago, # ^ |   0 That is unethical certainly, but not 'plagiarism'Plagiarism, the term itself, is defined as 'the practice of taking someone else's work or ideas and passing them off as one's own.'So, your answer is: no, not unless you copy from someone else.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -39 I am sorry. I do not do that again though i left that habit already sir .
•  » » » 5 months ago, # ^ |   +25 this is literally strictly against the rules
 » 5 months ago, # |   0 I think this is going to be a interesting Contest !!!
 » 5 months ago, # |   +73 Um_nik's comment has been deleted!
•  » » 5 months ago, # ^ |   +37 Probably for the best, it was not tasteful. I'm kinda surprised that I didn't get readonly for that. Looks like KAN tries to be a peacemaker)
•  » » » 5 months ago, # ^ |   +17 With all due respect, sir, the comment was not good!
•  » » » 5 months ago, # ^ |   +26 What was the comment about?
 » 5 months ago, # |   +2 Hope for strong pretests lol
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 They were even stronger than vibranium lol (Atleast in Div2?)
 » 5 months ago, # |   0 Might see a big change to Top Rated?This is a very friendly time for Chinese players.Get a higher rating!
 » 5 months ago, # | ← Rev. 2 →   -8 Hello, What about score table ch_egor? (before showing score table) thank you very much I get my Ans Now!(now)
 » 5 months ago, # |   -16 We kindly ask all the community members that are going to participate in the competition to show sportsmanship by not trying to cheat in any manner. This is quite important I think, and I hope this will be added to all the announcements of the contests in the future.I also hope that everyone will remember: Due to the official competition source codes of other participants will not be available for an hour after the end of the round. So please DO NOT discuss about the problems especially the solutions during the one hour after the contest is over. (It seemed that this happened last time.) Hope for strong pretests, too!
 » 5 months ago, # |   0 Due to the official competition source codes of other participants will not be available for an hour after the end of the round. Does this mean we will not be allowed to discuss the problems for an hour after the end of the round? (If so, I think it should be written somewhere because right now it is not very clear.)
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 They updated it now: Please do not discuss problems publicly until 12:30 UTC.
 » 5 months ago, # |   -8 Scoring distribution shows us that this contest will be HardForces
 » 5 months ago, # |   -28 2.5 hours for 6 problems!!!It tells about the difficulty level of the "Problemset".
 » 5 months ago, # |   -41 hope this time i will get positive delta
 » 5 months ago, # |   -28 What a mindfuck contest.
 » 5 months ago, # |   -26 Im outta here. Ratings go brrrrrrr
•  » » 5 months ago, # ^ |   +12 and this is why you don't improve
•  » » » 5 months ago, # ^ |   -7 I honestly want to. I had bad last couple days so mind is not at peace.You know the saying "It is possible to commit no mistakes and still lose. That is not a weakness; that is life."? That's what's happening in life outside CP.That's it. Thanks for coming to my TED talk. And thanks for judging.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +209 YEAH!
•  » » » » 5 months ago, # ^ |   +10 OMG....Feeling sorry for you
•  » » » » 5 months ago, # ^ |   +37 this is so much pain in a single photo :( xD
•  » » » » 5 months ago, # ^ |   +11 This is very sad, but enough of the honor to try until the end!
•  » » » » 5 months ago, # ^ |   +11 Salute your efforts!!!
•  » » » 5 months ago, # ^ |   +7 Classic codeforces crowd. Sucking based on colours.
 » 5 months ago, # | ← Rev. 2 →   0
 » 5 months ago, # |   +266 .
 » 5 months ago, # |   +13 I liked the baiting in score distribution
 » 5 months ago, # |   +55 Even those who couldn't solve A, solved C and most of them are green or newbie
•  » » 5 months ago, # ^ |   +4 Really! C is surely not that easy. Something is wrong here. But A was tougher than B. The test cases in A could have been explained more clearly. But that's part of the contest, I mean understanding the test cases.
 » 5 months ago, # |   0 Expecting Strong Pretest...
 » 5 months ago, # |   +15 Codeforces Round #707 (Div 1, Div 2)Codeforces Round #707 (Div 0.5, Div 1.5)
•  » » 5 months ago, # ^ |   -46 There is no way this could be Div 0.5.
•  » » » 5 months ago, # ^ |   +9 But it's surely div 1.5 , atleast for me :(
 » 5 months ago, # | ← Rev. 2 →   0 Can tourist submit D on time? What you guys say
 » 5 months ago, # |   +61 Div 2A was just disgusting.
•  » » 5 months ago, # ^ |   -10 div1 A,B as well
•  » » 5 months ago, # ^ |   0 Why so?
•  » » 5 months ago, # ^ |   +3 +1 for IU picture! <3
 » 5 months ago, # |   +19 tourist be like: " Div1 D? Let me just solve E and F instead..."
 » 5 months ago, # |   +35 don't know why but i feel lot of fst in problem C
 » 5 months ago, # |   +223
•  » » 5 months ago, # ^ |   +23 lol same
•  » » » 5 months ago, # ^ |   0 in Div 2; there are only 12 pretests. So the tests for Div1 and Div 2 are not the same?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +11 phew
•  » » 5 months ago, # ^ |   +6 Was this yours? I wanted to know whether it was accepted after reJudging or not, But when I entered on your submissions, I found that you had not reached Test 15 in the B problem in time of contest! Did this solution get accepted after the reJudging?
 » 5 months ago, # |   +8 100% have cheating in this contest.
 » 5 months ago, # |   +26 Using 30 minutes for reading A 10 times, and I still don't understand its statement now.
•  » » 5 months ago, # ^ |   0 Then how did you solve it?
•  » » » 5 months ago, # ^ |   +7 Just guess
•  » » 5 months ago, # ^ |   0 Agree.
•  » » 5 months ago, # ^ |   +9 I honestly wouldn't be surprised if I got failed system test or something on A. I basically did the same. Just tried to guess what the author meant until the example tests worked.
 » 5 months ago, # |   -10 Unbalanced difficulties but nice problemset. I enjoyed it.
 » 5 months ago, # |   +13 B was easier to solve and code compared to A in DIV 2
•  » » 5 months ago, # ^ |   0 A was too hard to understand. Looks like it was google translated :P
•  » » 5 months ago, # ^ |   0 That's absolutely true. And reading A is just too time-consuming!
 » 5 months ago, # |   +89 WTF, I think the correct contest duration is 2.5 days instead of 2.5 hours.
 » 5 months ago, # |   -6 Very brainstorming and skillful contest.
 » 5 months ago, # |   0 Shouldn't Div2.D run for lcm(n, m);?? then I used a map for freq-> index
•  » » 5 months ago, # ^ |   0 i got tle with this approach
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 deleted
•  » » » 5 months ago, # ^ |   0 ,but how would it be correct if I used a lower number for simulation?
•  » » » » 5 months ago, # ^ |   0 Why are you discussing.
•  » » » » » 5 months ago, # ^ |   0 I just noticed that.I would delete it
•  » » » » » » 5 months ago, # ^ |   0 how to delete this?
•  » » » » » » » 5 months ago, # ^ |   0 I don't know!!
•  » » » » » » » » 5 months ago, # ^ |   0 Looks like the only way to do this is to ask Codeforces admins: KAN, geranazavr555 and MikeMirzayanov
 » 5 months ago, # | ← Rev. 2 →   +61 Am I the only one who didn't notice that all $a_i$ and $b_i$ are distinct in Div1 B?Even worse, the problem is solvable without that assumption, but my $O(n\ log\ ANS)$ implementation got TLE (thanks to the miserably tight constraints and time limits...). Spent the whole contest trying to optimise that code >_>
•  » » 5 months ago, # ^ |   +20 Same thing happened with me.It took me 1hr to notice that even author highlighted that.
•  » » 5 months ago, # ^ |   +28 I didn't notice at first too, and an hour was wasted:(
•  » » 5 months ago, # ^ |   +37 I didn't notice too. After noticing and making the constant better still TLE btw, so it also required squeezing.
•  » » » 5 months ago, # ^ |   +23 Same here. It was an absolutely miserable experience.
•  » » 5 months ago, # ^ |   +38 I didn't realize it until I saw your words just now :(
•  » » 5 months ago, # ^ |   0 Can you explain how it can be solved if elements weren't distinct? I used a different approach so couldn't grasp the idea in your code.
 » 5 months ago, # |   +4 How to solve Question C?
•  » » 5 months ago, # ^ |   +2 I guess we can discuss the problems after 1hr from completion
•  » » 5 months ago, # ^ |   -35 Since a[i] <= 2.5 * 10^6 we can get atmost 5 * 10^6 different sum. which is possible by any N >= sqrt(5 * 10^6 ) so we can take N as 10^4 and we can optimize to O(N^2) Solution
 » 5 months ago, # |   +16 Me after reading the D2A problem. Petr on Bad Problems
 » 5 months ago, # |   -8 Finally AC!!
•  » » 5 months ago, # ^ |   +8 It's so cool to keep trying to the end, But why did you spend 2 hours and 17 minutes on problem C? You could have solved problems A and B quickly
•  » » » 5 months ago, # ^ |   +10 Solving problems A and B will not help me anyway. I want to improve. Each time after the contest I regret that I can solve one more during the contest, but could not solve due to nervousness and lack of time. So, from now, I am planning to solve difficult problems first during the contest time. Starting 2 problems are just based on reading the problem, understanding it and then typing it (without much thinking). If you look at my rating graph, I reach around 1700 and then fall down, that too from more than 6-7 months maybe. I usually solve div 2 A B C and after the contest I realise that I could even solve D if I had time (or even if I had sufficient time then I don't know why negative thoughts come into my mind that i could not solve it). So, I just want to gain confidence that I can solve difficult problems in the contest time as well, and when I will gain confidence then I will start from the problem A.
•  » » » » 5 months ago, # ^ |   0 wah bhaiya! i too have same thoughts and gonna follow this for sure.
•  » » » » 5 months ago, # ^ |   -6 Inefficient strategy. If you end up solving D, still you would be late and you won't get enough points due to penalties. Then, you would have only time for A and B, still you would face huge penalty.
•  » » » » » 5 months ago, # ^ |   +9 As i said that i just want to gain some confidence and remove the negative thoughts from my mind. Ratings don't matter to me much. It can be increased at any time if I am capable enough.
 » 5 months ago, # | ← Rev. 3 →   +36 Again this where bad problem statements for Div2.A is nothing else than a complected problem statement, and the whole thing about the problem is understanding the text. This is, honestly, the worst kind of problems we can get. This is even worse than asking for some googleable formular or the like.B needs at least a bit fantasy for implementation, but still the main part is understanding what the statement wants to tell us.C is nice statement, but implementation needs (at least for me) a lot of edge-case searching. So, this problem was again like 5 minutes thinking, then 2 hours asking "What did I get wrong here?". That is good for educational contest.Maybe the other problems where super creative, but 90% of the partitipants did not even read them.Edit: And of course, E, F where to hard. No Div2 solved any of them.
•  » » 5 months ago, # ^ |   +55 'That is good for educational contest.' No it's shit for any type of contest.
•  » » » 5 months ago, # ^ |   0 I think the contract for Educational contest is that boring implementation heavy problems are ok, because beginners need to learn implementation skills.
•  » » 5 months ago, # ^ |   0 Straight forward implementation for C: https://codeforces.com/contest/1501/submission/109849688
 » 5 months ago, # |   +88 Timelimits in B, C and D are a joke. Don't know about E, but looks hard too.
•  » » 5 months ago, # ^ |   +10 Do you know what's the problem with GNU C++17 (64)? I noticed that you changed compiler to C++14 and got OK, and did the same, but there are some people who have OK with C++17.
•  » » » 5 months ago, # ^ |   +10 But it was only in C. My guess (but I'm not an expert here) is that jumping over the memory is slower with 64bit compiler.
•  » » » 5 months ago, # ^ |   +70 I'm pretty sure that (one of) the slowest part of the solution in all these three problems is reading input. scanf is very slow on GNU C++17 (64), while cin (with ios_base stuff) is fast. The opposite is true for MS C++ 2017 (scanf is fast, cin is slow).
•  » » » » 5 months ago, # ^ |   +28 You are right, on GNU C++14 both cin and scanf work 0.9 seconds, while on GNU C++17 scanf gets TL and cin works in 0.5 seconds. :(
•  » » 5 months ago, # ^ |   -19 You mean too low or too high? My solution for C ran in 1.2s and for B in 1.5s, I'd set both to 3s just to make sure but it's not that much different. D has plenty of reserve time, my solution runs in 1.7s.
•  » » » 5 months ago, # ^ |   +2 To low. In B and C I had hard time, both take more than a half of a time limit while being more or less optimal. In D I also had no problem (it's a miracle btw, I had $O(n^2 \cdot q \cdot \log(q))$), but I see many people in the standings having some TLEs, while I guess their solutions also have correct complexity.
•  » » » » 5 months ago, # ^ |   -18 Yeah, that log seems excessive. I can't see solutions but I expect a lot of overcomplicated shit in B, C and D since I almost fell into the trap of trying to bash out an ugly code for a nice idea several times during this contest.
 » 5 months ago, # |   +72 Does anyone else think that after a certain point in the contest, the submissions for C grew exponentially? When I see the standings, I can see more pupil, newbies and specialist having AC when compared to blue, which is very weird. Not trying to be ratist but I've never seen this kind of acceptance rate for a problem like C.
•  » » 5 months ago, # ^ |   +3 Only 4 people in my room managed to solve the problem. 3 of them are grays and blue was last to submit AC...
•  » » » 5 months ago, # ^ |   -6 I hope they all got FST.
•  » » 5 months ago, # ^ |   0 This is what happens when the problem is actually of nice easy observation. And I like it
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 some couldn't even solve A but somehow solved C
•  » » 5 months ago, # ^ |   +21 don't worry it's pretest are too weak
•  » » 5 months ago, # ^ |   0 Probably solution is available in the internet . they just find out from net after that certain point of contest
•  » » 5 months ago, # ^ |   0 what's wrong with expecting higher rated participants to be above lower rated participants in standings? Isn't that the whole point of 'rating'. 'ratism' is a stupid concept
 » 5 months ago, # |   -30 I hope I wasn't the only to solve Div2C/Div1A with NTT. Thanks to AtCoder Library I passed pretests in 1.6s out of 2 second. In general, AC library turned out very useful for me this contest as D2D/D1B required CRT, which is implemented there as well.
•  » » 5 months ago, # ^ |   0 i was getting runtime on 6
•  » » 5 months ago, # ^ |   0 What does NTT stand for?
•  » » » 5 months ago, # ^ |   0 I meant DFT (discrete Fourier transform) modulo prime number. It's actually just fast polynomial multiplication; you can treat this algorithm as a black box in many cases. I believe NTT stands for Number Theoretic Transform, but that's a coloquial term. Below is the link describing formally what it does exactlyhttps://github.com/atcoder/ac-library/blob/master/document_en/convolution.md
•  » » » » 5 months ago, # ^ |   0 Thanks for the info! I've only used Atcoder Library on atcoder contests but I think I'll start using it on codeforces as well.
•  » » 5 months ago, # ^ |   0 can you please explain me how to apply NTT to such problems or tell me some resources from where i can learn application of NTT(appart from cp algorithm).
•  » » » 5 months ago, # ^ |   +3 I'm afraid I don't have a better source. You should learn about polynomials in general and the application of polynomial multiplication in combinatorics. You can use any Math textbook of your choice. In fact, this very NTT application that I used (with a minor modification) is described on cp-algorithms https://cp-algorithms.com/algebra/fft.html#toc-tgt-9
 » 5 months ago, # |   +8 weak pretests on 1A/2C.
•  » » 5 months ago, # ^ |   0 This means my solution is going to fail sys test:(
 » 5 months ago, # |   +3 Is there a O(n) or O(nlogn) solution for C ?
•  » » 5 months ago, # ^ |   0 I solved using FFT in O(M*log(M)) time complexity. M = 2*2.5*1e6
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 My solution was to solve for $n <= 2e4$ with an $O(n ^ 2 log n)$ algorithmAnd for $n > 2e4$ there will be $2$ positions with equal adjacent differences after sorting($i, i + 1$ and $j, j + 1$, $i < j$) and those can be the four indices.Idk it might FST.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 i set n as 1600 rip
•  » » » » 5 months ago, # ^ |   0 AC :)
•  » » » » » 5 months ago, # ^ |   0 hi5
•  » » 5 months ago, # ^ |   0 If you are talking about Div2 C then you just need to notice that the possible sums are just 2*M (M is the max a[i], that is to say 2.5*1e6) so you can just iterate over all pairs and you get a solution in O(min(n^2, m))
 » 5 months ago, # |   +28 cheatforces!
 » 5 months ago, # | ← Rev. 3 →   0 My reaction while reading prolem 2A was similar to https://www.youtube.com/watch?v=KNviwfDeRKg
 » 5 months ago, # |   -14 Solved Div 1A using FFT, missed a silly observation.. how stupid I am.. :/
•  » » 5 months ago, # ^ |   -8 How to solve it normally? I tried randomized approaches but none worked
•  » » » 5 months ago, # ^ |   0 We know that sum of two elements is <= 2*2.5*1e6. So, iterate using two for nested loops, and do, v[a[i]+a[j]].pb({i,j}); if(v[a[i]+a[j]].size() == 2){ // print } complexity is min(n^2,2*2.5*1e6)
•  » » » » 5 months ago, # ^ |   0 But for iterating over the entire arr it would be n^2. Can you explain to me how it will be a minimum of n^2 and 5*1e6 and not maximum?
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   +5 You stop when some sum is created twice. There are at most $5e6$ possible sums, so you do at most that much work.
•  » » » » » » 5 months ago, # ^ |   0 Got it!!!
•  » » » » 5 months ago, # ^ |   0 Got AC with the same idea.
•  » » » » 5 months ago, # ^ |   +4 This might not work. e.g 1 3 1 4 notice index (1, 2) and (2,3) have same sum but they are not unique. I used map to remove this which resulted in TLE, i was too lazy to implement without map.
•  » » » 5 months ago, # ^ | ← Rev. 3 →   0 FST
•  » » » 5 months ago, # ^ |   -8 I use $O(n^2\log n)$ brute-force for $n \leq 3000$, and for $n \geq 3000$, run 1.9s random check. If can't find the answer then print NO. I don't think it can survive in system test
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -8 I think I got the idea, but I had no time to work it out, but the idea is probably first we check if there are more than 3 equal elements, if so output them. If not, then notice that a+b=c+d is just like saying find two pairs with same difference, and for that let’s consider differences of contiguous elements(sorted array) and count them. If we find a difference which appears more than 2 times, we can output the corresponding 4 elements(heavy implementation). If this does not find us any pair, then we can just brute force it because the number of elements should not exceed sqrt(10^6) or something.
•  » » » 5 months ago, # ^ |   0 There is definitely an answer among the first 3163 elements no matter what, so you can do O(n^2), ignoring most of the input
•  » » » » 5 months ago, # ^ |   0 Why 3163? Can you elaborate this please?
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, it's because (3163 choose 2) > 5 million
•  » » » 5 months ago, # ^ |   0 We have to find $x$, $y$, $z$, and $w$ such that $a_{x} - a_{z} = a_{y} - a_{w}$. Let's create set of integers and iterate through all pairs  in $[1,n]$, check, if the number $a_{i} - a_{j}$ is in set, if yes, print answer, otherwise insert $a_{i} - a_{j}$ into set. Due to Dirichlet principle, the number will be found in no more than $C = 2.5 \cdot 10^{6}$ iterations. Also it means, that if $n \ge \sqrt{C}$, answer is YES.Also remember, that we can bring one pair of iterators $x, y, z, w$ equal. Look at cycles in my submition, it can happen there no more than one time, so the total number of iterations is $\le 2C$.
•  » » » » 5 months ago, # ^ |   0 Can you give some content about the Dirichlet principle you're talking about? (Preferably YouTube)
•  » » » » 5 months ago, # ^ |   0 Can you elaborate on the Dirichlet Principle that you are using here? Why the next pair be found within C = 2.5 * 10**6 iterations?
•  » » » » 5 months ago, # ^ |   +1 Dirichlet principle is quite obvious statement: if there are $n$ holes and we put $n+1$ balls there, there has to be a hole with $2$ or more balls.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 I used to know it as pigeon hole principle
 » 5 months ago, # |   -6 Anyone noticed the weird constraint for the elements in Div2C?
•  » » 5 months ago, # ^ |   +3 Why so much down votes in this comment? Did I say someting wrong?
 » 5 months ago, # |   +26 And some interesting fact: you can pass Div2 C's pretest by just simple rand().
•  » » 5 months ago, # ^ |   0 What is the idea?
•  » » » 5 months ago, # ^ |   0 linkAnd it can pass system test. I got fst because I made a very very stupid mistake in brute-force part :(
 » 5 months ago, # |   +6 Thanks the organizers for this contest although I may suffer from a minus delta. At least it has given me the chance for a successful hack, which did not happen since June 2020 :-)
 » 5 months ago, # |   -9 How to slove TLE in problem 2 in div 2?
•  » » 5 months ago, # ^ |   -10 Use difference array
•  » » » 5 months ago, # ^ |   -8 Can we discuss? I am getting runtime error then WA on pretest 2.. Shall I share my submission?
•  » » » » 5 months ago, # ^ |   -8 message me
 » 5 months ago, # | ← Rev. 3 →   -163 It's a good game!
•  » » 5 months ago, # ^ | ← Rev. 2 →   -100 Fun!
 » 5 months ago, # |   +55 Will the system testing be done right now or an hour later?
 » 5 months ago, # |   +5 Please do not discuss problems publicly until 12:30 UTC.
•  » » 5 months ago, # ^ |   0 I think disable comments for that time would help as this is where people wold discuss the problems.
 » 5 months ago, # |   +73 I think div1a should be easier or we should have open-then-rated system.I am pretty sure atleast a 200 people didn't submit anything because they couldn't solve anything in div1.
 » 5 months ago, # | ← Rev. 4 →   +11 In today's contest something was weird ,In standing I saw many who has solve d2C but made wrong on d2A/d2B.....And C was not that easy!? Or Do I missed any trick???Yeah As I guessed Same question was available on gfg link
•  » » 5 months ago, # ^ | ← Rev. 3 →   +3 There is a simple observation that makes it easy -- if you see it, you can get AC quickly
•  » » » 5 months ago, # ^ |   +1 No, this is an implementation problem, too. And there are edge cases with duplicate numbers... I had the right idea after some minutes, still needed 8 WA and more than an hour to get it right.
•  » » » » 5 months ago, # ^ |   +3 I initially thought that the edge cases mattered, but it seems that a "naively" written solution still passes.No matter what, there is always going to be a solution among the first 3163 elements, regardless of the presence of duplicates.Check this out: https://codeforces.com/contest/1500/submission/109893462 (no edge cases)
•  » » » » » 5 months ago, # ^ | ← Rev. 4 →   0 can you explain, why the answer would be found in first 3136 elements?As : what would happen when the answer is no and tc consists of constraints limits in that case it would be n^2 which is around 4*10^10 iterations . [UPD : understood]
•  » » » » » 5 months ago, # ^ |   0 This is much simpler and intuitive, thanks for sharing!
•  » » » 5 months ago, # ^ |   +8 it took me more than an hour to see this easy observation. also solving C and not able to solve A or B looks a bit fishy tbh.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 I think what happened is that many people who submitted C didn't make the observation. A naively written solution could still pass.So, check out this submission here: 109894474 I cleared the map each time to simulate a solution that uses a map to a single pair. I even commented out the line that reduces n to 3163, to demonstrate that it is possible to get AC without actually making any sort of observation (recall, many people who are just starting out would still implement an O(n^2) algorithm when n >= 10^5 if they didn't know a better one)I guess this explains it (I guess the test cases are weak as well)
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Yes, I agree with this. Some people just implemented the n^2 algorithm without knowing why it worked.
•  » » » » 5 months ago, # ^ |   +7 Cause C was available on gfg while a nd b not
•  » » » » » 5 months ago, # ^ |   +1 And dumb me didn't implemented it thinking that it would give me TLE.
•  » » » » » 5 months ago, # ^ |   0 Problem C — Uneven TCs? For some reasons, there are weak Test Cases. Testcases only contain N<1000 which is easily acceptable in N^2. Moreover, in a few test cases N=200000 but in those TCs the N^2 approach is getting completed in N. This is somewhat unfair for those who don't submit the solution because of N^2 TLE reason. There may be other proofs that will prove that N^2 will never give TLE but thinking a general way, it won't.
•  » » » » » » 5 months ago, # ^ |   0 actually, it can be proven that if you have an array of size greater than let's say 1000 then you'll always find an answer (hint a[i] is of 10^6 order). that's why the n^2 solution worked as it'll find the answer in some starting 1000 elements of the array itself. hence it was the intended solution. I hope it clears everything.
•  » » » » » » » 5 months ago, # ^ |   0 Yes, but how to prove it?
•  » » » » » » » » 5 months ago, # ^ |   0 You've a[i] of order 10^6 means 10^6 — 1 unique differences available lets say this equals t. Also, in an array of size n, we have nC2 ways of choosing 2 elements and hence nC2 differences available. If nC2 > t then by PHP, there'll be atleast one difference occuring more than once. Which limits n to some order of 10^3.
 » 5 months ago, # |   +32 In D1B, I wrote int posa[500005],posb[500005] and used $posa[a_i],posb[b_i]$. However $a_i,b_i$ might be $10^6$! Despite this fact, this program with too small array bounds passed pretests. I really wonder how strong pretests are.
 » 5 months ago, # |   0 I'm afraid of system testing
 » 5 months ago, # |   0 Can somebody give me a hint on how to approach DIV-2 problem-C. I am totally clueless about how we can do it in less than O(n^2)
•  » » 5 months ago, # ^ |   +11 The sum of the two numbers must be less than 5e6, and you can find the answer at most 5e6 times.
•  » » » 5 months ago, # ^ |   0 Had this idea 1 hour before ending, couldn't evolve it further :(
•  » » 5 months ago, # ^ |   0 You don't have to implement it less than that. O(n^2) solution will pass the test cases. Don't know the reason though.
 » 5 months ago, # | ← Rev. 5 →   -37 The initial problem scores seems too small for me.:(QAQI solved 2 problems but my score is smaller than some people with 1 problem.Let's admire the great score setter.
•  » » 5 months ago, # ^ |   -16 BTW, if the number of my incorrect submissions * 50 > the score according to the accepted time will I get less perf?:(
•  » » » 5 months ago, # ^ |   0 You get at least 30% of initial score
 » 5 months ago, # |   +9 I didn't like div2A, spent 15+ mins trying to understand the statement
•  » » 5 months ago, # ^ |   0 The same.I spent 13 mins on A, but only 11 mins on B.
 » 5 months ago, # |   0 I don't know what's wrong with me, I literally completed A 15 minutes before the contest ends, then I thought there would not be ample amount of time left for even B, so I was just browsing the blogs. Then, I took a look at the question and I was like, why was A >>>>>>>>>>>>>> B in terms of thinking. I literally thought B would be much harder, and thus now sad noises are coming from the corner of my room. :')
 » 5 months ago, # |   +16 Nice random scores on ACD.D: easiest — in the same way as with 2D prefix sums, for each top left corner $(r,c)$ you just list "colour, smallest square for which we first see it" for the first $Q+1$ such colours; this list is created by merging the lists for squares with top left corners $(r+1,c)$, $(r,c+1)$, $(r+1,c+1)$ in linear time and that directly gives us the answersB: alright, not trivial, not too hard, obvious binsearch and some number theory behindA: Not The First Problem In The Contest Please! I solved it mainly by noting that if there are many different values (around $\sqrt{\max A_i}$), the answer always exists and we can ignore all except those few values to find it. Otherwise, there are some special cases — if there are 2 values that occur at least twice or one that occurs at least 4 times, the answer is obvious; if all values used in the sums are different, bruteforce works; and finally, there's the case $a+a=b+c$. It could be a 500-750pt A if it was just a yes/no problem and all values were guaranteed to be different, but this way, there are just way too many details to consider. Harder than B or D.C: Nice problem, requires not getting bogged down in implementation even if you know the gist of what you want to check. The matrix A is almost irrelevant — we're splitting $B$ into chunks of rows. If there's an axis $a$ such that each chunk is increasing along that axis, and there's a chunk that contains at least 2 different values on that axis, we can "unsort" by $a$, splitting this chunk between rows that have different values on axis $a$. If we consider sorting instead of unsorting, in reverse order, we find that as long as the rows in each chunk are originally in the same order, we'll end up with $B$. Vice versa, any other unsorting means we'll never obtain $B$ since something would be sorted in a way we don't want. When there's no more splitting possible, we hash the rows and check if we can build $A$ by merging the chunks of rows we have at the end without changing the order in each chunk.In implementation, it's essential to notice that the conditions "is increasing along axis" and "has at least 2 different values on axis" don't need to be checked for chunks, only for adjacent rows. We discard pairs of adjacent rows that are already in different chunks, and for each axis, we remember how many remaining pairs are strictly decreasing and which ones are strictly increasing. When splitting between two rows, we only update these conditions for this pair of adjacent rows and each axis, and this way, we only check each pair of vertically adjacent values once, leading to $O(NM \log)$ complexity.There's also the question: can two identical rows end up in different chunks? If that happens, then there must be a split along some axis that had values $a, \ldots, b, c, \ldots, a$ in one chunk in $B$, where at least one of $b,c$ is different from $a$ and the split happens between rows with $b$ and $c$. However, the first time this happens, this chunk can't be increasing — the value among $b,c$ that's different from $a$ is either larger than the next $a$ or smaller than the previous $a$. That means the answer is no, all rows with the same value must be in the same chunk, and that greatly simplifies the final check with hashing — if we're adding a given row to the end of partially built matrix $A$, we know which chunk we must take it from.
•  » » 5 months ago, # ^ |   0 I believe there's no real need for special cases, just take a looser bound — the special cases get accounted for fast.
•  » » » 5 months ago, # ^ |   0 If so, that's a different thing you need to pay attention to. The difficulty of a problem shouldn't be assessed by "I'll guess that with a loose bound, this is all I need", but how hard it is to figure out why a given solution works.
•  » » » » 5 months ago, # ^ |   0 Maybe? The thing is, if $N$ is much higher than $\sqrt{max A_i}$ and there are still less than $\sqrt{max A_i}$ distinct values, surely there are two pairs of equal elements.
 » 5 months ago, # |   +75 My Div1C passed pretests even I typed n instead of m somewhere. It was so scary.
•  » » 5 months ago, # ^ |   +54 It somehow passed systests(and hacked by myself).
 » 5 months ago, # | ← Rev. 2 →   +19 Dont we all agree that most of the C accepted submissions were from GeeksForGeeks!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Div2 C? Could you please provide the link? Got it: https://www.geeksforgeeks.org/find-four-elements-a-b-c-and-d-in-an-array-such-that-ab-cd/
 » 5 months ago, # |   +18 Div1C can be solved with "bitset" in O(N^3/w)
•  » » 5 months ago, # ^ |   +24 I also used bitsets, but it only passed after I put in this pragma from Chilli: https://codeforces.com/blog/entry/77480. The runtime was 1996 ms, which was really scary. Thanks Chilli!
•  » » » 5 months ago, # ^ |   0 You are very lucky :)
•  » » » 5 months ago, # ^ |   +8 bruh
•  » » 5 months ago, # ^ |   -11 Apparently bitset isn't needed. My O(n^3) passed without bitset.
•  » » » 5 months ago, # ^ |   0 Orz
 » 5 months ago, # |   +1 Great problems, thanks!
•  » » 5 months ago, # ^ |   +7 +1Problems C & D were very nice.
 » 5 months ago, # | ← Rev. 2 →   +115 Good contest with strong pretests, especially in problem B and problem C.What's more, the tl of problem B and the ml of problem D are very friendly. No one can get TLE or MLE on them.
 » 5 months ago, # |   0 Can somebody explain me in short how to solve DIV2 problem-C. I was very clueless about how to solve it in less than O(n^2)
•  » » 5 months ago, # ^ |   +4 Think of brute force, and show that it'll work using the pigeonhole principle
•  » » » 5 months ago, # ^ |   0 Brute force would be to calculate sum of all pairs. Which itself is n^2.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 n^2 is enough to pass time limitsmy submission https://codeforces.com/contest/1501/submission/109856495
•  » » » » » 5 months ago, # ^ |   0 It is min(n^2,10^6). That's why, It pass time limits.
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 what would happen when the answer is no and tc consists of constraints limits in that case it would be n^2 which is around 4*10^10 iterations . [UPD : understood]
•  » » » » » » » 5 months ago, # ^ |   +3 Pair sum can be from 2 to 5*10^6. Let's assume you are doing 10^7th iteration so there will be at least one pair sum which have more than 1 frequency and have distinct indexs.So, Answer will be always Yes for large N values.
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 I don't get it, for me n<=10^5 tells me that n^2 solutions don't work..I thought an hour of how to get a lower complexityI even looked up in cp4 handbook, and they say only if n < 10^4 you can use n^2, so I was certain it won't work...
 » 5 months ago, # |   -8 I spent about one and half an hours to deal with div2C. End up finding the solution is so brute made me really sad...
 » 5 months ago, # |   +22 I resubmitted my TLE code during the contest and got an AC. Can anyone explain why? Can we rejudge? Sorry to disturb you.
•  » » 5 months ago, # ^ |   +11 You have used in 2nd submission gnu c++ 17 instead gnu c++ 17(64).
•  » » » 5 months ago, # ^ |   0 Sorry, I don't know the difference.
•  » » 5 months ago, # ^ |   0 Same for me...Contest TLE: https://codeforces.com/contest/1500/submission/109868976 Resubmitting AC: https://codeforces.com/contest/1500/submission/109893896
 » 5 months ago, # |   +52 My code with scanf can't pass div1 C, but it only takes 102ms after switching to fread. How could such thing happen on codeforces?
•  » » 5 months ago, # ^ |   +15 Its called Miracle dood:)
•  » » 5 months ago, # ^ |   0 scanf becomes much slower, if stdio.h is not included as first header working with streams, which is your case.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Iss contest mei kuch bhi ho raha hai yaar (Miracle) MikeMirzayanov Please look into it as just by changing C++17(64) to C++17 can get you AC.
 » 5 months ago, # |   +1 Hi, I had a query regarding my submission of the Div2(C) Going Home question. I had submitted two submissions for that question. My first submission got skipped and the second submission got accepted .The second was optimized solution as compared to first solution. But the first solution would have worked also because I had submitted the first submission again after the contest was over and got accepted. If my first solution was checked then I would have got much better rank. I would like to know more about why this happened?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +9 I am sorry to hear that. But it is because of the rule of Codeforces. Only your last submission to a problem will be considered as your valid submission. And if it gets AC, all your previous submissions will cost 50 points.If you want to know why it is designed in this way, let me explain in a deeper way. There are typically two types of competitive programming contests. One is judging real-time and the other is judging after contest ends. In a real-time judging contest, participants can try many times for a problem until they get AC. But in the other type of contests, participants must specify one submission as they final submission for each problem. Just like taking exams, you can not submit many answers to the teacher and say "Hey, please check all my answers. If one gets passed, then I get credit."Because Codeforces enables real-time testing, you may think Codeforces is the first type contests. However, in my opinion, Codeforces rounds are much more like the second type. Because it just does pretests during contests. Nobody knows the system test result until contest ends.So, in the next Codeforces round, please remember not to resubmit if you think you have given a correct answer.
 » 5 months ago, # |   +12 It got TLE in contest DIV1 B https://codeforces.com/contest/1500/submission/109868976, but resubmitted got AC: https://codeforces.com/contest/1500/submission/109893896Is this supposed to happens?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Can you please explain why this solution for div2 A is giving wrong answer https://codeforces.com/contest/1501/submission/109849523
•  » » » 5 months ago, # ^ |   0 Don' use b[i] — a[i]+ 1. It will fail if b[i] — a[i] is even. It should be ceil((b[i]-a[i])/2.0).
•  » » » » 5 months ago, # ^ |   +8 (b[i] — a[i] + 1) / 2 is perfectly fine for ceiling...
•  » » » » » 5 months ago, # ^ |   -9 My mistake.
•  » » » 5 months ago, # ^ |   0 Your Ac code,with little modification
•  » » » » 5 months ago, # ^ |   0 Thank you I get it now
•  » » 5 months ago, # ^ |   +8 Me too.
 » 5 months ago, # |   0 Can somebody explain me why O(n^2) is accepted for n<=200000 in DIV-1A (DIV-2C)?
•  » » 5 months ago, # ^ |   +1 You will find a solution before than all operations. Worst case there are 2.5⋅106 + 2.5⋅106 possible values(a+b)
•  » » 5 months ago, # ^ |   +4 I suppose you are looking at a brute force solution. If you already cleared out the a+a=a+a and a+b=a+b case, then there is at most one value appearing more than 1 time, and it does not appear more than three times, let's call it v. Later you will discover that this is not important, but let's first assume that v appears only one time. Then, since a[i]<=2.5e6, so the sum of two elements <= 5e6, so if there are >5e6 pairs, at least one will collide. That's why the brute force solution always exits and will pass.
•  » » » 5 months ago, # ^ |   0 does that mean if n > sqrt(5e6), the answer is true anyway?
•  » » » » 5 months ago, # ^ |   0 yes
•  » » 5 months ago, # ^ |   0 you can use the pigeon hole principle to understand why a solution always exists for n > sqrt(5e6), and this is the reason Bruteforce works here
 » 5 months ago, # |   +24 AC:https://codeforces.com/contest/1500/submission/109898116 TLE:https://codeforces.com/contest/1500/submission/109870735 It's the same Code. I submit it after the contest several times and all get accepted but got TLE during the contest...
»
5 months ago, # |
-23

# HAPPY CODING

 » 5 months ago, # |   0 My clean 30 Line code to DIv2 C. only based on pigeonhole principle. 109899822
•  » » 5 months ago, # ^ |   0 My $O(n^2logn)$ solution using hash table don't know it but passed ^_^
•  » » 5 months ago, # ^ |   -10 Problem C — Uneven TCs? For some reasons, there are weak Test Cases. Testcases only contain N<1000 which is easily acceptable in N^2. Moreover, in a few test cases N=200000 but in those TCs the N^2 approach is getting completed in N. This is somewhat unfair for those who don't submit the solution because of N^2 TLE reason. There may be other proofs that will prove that N^2 will never give TLE but thinking a general way, it won't.
•  » » » 5 months ago, # ^ |   0 NO Man tcs have 200000 values at max. see test cases in my submission.
 » 5 months ago, # |   0 int128 -> long longTLE -> AC
•  » » 5 months ago, # ^ |   0
•  » » 5 months ago, # ^ | ← Rev. 3 →   +11 int128 is emulated by software while int64_t(by which long long is usually represented) is supported natively by hardware, so it is only natural that int64_t is faster in generalAlso your solution passed by such a narrow margin that it can be explained by just fluctuations.
 » 5 months ago, # |   0 Problem C — Uneven TCs? For some reasons, there are weak Test Cases. Testcases only contain N<1000 which is easily acceptable in N^2. Moreover, in a few test cases N=200000 but in those TCs the N^2 approach is getting completed in given time. This is somewhat unfair for those who don't submit the solution because of N^2 TLE reason. There may be other proofs that will prove that N^2 will never give TLE but thinking a general way, it won't.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +4 This is because there are total n*(n-1)/2 pairs of two numbers possible. So there can be maximum n*(n-1)/2 different sums possible.And from the constraint a[i]<=2.5*10^6. So, maximum possible sum will be 5*10^6.That's why when n*(n-1)/2 is greater than 5*10^6, then answer always exists. So, when n>4000, the there always exist a answer. Hence not getting TLE.:)
•  » » 5 months ago, # ^ |   0 Look at this submission : https://codeforces.com/contest/1501/submission/109911010 If you place 762 instead of 763 you will get WA on test 5. Can someone explain why this solution works for 763? I think someone can easily hack if they try. Tests were very weak!!