ch_egor's blog

By ch_egor, 5 months 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, 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:

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

Div. 2:

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

»
5 months 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(???

»
5 months 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! >_<

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

    sorry to make the second comment meaningless too:<

  • »
    »
    5 months 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.

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

      ?

    • »
      »
      »
      5 months 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 $$$

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Wish I can get perfect ranking and rating change.

  • »
    »
    5 months 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!

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Notice the unusual start time!

»
5 months 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

»
5 months 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! :)

»
5 months 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!

»
5 months 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.

»
5 months ago, # |
  Vote: I like it +89 Vote: I do not like it

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

  • »
    »
    5 months 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.

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

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

»
5 months 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!

  • »
    »
    5 months 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

  • »
    »
    5 months 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.

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

    Happy Indian Noises Intensifies

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Olympiad rounds are challenging and fun!

»
5 months ago, # |
  Vote: I like it -16 Vote: I do not like it

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

»
5 months 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.

»
5 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Notice the unusual start time :)

»
5 months 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.

»
5 months 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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hopefully it will be a great round.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

where are the "as a tester" comments!

»
5 months 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) !

»
5 months 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

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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?

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

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

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

      this is literally strictly against the rules

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think this is going to be a interesting Contest !!!

»
5 months ago, # |
  Vote: I like it +73 Vote: I do not like it

Um_nik's comment has been deleted!

  • »
    »
    5 months 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)

»
5 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Hope for strong pretests lol

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 months 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!

»
5 months 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.)

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Scoring distribution shows us that this contest will be HardForces

»
5 months ago, # |
  Vote: I like it -28 Vote: I do not like it

2.5 hours for 6 problems!!!It tells about the difficulty level of the "Problemset".

»
5 months ago, # |
  Vote: I like it -41 Vote: I do not like it

hope this time i will get positive delta

»
5 months ago, # |
  Vote: I like it -28 Vote: I do not like it

What a mindfuck contest.

»
5 months ago, # |
  Vote: I like it -26 Vote: I do not like it

Im outta here. Ratings go brrrrrrr

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

    and this is why you don't improve

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it -7 Vote: I do not like it

      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   Vote: I like it +209 Vote: I do not like it

      YEAH!

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

      Classic codeforces crowd. Sucking based on colours.

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +266 Vote: I do not like it

51jsms.

»
5 months ago, # |
  Vote: I like it +13 Vote: I do not like it

I liked the baiting in score distribution

»
5 months 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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Expecting Strong Pretest...

»
5 months 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)

»
5 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can tourist submit D on time? What you guys say

»
5 months ago, # |
  Vote: I like it +61 Vote: I do not like it

Div 2A was just disgusting.

»
5 months 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..."

»
5 months 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

»
5 months ago, # |
  Vote: I like it +223 Vote: I do not like it

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

    lol same

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

      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   Vote: I like it +11 Vote: I do not like it

     phew

  • »
    »
    5 months 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?

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

100% have cheating in this contest.

»
5 months 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.

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

    Then how did you solve it?

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

    Agree.

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Unbalanced difficulties but nice problemset. I enjoyed it.

»
5 months 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

  • »
    »
    5 months 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

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

    That's absolutely true. And reading A is just too time-consuming!

»
5 months 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.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Very brainstorming and skillful contest.

»
5 months 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

»
5 months 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 >_>

  • »
    »
    5 months 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.

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

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

  • »
    »
    5 months 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.

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

      Same here. It was an absolutely miserable experience.

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

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

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve Question C?

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

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

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Me after reading the D2A problem. Petr on Bad Problems

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Finally AC!!

submission

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

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

        wah bhaiya! i too have same thoughts and gonna follow this for sure.

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.

»
5 months 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.

»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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).

      • »
        »
        »
        »
        5 months 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. :(

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

»
5 months 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.

  • »
    »
    5 months 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...

  • »
    »
    5 months 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

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

    some couldn't even solve A but somehow solved C

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

    don't worry it's pretest are too weak

  • »
    »
    5 months 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

  • »
    »
    5 months 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

»
5 months 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.

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

    i was getting runtime on 6

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

    What does NTT stand for?

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

      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 exactly

      https://github.com/atcoder/ac-library/blob/master/document_en/convolution.md

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

        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, # ^ |
      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).

    • »
      »
      »
      5 months 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

