ch_egor's blog

Codeforces Round #707 (Div.1, Div.2, based on Moscow Open Olympiad in Informatics, rated)
By ch_egor, 4 years ago, translation, In English

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, budalnik, blyat, 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:

  1. tourist
  2. jiangly
  3. maroonrk
  4. ecnerwala
  5. Rewinding

Div. 2:

  1. 20I6wudi
  2. ShimaRin
  3. fengqiyuka
  4. gezlik
  5. b___
  • Vote: I like it
  • -695
  • Vote: I do not like it

Comments Comments (348)
| Write comment?
»
4 years ago, # |
← Rev. 3   Vote: I like it +35 Vote: I do not like it

amazing fact：in the first few minutes after the announcement is published，the announcement‘s rating is negative（？？？

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

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! >_<

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

    sorry to make the second comment meaningless too:<

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

    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.

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

      ?

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

      In my opinion, i suggest to virtual participation a contest so that you can enjoy the fun of problem solving and avoid $$$ - \Delta $$$

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

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish I can get perfect ranking and rating change.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +6 Vote: I do not like it

    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!

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

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.

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

Notice the unusual start time!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -91 Vote: I do not like it

As a contestant, I want to become a tester :) Why to many down votes

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

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! :)

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Amazing starting time. I can finally get rid of my regular 'drink coffee and have a stomachache during contest' cycle. Yay!

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

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.

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

From the past few weeks the unusual timing became usual to us.

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

    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.

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

      Wow, Americans must be doing contests with a fresh mind.. Nice

      → Reply
»
4 years ago, # |
  Vote: I like it -40 Vote: I do not like it

Why are some contests held at different times than usual? I think the usual timing is right for everyone!

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

    I think the usual timing is right for everyone !

    Sad American Noises from the corner

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

    Because some contests are mirrors of Russian OIs, like Open Olympiade or Technocup which held some hours before CF round.

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

    Happy Indian Noises Intensifies

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

    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.

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

Olympiad rounds are challenging and fun!

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

There are 22 writers in this contest. Can't believe it!!

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

I can bet this won't be an easy codeforces round. Expecting Div-2 to be Div-1.5 by the length of contest.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

Your last 2 contests had weak pretests. Hoping for strong pretests this time.

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

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?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

where are the "as a tester" comments!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

Too many reds means too many problems to upsolve :v (to learn) !

→ Reply
»
4 years ago, # |
  Vote: I like it -32 Vote: I do not like it

After see the author list and contest length. I am scaring about my rating :v

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

    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. :v

    Here are 2 of many examples how it's done:

    Screenshot-2021-03-14-12-47-06-737-com-android-chrome-01

    Screenshot-2021-03-14-12-37-31-746-com-android-chrome-01

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

      if u copy-paste the same code on different id's wouldn't that leads to plagiarism?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 3   Vote: I like it -39 Vote: I do not like it

      I am sorry. I do not do that again though i left that habit already sir .

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

      this is literally strictly against the rules

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

Um_nik's comment has been deleted!

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

    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)

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

Hope for strong pretests lol

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

    They were even stronger than vibranium lol (Atleast in Div2?)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Hello, What about score table ch_egor? (before showing score table) thank you very much I get my Ans Now!(now)

→ Reply
»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

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!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.)

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

    They updated it now: Please do not discuss problems publicly until 12:30 UTC.

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

Scoring distribution shows us that this contest will be HardForces

→ Reply
»
4 years ago, # |
  Vote: I like it -41 Vote: I do not like it

hope this time i will get positive delta

→ Reply
»
4 years ago, # |
  Vote: I like it -26 Vote: I do not like it

Im outta here. Ratings go brrrrrrr

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

51jsms.

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

I liked the baiting in score distribution

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

Even those who couldn't solve A, solved C and most of them are green or newbie

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

    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.

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

Codeforces Round #707 (Div 1, Div 2)

Codeforces Round #707 (Div 0.5, Div 1.5)

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

Div 2A was just disgusting.

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

tourist be like: " Div1 D? Let me just solve E and F instead..."

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

