tibinyte's blog

By tibinyte, 19 months ago, In English

Hello, Codeforces! Or, as we like to say in Romania: Sus Sus Sus, ca la Strehaia tată!

I am glad to finally invite you to participate in Codeforces Round 875 (Div. 1) and Codeforces Round 875 (Div. 2), which will start on May/28/2023 17:35 (Moscow time). In both divisions, you will be given 6 problems and 2 hours and 30 minutes to solve them.

The problems were authored and prepared by Andrei_ierdnA, Doru, Gheal, IacobTudor, LucaLucaM, RedstoneGamer22, SlavicG, Sochu, alecs, andrei_boaca, anpaio, lucaperju, valeriu and me ( tibinyte ).

I would like to thank:

  • irkstepanov for further help with logistics of organization.
  • freak93 for no morning refreshment.

Scoring Distribution

  • div 2: $$$500-750-1250-1750-2500-3000$$$

  • div 1: $$$500-1000-1750-2250-3000-3500$$$

The editorial has been published here!

And here are our winners!

# Div 1 Div 2
1 Ormlis kotrin
2 1a2b3c4 CLOCKS_PER_SEC
3 dorijanlendvaj IHatePaiu
4 tourist Lihwy
5 Radewoosh VietCek
  • Vote: I like it
  • +575
  • Vote: I do not like it

| Write comment?
»
18 months ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

As a non-newbie, I miss being newbie :(

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

    As a specialist tester, i specialist tested.

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

    This may be a way of speaking for the question group. They may be saying this in another way to wish us a better ranking!

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

    as a newbie, i wish i will become like you

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

As an average tester, I average tested.

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

As a bad tester,I tested like good tester.

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

didn’t Mike say you can’t put the wrong colors for usernames?

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

sus

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

As a setter, I didn't test.

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

I am a simple man: i see pepe the frog, i upvote the blog

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

Why so few authors? What happened to the rest?

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

    We were asked by the Codeforces admins to shorten the author list.

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

Wasn't everyone's name colored grey initially? What happened?

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

    Practice, hard work, and dedication.

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

Only 14 authors :D

»
18 months ago, # |
Rev. 2   Vote: I like it -180 Vote: I do not like it

Kind request to question setter. Please try to keep,

1) questions are balanced,

2) different topics ( rather than one single topic ),

3) cover largest input and longest run time test cases and yet keep one or two edges cases so contest could be fun with hacks.