»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

weak pretests on 1A/2C.

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

    This means my solution is going to fail sys test:(

»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 months 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

  • »
    »
    5 months 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.

  • »
    »
    5 months 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))

»
5 months ago, # |
  Vote: I like it +28 Vote: I do not like it

cheatforces!

»
5 months 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

»
5 months 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.. :/

  • »
    »
    5 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

    • »
      »
      »
      5 months 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)

      • »
        »
        »
        »
        5 months 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?

        • »
          »
          »
          »
          »
          5 months 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.

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

        Got AC with the same idea.

      • »
        »
        »
        »
        5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      FST

    • »
      »
      »
      5 months 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

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      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, # ^ |
        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

    • »
      »
      »
      5 months 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$$$.

      • »
        »
        »
        »
        5 months 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)

      • »
        »
        »
        »
        5 months 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?

      • »
        »
        »
        »
        5 months 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.

»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Anyone noticed the weird constraint for the elements in Div2C?

  • »
    »
    5 months 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?

»
5 months 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().

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

    What is the idea?

    • »
      »
      »
      5 months 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 :(

»
5 months 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 :-)

»
5 months ago, # |
  Vote: I like it -9 Vote: I do not like it

How to slove TLE in problem 2 in div 2?

»
5 months ago, # |
Rev. 3   Vote: I like it -163 Vote: I do not like it

It's a good game!

»
5 months ago, # |
  Vote: I like it +55 Vote: I do not like it

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

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

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

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

    I think disable comments for that time would help as this is where people wold discuss the problems.

»
5 months 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.

»
5 months 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

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.com/contest/1500/submission/109893462 (no edge cases)

        • »
          »
          »
          »
          »
          5 months 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]

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

          This is much simpler and intuitive, thanks for sharing!

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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)

        • »
          »
          »
          »
          »
          5 months 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.

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

        Cause C was available on gfg while a nd b not

        • »
          »
          »
          »
          »
          5 months 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.

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months 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.

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

              Yes, but how to prove it?

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

»
5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm afraid of system testing

»
5 months 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)

  • »
    »
    5 months 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.

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

      Had this idea 1 hour before ending, couldn't evolve it further :(

  • »
    »
    5 months 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.

»
5 months 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.

  • »
    »
    5 months 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?

    :(

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

      You get at least 30% of initial score

»
5 months 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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.

»
5 months 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.

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

    It somehow passed systests(and hacked by myself).

»
5 months 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!

»
5 months ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Great problems, thanks!

»
5 months 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.

»
5 months 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)

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

      • »
        »
        »
        »
        5 months 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.com/contest/1501/submission/109856495

        • »
          »
          »
          »
          »
          5 months 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.

          • »
            »
            »
            »
            »
            »
            5 months 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]

            • »
              »
              »
              »
              »
              »
              »
              5 months 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.

  • »
    »
    5 months 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...

»
5 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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, # |
  Vote: I like it +22 Vote: I do not like it

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

»
5 months 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?

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

    Its called Miracle dood:)

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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

Is this supposed to happens?

»
5 months 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)?

  • »
    »
    5 months 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)

  • »
    »
    5 months 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.

  • »
    »
    5 months 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

»
5 months ago, # |
  Vote: I like it +24 Vote: I do not like it

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, # |
  Vote: I like it -23 Vote: I do not like it

PROBLEM( B + A ) LINK : https://www.youtube.com/watch?v=MUnsGm0K8Qw

HAPPY CODING

»
5 months 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

  • »
    »
    5 months 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 ^_^

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

int128 -> long long

TLE -> AC

»
5 months 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.
  • »
    »
    5 months 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.

    :)

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

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

»
5 months 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.com/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.com/contest/1501)** link — code avaialble on net link to my submission — [](https://codeforces.com/contest/1501/submission/109863008) please look MikeMirzayanov

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

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

        And Div2c is available on internet

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

        I agree with u. I thinl who clicked downvote your comment was a cheater and they didn't admit their action. They are cowardice.

    • »
      »
      »
      5 months ago, # ^ |
      Rev. 2   Vote: I like it