don't know why but i feel lot of fst in problem C

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

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

    lol same

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

    phew

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

    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?

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

100% have cheating in this contest.

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

Using 30 minutes for reading A 10 times, and I still don't understand its statement now.

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

    Then how did you solve it?

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

    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.

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

B was easier to solve and code compared to A in DIV 2

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

    A was too hard to understand. Looks like it was google translated :P

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

WTF, I think the correct contest duration is 2.5 days instead of 2.5 hours.

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

Very brainstorming and skillful contest.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Shouldn't Div2.D run for lcm(n, m);?? then I used a map for freq-> index

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +61 Vote: I do not like it

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 >_>

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

    Same thing happened with me.It took me 1hr to notice that even author highlighted that.

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

    I didn't notice at first too, and an hour was wasted:(

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

    I didn't notice too. After noticing and making the constant better still TLE btw, so it also required squeezing.

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

      Same here. It was an absolutely miserable experience.

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

    I didn't realize it until I saw your words just now :(

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

    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.

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

How to solve Question C?

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

    I guess we can discuss the problems after 1hr from completion

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -35 Vote: I do not like it

    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

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

Me after reading the D2A problem. Petr on Bad Problems

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

Finally AC!!

submission

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

    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

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        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.

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

          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.

          → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +36 Vote: I do not like it

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.

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

    'That is good for educational contest.' No it's shit for any type of contest.

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

      I think the contract for Educational contest is that boring implementation heavy problems are ok, because beginners need to learn implementation skills.

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

Timelimits in B, C and D are a joke. Don't know about E, but looks hard too.

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

    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.

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

      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.

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

      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).

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

        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. :(

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -19 Vote: I do not like it

    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.

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

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -18 Vote: I do not like it

        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.

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

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.

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

    Only 4 people in my room managed to solve the problem. 3 of them are grays and blue was last to submit AC...

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

    This is what happens when the problem is actually of nice easy observation. And I like it

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

    some couldn't even solve A but somehow solved C

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

    don't worry it's pretest are too weak

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

    Probably solution is available in the internet . they just find out from net after that certain point of contest

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

    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

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

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.

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

    i was getting runtime on 6

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

    What does NTT stand for?

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

    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).

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

      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

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

weak pretests on 1A/2C.

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

Is there a O(n) or O(nlogn) solution for C ?

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

    I solved using FFT in O(M*log(M)) time complexity. M = 2*2.5*1e6

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

    My solution was to solve for $$$n <= 2e4$$$ with an $$$O(n ^ 2 log n)$$$ algorithm

    And 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.

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

    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))

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

cheatforces!

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

My reaction while reading prolem 2A was similar to https://www.youtube.com/watch?v=KNviwfDeRKg

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

Solved Div 1A using FFT, missed a silly observation.. how stupid I am.. :/

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    How to solve it normally? I tried randomized approaches but none worked

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

      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)

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

        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?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it

          You stop when some sum is created twice. There are at most $$$5e6$$$ possible sums, so you do at most that much work.

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

        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.

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

      FST

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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

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

      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

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

      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 $$$<i, j>$$$ 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$$$.

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

        Can you give some content about the Dirichlet principle you're talking about? (Preferably YouTube)

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

        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?

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

        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.

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

Anyone noticed the weird constraint for the elements in Div2C?

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

    Why so much down votes in this comment? Did I say someting wrong?

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

And some interesting fact: you can pass Div2 C's pretest by just simple rand().

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

    What is the idea?

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

      link

      And it can pass system test. I got fst because I made a very very stupid mistake in brute-force part :(

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

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 :-)

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

How to slove TLE in problem 2 in div 2?

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

Will the system testing be done right now or an hour later?

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

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

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

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.

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

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

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

    There is a simple observation that makes it easy -- if you see it, you can get AC quickly

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

      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.

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

        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.net/contest/1500/submission/109893462 (no edge cases)

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

          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]

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

          This is much simpler and intuitive, thanks for sharing!

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

      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.

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

        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)

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

          Yes, I agree with this. Some people just implemented the n^2 algorithm without knowing why it worked.

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

        Cause C was available on gfg while a nd b not

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

          And dumb me didn't implemented it thinking that it would give me TLE.

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

          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.

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

            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.

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

              Yes, but how to prove it?

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

                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.

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

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm afraid of system testing

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    The sum of the two numbers must be less than 5e6, and you can find the answer at most 5e6 times.

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

    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.

    → Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it -37 Vote: I do not like it