4) give clear explanation for the example test cases.

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

    " keep one or two edges cases so contest could be fun with hacks "

    Its not fun for the guy who gets hacked.

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 3   Vote: I like it -210 Vote: I do not like it

      true. but it gives you the feeling like ICPC.

      You may think that you have solved problem, but it could fail final system testing.

      Also, when we have left very little time left and we cant solve/implement problems anymore, it is good to try to hack.

      UPDATE :

      There is some misunderstanding, I failed to clearly pointing out that hacking and ICPC aren't related. Personally I find weak pretests or excluding edge cases very enjoying. Also, if pretests are passing, then there should be some suspense whether final system test will pass or not ( like an ICPC ) .

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

        Feeling like ICPC? Who told you that there is system testing in ICPC?

        • »
          »
          »
          »
          »
          18 months ago, # ^ |
          Rev. 3   Vote: I like it -122 Vote: I do not like it

          adityagamer , I dont know if they changed it recently or not.

          But this is what I know about ICPC finals,

          https://youtu.be/kIbgLrquTx4?t=31411

          https://youtu.be/15Wyj_-PG9I?t=30869

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

            That's not hacking. The scoreboard is frozen near the end of an ICPC competition. Those clips show the scoreboard being unfrozen after the end of the contest. The yellow submissions are ones that were submitted in the last hour when the scoreboard was frozen.

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

              I didn't say its hacking. I said, some of the submissions could fail final system testing, if edge cases are not considered in pretests. adityagamer said, there is no system testing in ICPC, but I guess, there are few pending problems which are done tested after the contests.

              All I am saying is,,, there should be some suspense after the pretests, whether the final system testcases will pass or not.

              Of course there is no hacking in ICPC, I never said There is hacking ICPC.

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

                Please reread comment above and stop being annoying. If you're unable to see that there's no "system testing" in ICPC (it's clearly explained in Erekle's comment) then don't even start/continue conversation.

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

                man got 300+ downvotes from a single comment thread

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

                  ratings or downvotes, does it matter ?

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

                  to some extent, yes (30%) for me

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

                  great thinking, rating and contribution don't matter on codeforces. Contribution doesn't since it's ratist community and rating doesn't since you get nothing to show for it

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

    We've started working on the round over half a year ago and we most likely won't be making radical changes one day before the start of the round.

    I hope you enjoy the round regardless :thumbsup:

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

      Yes agreed. makes sense, not to change testcases-files or any other critical data.

      But, problem statements could be changed ( for better understanding, or test cases explanations could be changed )

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

        Are you implying that we made a conscious effort to make the statements hard to understand?

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

          !!!!!!! I have clearly stated that, ""for better understanding"" .

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

    Do you really think that you are giving something new for community with this comment? You are just saying obvious things.

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

      1) Do you really think that you are giving something new for community with this comment ?

      No, I am not giving SOMETHING NEW , but I am reminding something which is OLD AND GOLD, which recently most of the question setters have forgotten in past consecutive contests.

      If these things are obvious things, then why question setters are not doing what is so called OBVIOUS ?

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

        If these things are obvious things, then why question setters are not doing what is so called OBVIOUS ?

        You will understand it by yourself just when you will become a problemsetter. You advice is just "make a good contest, please". It is obvious.

        For example, the balance of a contest is subjective and thus cannot be measured by authors and coordinators. One need dozens of testers to make a balanced round.

        And also. Imagine you have a slightly unbalanced round. What will you do? Throw away one or two tasks and try to come up with another tasks?

        Your problem is that you think that coordinators or problem-setters are incompetent in some way. It's better to try to approach your questions in another way: why the rounds are like they are now? Which things I don't know and don't understand about problemsetting?

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

    All the best to heard-mentality-crew... have positive delta... xD

»
18 months ago, # |
Rev. 2   Vote: I like it -51 Vote: I do not like it

The contest clashes with the leetcode biweekly contest 105. Please do something about the timing :)

Update

As I can see my comment has initiated a spread of hate towards a certain platform in the thread, I would like to clarify that we live in a world of free will, thus anyone can opt to give either of the two contests according to their preference. I'd myself choose the codeforces contest due to the better quality of questions. My comment was only intended to make the round makers aware of a clash between the two contests and nothing else. Finally to everyone, who blindly downvoted my comment due to their specific hate for a platform just shows their herd mentality. Rest I hope for everyone to have a great performance in the contest.

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

    Get your prioties straight. This contest doesnt clash with leetcode biweekly, leetcode biweekly clashes with this.

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

      Exactly! Leetcode problems are easy. Codeforces is the real challenge

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

      I was just commenting to let them know. No need to get so worked up about it :)

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

      don't be rude, the guy just wanted to write both contests, and you told him to forget about it

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

    Thy wish has come true

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

As grey. I hope be specialist next round uWu

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

As a participant, I like participating.

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

leetcode biweekly + div2 both tomorrow. But everyone gonna choose div2...

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

omg grey round!

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

longest duration contest 2:30 hr.

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

    It's not the longest, there were several contests that lasted 3 hours.

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