The initial problem scores seems too small for me.:(QAQ

I solved 2 problems but my score is smaller than some people with 1 problem.

Let's admire the great score setter.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -16 Vote: I do not like it

    BTW, if the number of my incorrect submissions * 50 > the score according to the accepted time will I get less perf?

    :(

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

      You get at least 30% of initial score

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

I didn't like div2A, spent 15+ mins trying to understand the statement

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

    The same.

    I spent 13 mins on A, but only 11 mins on B.

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

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 answers

B: alright, not trivial, not too hard, obvious binsearch and some number theory behind

A: 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.

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

    I believe there's no real need for special cases, just take a looser bound — the special cases get accounted for fast.

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

      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.

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

        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.

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

My Div1C passed pretests even I typed n instead of m somewhere. It was so scary.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Dont we all agree that most of the C accepted submissions were from GeeksForGeeks!

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

Div1C can be solved with "bitset" in O(N^3/w)

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

Great problems, thanks!

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +115 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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)

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

    Think of brute force, and show that it'll work using the pigeonhole principle

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

      Brute force would be to calculate sum of all pairs. Which itself is n^2.

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

        n^2 is enough to pass time limits
        my submission https://codeforces.net/contest/1501/submission/109856495

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

          It is min(n^2,10^6). That's why, It pass time limits.

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

            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]

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

              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.

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

    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 complexity

    I 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...

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

TLE: https://codeforces.net/contest/1500/submission/109883422 AC: https://codeforces.net/contest/1500/submission/109892108

I resubmitted my TLE code during the contest and got an AC. Can anyone explain why? Can we rejudge? Sorry to disturb you.

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

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?

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

    Its called Miracle dood:)

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

    scanf becomes much slower, if stdio.h is not included as first header working with streams, which is your case.

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

    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.

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

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?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +9 Vote: I do not like it

    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.

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

It got TLE in contest DIV1 B https://codeforces.net/contest/1500/submission/109868976, but resubmitted got AC: https://codeforces.net/contest/1500/submission/109893896

Is this supposed to happens?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain me why O(n^2) is accepted for n<=200000 in DIV-1A (DIV-2C)?

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

    You will find a solution before than all operations.

    Worst case there are 2.5⋅106 + 2.5⋅106 possible values(a+b)

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

    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.

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

    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

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

AC:https://codeforces.net/contest/1500/submission/109898116 TLE:https://codeforces.net/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...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My clean 30 Line code to DIv2 C. only based on pigeonhole principle. 109899822

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

    My $$$O(n^2logn)$$$ solution using hash table don't know it but passed ^_^

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    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.

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

      NO Man tcs have 200000 values at max. see test cases in my submission.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

int128 -> long long

TLE -> AC

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 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.
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    :)

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

    Look at this submission :

    https://codeforces.net/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!!

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

Your solution 109863008 for the problem 1501C significantly coincides with solutions shaw_off/109861748, rUnTiMe_TeRRORrr/109863008. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked. Here is the code that was published before this Competition as it was published before this competiton Contest -707 Div 2 Problem C **link to the contest -[](https://codeforces.net/contest/1501)** link — code avaialble on net link to my submission — [](https://codeforces.net/contest/1501/submission/109863008) please look MikeMirzayanov

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

    I reverted all punishments if for a user the only matched code is in problem 1501C.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it -24 Vote: I do not like it

      but i think this contest should be unrated because many participants had the same submission on problem Div2c. Many newbie and pupil only solve only C. If the round is still rated , it is unfair to another participant who did with self-ability.

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

      This must be a joke.

      The whole problem, was to figure out that the brute force works. Now somebody provides a brute force solution, which works for distinct numbers — it was obvious that tons of them are available and you cancel all punishments based on that...

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

109903632 109904857

I want to know why making the one which uses vector get Memory limit exceeded!

I think it is totally unnessary!

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

    Not justifying the constraints of the problem or anything, but this is just one pitfall of std::vector. I agree that the problem didn't have a good memory limit anyway.

    Note that we say std::vector takes amortized $$$O(n)$$$ space. More precisely, when there are $$$n > 0$$$ elements, its internal capacity becomes $$$2^{\lceil \log_2 n \rceil}$$$, which in the worst case can be as large as $$$2n - 2$$$. This might have given the MLE verdict.

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

Problem 2C is pretty standard problem available on all coding tutorial websites including GFG.https://www.geeksforgeeks.org/find-four-elements-a-b-c-and-d-in-an-array-such-that-ab-cd/

@MikeMirzayanov

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

Codeforces is now filled with idiots. Whenever they perform bad on contests, they blame the problem statements and writers

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    agree but in this contest it did't balance to all participants because of the cheating on Div2C.

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

      what type of cheating? on telegrams?

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

      Tbh, it isn't cheating. According to codeforces rules, you can use any publicly available 3rd party code written before the contest. I guess they were just lucky

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

ASAS Isn't it?

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

I don't really think we should downvote this contest so heavily. It's true that many parts of the contest can be improved, but such downvoting is a disrespect to the authors and their contribution to the community.

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

    I do agree . They have done a lot of hardwork and downvoting so harshly is not fair .

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

    Even this contest wasn't bad.A,B were same as other rounds have.C have observation.And D was obvious binary search with some implementation.I don't know what people expect from cf.What people do is:if they performed bad,blame on authors.In todays contest atleast till Div2d didn't require any advance knowledge neither any advance math.

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

      Did you see the rest of div1 problems? I'm not sure that 2600 rating is normal for div1C. Or 2900 for div1D. Maybe I don't understand something, but these problems should be a bit easier.

      In fact, there were 2 more problems on the contest, that were as hard as div1F. IMO, the authors of the contest just overestimated the skill of the participants.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div2B can actually be directly simulated (of course compressing the sequences, e.g., 1 1 1 1 1 1 -> (6,1)). Since with compression on each iteration we insert only one element, no matter how many we have removed, and we remove only once, it is linear in N.

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

    when will the ratings get updated based on this contest ?

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

Not submitted DIV 2.C O(n^2) solution with the fear of getting TLE. Could not find during the contest that sum cannot exceed 5*10^6.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hard contest

→ Reply
»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Seriously

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me here why n^2 solution is passing?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it
    • The minimum pair sum is $$$1 + 1 = 2$$$
    • The maximum pair sum is $$$2.5 \times 10^6 + 2.5 \times 10^6 = 5 \times 10^6$$$
    • Total number of pairs when $$$n = 200000$$$ is $$$\frac{n \times (n - 1)}{2} = 19999900000$$$ which is roughly $$$10^{10}$$$
    • Now according to the pigeon hole principle after at most $$$5 \times 10^6$$$ unique sums it will hit again one of those unique sums and only then you can stop your nested loop and and print the result.
    • So half way through the $$$O(n^2)$$$ you definitely find the answer and you can terminate there so the $$$O(n^2)$$$ solution will need to run at most $$$5 \times 10^6 + 1$$$ iteration to find the answer.
    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      What about the differences:

      $$$x+y=z+w$$$
      $$$x-w=z-y$$$

      Note that for the differences we can switch the sign, so we can use the absolute value.

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

        Thats exactly the same problem. Just move w to the right and y to the left and you get x+y = z+w

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

          Yes, but the result of the subtraction is max half the size of the result of the addition. So the loop runs only half the time.

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

      "So half way through the O(n2) you definitely find the answer and you can terminate there so the O(n2) solution will need to run at most 5×106+1 iteration to find the answer."

      But what if we don't find an answer, then the loop will run O(n^2) times (right?), would that not be TLE?

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

        There is some possibility that we won't find answers for cases where n^2 < 2.5*10^6 but for cases of n^2 > 2.5*10^6 (we may need few more numbers because of some collisions in the chosen indices) we are bound to find an answer. I hope this clears your doubt :)

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

        It is guaranteed to have an answer when is $$$n$$$ is roughly $$$\ge 4000$$$ (Pigeon Hole Principle)

        Let me demonstrate that:

        We only have $$$7$$$ days a week sat through Fri.

        If I ask you to name the names of 8 days, at some point it is guaranteed to name some day twice or more.

        With that, let us go back to the problem, we only have $$$2$$$ through $$$5 \times 10^6$$$ possible pair sums (Holes), Now when you run your nested loop you are going to generate sums more than the number of holes that you have, and so you are gonna have pairs with repeating sums.

        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this round rated?

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

In Div2 C, I used an intuitive approach to solve that worked. Basically, I iterated over differences (ax — az) from 0 to k*C/N, where C = 2.5*10^6, N is the input size, and k is some constant (say 2) and then I checked whether four such indices exist or not. My question is how to prove that only checking first k*C/N differences works? Also, what is the tight lower bound for such k?

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

When will the rating be updated, if you don't mind me asking?

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

Is the round unrated now ?? I can't see any rating changes in my profile or any one else

Thank you in advance

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was this contest rated

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

    If anyone noticed,contest final standings had been continuously changing yesterday in a span of every 2 hours albeit by a small margin of 2-3 yet ratings hadn't been updated and no info about contest being unrated had been published by the contest setters.

    → Reply
»
4 years ago, # |
  Vote: I like it -68 Vote: I do not like it

As a contestant, I think that if you want to hold a contest on CF, you should provide the best problems and sincerity to contestants. A good round should have novel ideas, strong data, and amazing solutions, instead of old problems, cumbersome details, and bad pretests. As we all know, contestants would be sad if they solved a problem but got failed on system test instead of accepted because of small detail. Isn't it? :)

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

was this round unrated ??

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is this round unrated

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

Hope this round will not unrated.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

，

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my code is getting TLE? https://codeforces.net/contest/1501/submission/109937856

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

    TL I made a small modification to your code, it passes #73, but it failed #74. Now replacing unordered map with array passes the limit, AC. Second code is runner up's C code. What is the reason for this?

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

      I was thinking that it was getting TLE because my map was getting updated each time and for that it needs more iteraton but after seeing your modification I have realised that my thought was wrong. But I have seen many contestants did it in similar way but got no TLE. Didn't find any dissisimilarity. If anybody knows the reason behind this TLE please tell me.

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

        Do you mean, similar unordered-map type solutions passed?

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

          Yes. I have lost the code but I have found no dissimilarity between these two. Maybe there are very few dissimilarity. But didn't get it.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it

        I think why your code gives TLE(not sure) is the code just stores one instance of a pair, but in the editorial, it mentioned we have to store all four instances of pairs and if we get to such a position we can break, by printing appropriate indices, but the code is not intended to do that, that is the reason for TLE(the test case 73 and 74 are specially made for this purpose like it has first 535 elements which have unique sum for each i belonging to N) so basically we get to near $$$1.07*10^8$$$ operations. But, it is evident that vector passes, I suspect that it is due to cache friendliness nature of vector(not sure). Like, I may quote one instance, in the last topcoder SRM 801, div 2 hard question, map solution was supposed to pass with the given complexity, but it didn't whereas it vector counterpart passed(although it is faster by a $$$logn$$$ factor), Click I am not able to come up with any other reason for this behaviour. Please correct me if I am wrong.

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

Why the div2 of the contest is unrated? Or the rating changes haven't been figured out yet?

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

This round should be unrated...I found a guy who just copy pasted from geeksforgeeks and did a little bit modification and got AC ...he didn't even try to write his own code...you can see in his submission....function name and code ,even comment is exactly same as geeksforgeeks...

https://codeforces.net/problemset/submission/1501/109870879

https://www.geeksforgeeks.org/find-four-elements-a-b-c-and-d-in-an-array-such-that-ab-cd/

I found just one guy and don't know how many have done the same thing ...

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

    And I also know all cheaters have down voted me...they want to make this comment hidden..

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

      You are being downvoted because your comment is useless as everyone knows that problem setters gave this question by miatake whose sol is already available and everyone knows and even Mike has accepted amd this is not the 1st time that this happened on codeforces so just stop thi nuissance and focus on your practice.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        When everyone knows and even mike accepted this..then this round must be unrated...let's wait what happens.

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

          I said this is not 1st time this happened. Just because of 1 question it would be very unfair to declare this round as unrated. Also div1 ratings have been updated so round is rated. Stop crying like a child just because you didn't know that solution is available on net. If you would have known then you also would have done the samething

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it -8 Vote: I do not like it

            as we all knows many people have cheated in this round and many not...I am just asking..is it fair to give +ve delta to a cheater and negative delta to those who didn't cheat.Make this round rated...I have no problem but before that remove all these cheaters

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

              unrating the round is unfair to those people who fairly submitted solutions and ended up receiving positive delta.

              Consider everyone's pov not just cheaters and those who are getting -ve.

              :)

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

          I think it’s not a big mistake that there is a duplicate problem of Div2 C

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

    The question was not at all difficult. What made it tricky was that most of us didn't know that this question would get accepted even in n2logn time.

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

      U are wrong.They have added TC #73 to reject n2logn submissions.P.S. try submitting ur solution again

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

    there have not any rule that " you can not copy solution from internet.". so its not illegal bro. actually its the author mistake. :( i also affected like you sir.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope it will be rated :)

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why the ratings of Div2 doesn't change ?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