Wow! A negative-rated author! Hopefully, enjoy this round (❁´◡`❁)

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

As a contestant, i am waiting...

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

What is "Scoring Distribution: TBD"?

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

vuw

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

Sniff sniff, i smell AmOnGuS!!!

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

Is this Div2 rated for participants with rating < 2100 ?

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

    You can only participate in div 1

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

    isn't div. 2 open for CM? It's neither a combined round

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

      Yes. A CM can participate in either div2 or 1 and have EDU round rated for them.

      Edit : But not in a div 2 within a separate div 1 — 2 round unless he registered when he was still expert.

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

      For rounds with separate Div 1 and Div 2, CM can only participate in the Div 1 round

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

        Are you sure about this? I usually see CMs profiles and have rated div2 in contests history even after being CM. Anyways, I registered for the div2 when I was still blue

        Edit : Upvoted. I think you're correct. I had a look over some random pages of the common registrants for the div2 and I rarely found a CM registered. The ones registered did so when they were yet expert.

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

        whaaa.. What's your source for that?

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

          Based on at least 100 or so rated rounds in the past two years, and also if you check the scoreboard for the Div 2 rounds that had an accompanying Div 1, there are no CMs. IIRC, Mike or other system managers manually removes CMs from the Div 2 registration or smth.

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

            thx for your reply. This seems highly confusing and inefficient. I bet it'd make waves but ffs make CMs div. 1 or div. 2 only

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

damn where scoring distribution? is it soo hard to publish it at least 1 day before the round? why almost nobody does that now...

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

    Don't know why, but I never care about scoring distribution O.o

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

      Same. Still, a bit strange to not see it one day before the contest. The authors have been preparing the contest for months, why couldn't they use a few minutes to write the points distribution?

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

Always welcome weekend rounds :) First rated contest for me in a long time.

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

good luck everybody!!!

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

Timing clashing with Leetcode Contest :(

»
18 months ago, # |
Rev. 2   Vote: I like it +54 Vote: I do not like it

who let a negative rated guy set problems 😡

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

Is this round is rated?

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

Good luck everyone!

»
18 months ago, # |
  Vote: I like it -11 Vote: I do not like it

I hoep everyone will get good marks in this contest. Good luck!

»
18 months ago, # |
  Vote: I like it -137 Vote: I do not like it

MikeMirzayanov please postpone this contest , today is IPL final , Probably dhoni would be playing for the last time today and everyone wants to see him. Please Postpone the contest Gheal

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

RescheduleForces!

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

(()def()r(es??again?

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

Please, if the round is postponed also this time, try to tell it earlier

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

I'm crossing my fingers and toes, hoping I don't plummet from my precious blue rank in today's game. It's a delicate balance, you see—I'm teetering at a hilariously precise 1601 points. Wish me luck!

  • »
    »
    18 months ago, # ^ |
    Rev. 5   Vote: I like it +21 Vote: I do not like it
    Recommendation
    Good luck!
»
18 months ago, # |
  Vote: I like it -45 Vote: I do not like it

CSK match >>>> CF contest :) feeling sad because not going to participate in this round

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

    why are you sad when your comparison has 4 >

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

      bruh now I am very very sad Na match dekh paya aur na contest de paya :( contribution -6 ho gaye wo alag

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

        same with me , but no problem tommorrow we would see the one and only legend msd lift the IPL trophy

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

    Lol it rained

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

I was registered for the contest when I was an expert. But I just noticed that I am a candidate master, but registered for div2. I think it would be better if the system would inform you about this.

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

Just as former world champion Magnus Carlsen won the recent chess tournament and came back again at the top, tourist(Gennady) should also try to get his first position back today :)

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

+76 is needed for CM. is it possible??

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

Problem B is s*ck

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

FSTs loading...

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

nice round,but i forgot something and got lot of wrong:(

»
18 months ago, # |
Rev. 2   Vote: I like it +63 Vote: I do not like it

Really dissapointed by B problem (Div. 1). There is 4 sec TL, and my $$$\mathcal{O}(n\sqrt{n})$$$ solution with hashmap doesn't pass. I tried to optimize it many times, using fast hashmaps, different pragmas and other methods.

Judging by standings I can conclude that I'm not the only one with this problem. But some people have achieved +5/+10/+20, others not.

TL 4 sec implies that $$$2 \cdot 10^5 \cdot 650 \cdot [hashmap time] = 1.3 \cdot 10^8 \cdot [hashmap time]$$$ will pass!

If author's solution has another complexity TL must be 1sec. If author's solution is just 2 times faster for example you can't ban people with $$$\mathcal{O}(n\sqrt{n})$$$ solution — this is not Codeforces politics.

So, AB were good tasks, C was interesting too, but I just waste all time to speed up B, it was terrible round.

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

    just don't use hashmap lol

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

      I have ML without it

      I need $$$[650][2 \cdot 10^5]$$$ array of $$$32$$$-bit integeres. This is $$$4$$$ byte $$$\cdot 650 \cdot 2 \cdot 10^5 = 520000000$$$ byte = $$$520$$$ MB.

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

        Since j < SQ in your solution, you can create an array int[SQ][n+1]. Just don't access the array if the second value is not in the range [1, n].

        Also you only need to clear n elements between test cases. Here's my submission: 207611902.

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

    I spent around 1 hour switching between unordered map, gp_hash_table and cc_hash_table and trying various optimizations to remove TLE and MLE :/.

    In the last 5 mins, I replaced it with a binary search on a vector containing deduplicated pairs, and their count and got pretests passed, though I still expect TLE during systests.

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

    Sometimes it is faster to just use regular (tree) map and check whether the element exists in the map before accessing (avoids unnecessary insertions). Not sure if this was intended though.

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

    Is it still possible to increase the time limit and rejudge submissions at this point? I'm another affected participant who tried messing with unordered_map and stuff which didn't work, while some solutions that just used binary search instead of map (207592515, for example), which should have the exact same complexity, passed.

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

    Try a stronger hash function

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

    lowerbound in vector works faster than hashmap in this kind of problems, from my experience

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

Decided to optimize D at the last second(after 1hr of being indecisive XD), it changed runtime from 3700 ms -> 1700 ms. But idk if it's actually just weak tests. Try hacking it 207664263. This problem would probably have many TLEs.

UPD: Turns out the initial 3.7s solution TLEd, but this one still passes in 1.7s

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

How to solve B div1/ D div2?

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

For the problem C do we have to use DFS? If anyone have use DFS to solve please can you share submission link.

»
18 months ago, # |
Rev. 3   Vote: I like it +26 Vote: I do not like it

div1 B too easy to come up with a solution but constraints too bad, it spoiled the contest for many people. Almost solved d1C, i think, could smb please write the solution? wanna check if mine is correct

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

    I am not sure about B constraints, I wrote the first thing which came to my mind and it passed in 2.1s. It's not optimal, surely it can be easily optimized to 1.5s and probably to <1s with some effort. But tbh I am not completely sure it will pass systests, I did not prove complexity. Upd: passed systests in 2.1s

    Regarding C, I did not solve it but I think one of the important insights is that any 2 intersecting (but not nested) segments [A;B] and [C;D] can be replaced with 3 non-intersecting segments [A;C) [C;B] and (B;D]. Then we can somehow remove all intersecting segments and solve a much easier subtask where segments can be only nested (build a tree from them).

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

    Yea I'm kinda bummed out because for d2D/d1B I had a java solution early on that got TLE, and I tried a lot of things but just couldn't get it under the TL. Then I converted the same code into c++ (which I barely know) and it passed, but by then I already wasted 1+ hours.

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

Great Contest! If you are stuck on Problem A, Problem B, Problem C (Div2) then this editorial might be helpful: link

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

how to solve D?

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

    idk

  • »
    »
    18 months ago, # ^ |
    Rev. 7   Vote: I like it +17 Vote: I do not like it

    you need to use the fact that the values of a[i] and b[i] are less than "N".

    So, for each pair (a[i],b[i]), we have to traverse till sqrt(N) at max, and see if the reverse pair exists or not.

    first of all, shard the pairs(a[i],b[i]) based on the first value (a[i]). Also sort each shard for applying faster search operation using binary_search.

    We also need to keep track that how many times particular pair has been encountered in past, to do so we need a map < pair <int, int > , int > where map[(x,y)] denotes, how many times particular pair (x,y) has been encountered yet.

    for(int i = 0 ; i < n ; i++) {
       shard[a[i]].push_back(b[i])
    }
    for(int i = 1 ; i <= n ; i++) { // sort each shards
       sort(shard[i].begin(),shard[i].end())
    }
    // suppose shard pairs are (1,2),(1,3),(2,3),(2,1),(4,8),(4,12),(4,4)
    // shard[1] = { 2 , 3 }
    // shard[2] = { 1 , 3 }
    // shard[3] = { empty , because no pair has a[i] == 3 }
    // shard [4] = { 4 , 8 , 12 }
    // Hope part 1 is clear...
    

    Core logic part is here now, suppose (a[i] , b[i]) and (a[j] , b[j]) are expected pair, then we will a[i] * a[j] - b[i] = b[j] , for better understanding I will use (x,y) and (p,q) instead of (a[i],b[i]) and (a[j],b[j]) from now on. so, (x*p — y == q) must hold in order to count the pairs.

    if shard[x] has value 'y' in it, that means, we have a pair (x , y) somewhere. Now, any pair (x , y) and (p, q) to be in the answer, we must make sure that x * p <= 2*n, otherwise answer is never possible ( because of the restriction that 1 <= y <= n && 1 <= q <= n,,, their sum will be 2 <= y + q <= 2*n. ) , that's why x * p must be less than 2 * n ;

    So, now using above facts, please go through code,


    for(int i = 1 ; i <= n ; i++) { for(int j = 0 ; j < shard[i].size(); j++) { int x = i; int y = shard[i][j]; // now assume that p is 1,2,3... until p * x <= 2 * n; for(int k = 1 ; k <= n ; k++) { if( x * p > 2 * n ) break; // here answer is never possible, // Now, try to find in shard[k], whether the value x*p - y is available or not // to do so, we can use binary_search, or set, or lower_bound() or anything auto it = lower_bound(shard[k].begin(),shard[k].end(),x*p-y); if(it != shard[k].end() && *it == x*p-y) { // Condition to see if the x*p-y is present or not // if the current value is present, then we have to add it number of times it has been encountered till now, ans += map[(x,y)] } } // once we have processed a pair (x,y), // we also have to add it to our map of encountered pairs map[(x,y)]++; } } // finally return ans, dont forget to initialise it with 0 by the time declaring it. :) . } Final complexity is O (N log N) + O(N * sqrt(N) * log N) in my case of implementation. With unordered maps and more further optimisations u could reduce log N factor to O(1) in the second part. but that's unnecessary to get AC.
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Wow, thanks a lot, pretty cool solution. I was close to it during the round, but wasn't able to write exact solution

»
18 months ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Edit: Oops, forgot checking by [] creates the element if it isn't already present. These unnecesary inserts and increase in query time due to map size probably leads to a 2-3x increase in running time leading to TLE.

Does gp_hash_table really use $$$\gt 500MB$$$ to store $$$2 \times 10^5$$$ elements????

gp_hash_table to store pairs (207666127) -> MLE

binary search on vector of deduplicated pairs (207666127) -> AC with 10KB memory usage

Also is there a faster than $$$O(n \sqrt n \log(n))$$$ solution to Div2D / Div1B? I spent like 1 hour optimizing it to remove TLE and then MLE T_T.

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

    $$$b_i\le n$$$, so you only need to maintain a bucket with size $$$n$$$

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

      Oh so since $$$a_i \leq \sqrt{2n}$$$, you just maintain a $$$\sqrt{2n} \times n$$$ vector for counts which fits in around 500MB of memory?

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

        no, you enumerate the a_i which is $$$\le \sqrt{2n}$$$ (assume that is $$$v$$$), and you only need to maintain a bucket with size $$$O(n)$$$ (which is also $$$O(n)$$$ in memory) to calculate the occurrence of $$$va_i-b_i$$$. After that, you clear the bucket.

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

    Every time you search in a map / unordered_map, if value you are searching for is not present, it always creates new element for it. So it is $$$O(n\sqrt{n})$$$ memory if you use them.

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

I do think there's no need to set the memory limit to 256MB instead of 1024MB. It is trivial to optimize the memory of knapsack on tree to $$$O(n)$$$ my storing the dp values into the return value of dfs.

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

What is second test case for D?

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

Is it possible to solve F by SMAWK + persistent segment tree?

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

    I see, maybe it needs to be some online version of it?

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

Confusing Round. C is a good problem.But B is just a Trash.

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

Had the new idea in the last 15 minutes. My heart can't handle this.

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

How to solve div2 C?

»
18 months ago, # |
Rev. 2   Vote: I like it +12 Vote: I do not like it

Judging by the number of people upset over Div2 D(Div1 B), I doubt the editorial would be satisfying(though I expect to learn something different/new). Still would love to know any approach that worked for you guys. Was stuck on this problem for 2 hours :(

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

    My approach was to split everything into buckets by A. Then we need to iterate through small buckets (A <= sqrt(MAX*2)) in an outer loop because otherwise, a*a will be too large and iterate through all buckets in an inner loop.

    At each iteration, calculate the answer for pair of buckets. To do it efficiently, sort elements in buckets, and use the smaller (by the number of elements) bucket as a needle and the larger as a haystack, do a binary search to find the number of matching elements.

    Also, we need to match every A <= sqrt(MAX*2) bucket with itself but it is fast so can be done in a variety of ways.

    I think my submission 207627709 is pretty clear but I am not sure if it was the supposed solution. Passed in 2.1s, probably could be optimized to 1s.

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

      I thought about the exact same optimization during the contest but wasted too much time trying to prove its worst-case time complexity. Here is my submission 207739872 after the contest. I still haven't figured the time complexity part yet. Do you (or someone else) have any insights?

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

Don't know why but I thought that there will be edge from u to v and not from v to u and treated the graph like a directed graph which resulted in a bad contest

»
18 months ago, # |
Rev. 4   Vote: I like it +63 Vote: I do not like it

This is the moment that I am very nervous about system testing. I solved problem div1 C in the last minute. If any of the div1 B and C passed, I will reach master! Please, don't FST, don't FST, don't FST.

ranking

UPD: I passed B, and I will reach master.

UPD again: Yes !! I passed C. In my estimation, problem 1C problem have a difficulty of at least 2300, and this problem will be the highest rating problem I have ever solved in contest.

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

Seems that many people passed pretests on D with 500MB of memory (me included). Could it have been a good idea to increase the memory limit to 1024MB instead?

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

    That might've been an unintended solution, in which case the memory limit should've been 256 MB. I also passed Div.1 B with 506 MB, just hoping for no FST (although it seems very likely)

    UPD: Luckily I didn't FST. Although I believe that the solution might be hackable.

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

      Well, the editorial solution seems to use the same idea as mine, maintaining a large 640x200000 array. I don't know much about memory but it should probably use a similar amount, unless arrays use up significantly less memory than vectors.

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

        Afaik, arrays don't use (significantly) less memory. I realize now that my comment doesn't really make sense — I didn't notice that the editorial was already published.

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

    It's possible to only use O(N) memory, so I think 500MB memory is already very generous.

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

for me , problems C<A<<<<<<<<B

»
18 months ago, # |
Rev. 2   Vote: I like it +99 Vote: I do not like it

Yeah, solved 1830B - The BOSS Can Count Pairs in $$$O(n^2)$$$. Solution

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

    OMG

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

    What? How did this pass?

    • »
      »
      »
      18 months ago, # ^ |
      Rev. 4   Vote: I like it +44 Vote: I do not like it

      This solution has been optimized by GCC after applying auto-vectorization for type float in a for-loop (FMA instruction set), in other words the for-loop has been parallelized on low level by processing $$$8$$$ floats per one iteration (SIMD — Single-Instruction-Multiple-Data), because iterations of for-loop are independent.

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

        Could you share any resource for the same?

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

          _aka5h, Elagamy, I read two articles: «A Guide To Vectorization With Intel C++ Compilers» and «GCC Autovectorization — A journey throught compiler options, SIMD», then experimented on old codeforces problems (most of them has limitation $$$n=100000$$$ or $$$n=200000$$$ and you can try to solve it). Also I used godbolt.org to see assembly. Maybe I read some other blogs from first pages from google, but I don't remember it.

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

    I think you should become a tester.
    To make sure that unintentional time complexity doesn't pass.

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

      The dilemma is a tighter time limit might've made the constraints so restrictive that even a fairly well written solution with the right time complexity would receive TLE verdict (especially in a language like Python or Java).

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

    wow it's a great optimization,How to learn the performance of interacting between CPU and memory ?

    I've learned about instruction set like this, but i want to know how to benefit from this knowledge in the coding paradigms?

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

For problem D, I am having difficulty thinking of a solution with less than O(n^2) time complexity. How should I approach this? For the entire duration, I was thinking of leveraging the fact that the sum of two elements can be at most 2*n and was not able to think of anything else. So far, I have only seen people using fancy data structures which I have never heard of.

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

    Try to think about pairs with ai <= sqrt(2 * n) and pairs with ai > sqrt(2 * n)

    In the first case you can iterate over all j

    In the second case you can iterate over all sums cause 2 * n / ai < sqrt(2 * n)

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

    See my solution using only binary search(as a fancy thing).

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

    Check Jiangly's O(n*sqrt(n)) solution

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

Might cross 1700 today for the first time in my CF journey 💙. I'm lucky that the contest was rescheduled because my internet connection was terrible yesterday.

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

please guide for B div 2

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

    suppose a[] = [_ _ _ _ x x x x _ __ _ _ ] b[] = [_ _ x x x _ _ _ ]

    You need max length subarray of equal elements

    for this you need a subarray from (array a) and a subarray of same element from (array b) and concatination of both will contribute to ans

    at last ans will be max of both subarray length

    fr(i , n) { lli val = v[i]; lli cm = 1; lli j = i + 1; while(j < n and v[j] == val) { cm++; j++; } i = j — 1;

    temp1[val] = max(cm , temp1[val]);       
    }

    // storing subarray of equal element size in temp array at particular index of that element

    // same for both array a and b at last finding max of both size

    lli ans = -1; fr( i , n + n + 1) { ans = max(ans , temp1[i] + temp2[i]); }

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

GreatForces

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

C was fun.

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

How to approach problem 1831C - Copil Copac Draws Trees ?. Got TLE while solving using Queue 207622849. Couldn't figure out why it is getting TLE.

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

    You should set vis[i]->true while you push the node into the queue

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

for today B problem i am understanding something wrong

  1. 1 1 1 1 3 2 2 2 2 — -
  2. 2 2 2 2 3 1 1 1 1-- for this i have checked output of users you have system test passed as ans 8 but which merging will lead to 8 as a answer. I am not getting. Maybe i am understanding something wrong.
  • »
    »
    18 months ago, # ^ |
    Rev. 2   Vote: I like it +4 Vote: I do not like it

    We can merge like this:

    1. 1 1 1 1 3 2 2 2 2
    2.                   2 2 2 2 3 1 1 1
    

    There is a segment of eight 2's in the middle.

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

      what if this
      - 3 1 1 1 1 3 2 2 2 2 3
      - 3 2 2 2 2 3 1 1 1 1 3
      what should be the answer.? according to me 4 i am not seeing largest subarray of equal elements

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

        We can get 8:

        1. 3 1 1 1 1 3   2 2 2 2         3
        2.             3         2 2 2 2   3 1 1 1 1 3
        

        Again, there is a segment of eight 2's in the middle.

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

          thanks a lot . got it .
          I cannot see that we can combine every segment of a array with b array. sorry if my doubt seems silly to you

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

Does the third question of div2 requires some knowledge of tree or it can be solved normally wihtout trees,as soon as i saw tree in the problem statement i left

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

    Things you should know about tree to solve Div2C:

    • tree contains $$$n-1$$$ edges, where $$$n$$$ is the number of vertices
    • tree is connected graph without cycles
    • there exists exactly one path from some vertex $$$v$$$ to some vertex $$$u$$$
»
18 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Missed the contest but my ratting saved from going down :p

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

    сколько стоил АК

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

      I don't understand what you said

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

        "How much does an AK cost?" Maybe some Russian movie dialogue about AK 47 smth

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

Great Contest, learnt something new in BFS 1831C - Copil Copac Draws Trees

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

Problem C — BFS-like solution:

I keep 3 sets: written, processed and current_edges.

written: Nodes that are written at the moment, but not fully processed

processed: Nodes that are fully processed.

current_edges: edges that are going to be processed.

Also, per each node, I keep a set of edge pointers.

  • At the beginning of the solution, add 1 to written set.

  • While there are nodes to be processed, keep processing (processed.size() < n)

  • For each node in written set, get all the edges where this node is part of, and insert them into current_edges set.
  • For each edge in current_edges set, get both nodes (one of them is alredy processed at this point, but I was too lazy to do the additional if statement), and insert to current_edges set all the edges that are greater than cure. Then, delete all these edges from it's edges index. If the set is empty, then insert it to processed set, otherwise, it should be processed fully so insert it into written set instead.

Solution link: https://codeforces.me/contest/1831/submission/207672990

It's a pitty I didn't got AC in the contest. I had a bug with lower_bound(...).

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

    I had a similar solution, I maintained an adjacency list so didn't need to use lower bound(because if once a node is inserted into current_edges it is either going to be processes fully in this iteration itself or the next iteration)

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

Did I miss some O(n) solution for D div 2 / B div 1? I tried square root decomposition, but I either get TLE or MLE. If I save the pairs as map<ii, int> I get TLE (which is understandable, as it is O(nlog(n)sqrt(n)). If I save them as unordered_map<i64, int> (using some hashing of course) I get MLE.

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

Can't wait for rating update! :)

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

So happy to. Victory thank, you

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

Very good problems, well done guys!

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

    Thank you! Which one was your favourite?

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

      In div1E it was very fun to figure out the precise invariant for operations, very cool and novel (at least to me). Definitely a highlight.

      Div1D is nice, div1C is good, and div1F looks interesting too (I'll try to solve it later).

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

        I wish I could, but can't try... way out of league

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

Thanks for the round, finally blue!

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

D is a great problem with stupid Memory limit

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

    I might be paranoic but I thought 1024MB is just a big spoiler. For me reading 1024MB in that problem just means "do some nsqrt memory dp".

    Setting $$$n \le 10^5$$$ to reduce memory also seemed to spoil a little, what setter does $$$n \le 10^5$$$ if not for $$$O(n \cdot \sqrt{n})$$$ or $$$O(n \cdot log^2)$$$ solutions? There was also a scam that worked quite well with this limit.

    I get we could set 1024MB limit to all problems, but I was unsure we wouldn't run into technical issues then.

    And the hld to reduce memory was posted not long ago so I thought most people knew about it...

    Nevertheless, I'm happy you enjoyed the idea of the problem.

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

This is one of the best rounds I've taken in a while, Tho Mle for Div2 D could've been less strict, Thanks!

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

can anyone explain me about problem 2 in div 2

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

    You are given 2 arrays a and b of length n. You have to merge these two arrays into c of length 2*n such that c has maximum length sub-array of equal element.

    Suppose a={1,2,2,3} and b={2,2,1,1}. We can merge it like, c={1,2,2,2,2,3,1,1}.here c[2,4](1 indexed)sub-array contains equal element. So answer is 4. Note that, We can also merge it in different way. Just keep mind that the Order of elements of array a and b will not change.

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

Div2 b Taught me not to use arrays when you can use vectors,

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

Would someone be able to check why my solution to Div 2 D TLEs on case 8?

It's basically the same as the official solution and runs in O(n*sqrt(n)), so I'm unsure why it TLEs.

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

Would someone fix my code, i don't know why it's wrong on test 4. thanks for help!

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

    It's because you use rand(). Use another number generator with a random seed and it will pass.

    Exactly your code but with these changes passes:
    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank you, but can u explain why using rand() is wrong, because i used srand(time(NULL)) in the beginning of my code

»
18 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

This comment is in context to the plagiarism applied to my code for the contest 875 div2 , for the problem C , with Numinous , on the submissions 207612824 and 207614629 , on going through the codes one can easily see how different they are one uses a dfs based approach while the other uses a bfs , I don't understand why are the codes plagiarised the only similarity I found was the template on top of the solve functions , to any one checking for plagiarism if he goes once through my submissions before the contest I have been using that template for more than 6 months and hence I have sufficient proof of my innocence and the false cheating charges levied on me should be taken back . MikeMirzayanov errorgorn irkstepanov freak93 tibinyte . Please just look into the solutions and you will know that these solutions are not at all same . MikeMirzayanov I hope you give me a fair trial . Thank You.