hey MikeMirzayanov sir , can u pls tell when will rating updated for contest-707 div2 its upto 18 hour from contest ends

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

I think they did not update ratings because, now for div2-C O(n^2logn) solutions are not working and giving tle on 73th testcase which were accepted before.

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

    So what is the correct approach now which will pass all the test cases?

    UPD:- So it seems n^2 solutions are working fine which means all the solutions copied from gfg will fail if systests happen again.

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

    But #73 was submitted at 2021-03-14 07:36:49,this cannot be the reason why the rating of div2 has not been updated with div1.

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

    Man O((n^2logn) are giving tle.My solution was min(n^2,5*1e6) is still passing all tests.P.s. ur solution is O(n^2logn)

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

    my brute force algo is working fine for C.Its also n^2

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

This is entirely my fault — it's even bolded! — but did anyone else miss the key condition "elements are distinct" for D2D/D1B? I only realised just now when reading a code that was identical to my own solution...

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

Ratings have been updated now.
Thank you !

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

congratulation to all cheater who copied code from the internet and get high rating change. congratulation congratulation !!!

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

    hahaha cheaters downvote me :)) you are trash and your skill never become better hahaha

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

      It is clearly stated all material published before contest is valid

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Many codes of Div 2 C which passed during the system tests are now giving TLE on test case 73 and 74, and still, they have got points. So isn't this unfair with the people who didn't submit that knowing that it will give TLE?

Eg: Submission C

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

.

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

I participated in Div.1 and I'm upsolving the Div.2 easy problems.

WTF is this shitty Div.2 A????

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please help me understand why O(n square) logic works for the Div2 C problem? The limits for n are (10 to power 5) so it should ideally give TLE for a N square logic according to me

problem link: https://codeforces.net/contest/1501/problem/C

Solution link: https://codeforces.net/contest/1501/submission/110046641

Thanks in advance

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

    $$$1 <= a_i <= 2.5*10^6$$$

    • What does this mean?

    This means there are at most $$$5*10^6$$$ possible sums.

    • So, if $$$n > sqrt( 5*10^6 )$$$ there is always a solution.

    • Stop when some sum is created twice.

    • Complexity $$$O(min(n^2,5*10^6))$$$

    My Submission

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody please tell me why my code:110064321 TLEs in Div.2D and any possible optimization I can do? Thanks.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The constraints are wrong on 1B. Says colors are greater than or equal to 1, but in the tests they can in fact be 0. Had fun debugging that -_-...

→ Reply