tibinyte's blog

Codeforces Round #875 (Div. 1, Div. 2)
By tibinyte, 5 weeks 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, andrei_iorgulescu, 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

»
12 days ago, # |
← Rev. 2   Vote: I like it +32 Vote: I do not like it

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

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

    As a specialist tester, i specialist tested.

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

    yo teach me your ways

    → Reply
  • »
    »
    10 days 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!

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

    as a newbie, i wish i will become like you

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

As an average tester, I average tested.

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

    As an average setter, I average setted.

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

      As an average solver, I average solved.

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

      As an average setter, I haven't average setted.

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

        As an average setter, I haven't average setted

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

          as i walk through the valley of the shadow of death

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

            I take a look at my life and realize there's nothing left

            → Reply
          • »
            »
            »
            »
            »
            »
            12 days ago, # ^ |
              Vote: I like it -65 Vote: I do not like it

            eminemforces

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

              you all act like you never seen a white person before

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 days ago, # ^ |
                  Vote: I like it -13 Vote: I do not like it

                No racism here

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

                  things are getting a bit out of hands

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

          As non-setter, I haven't setted at all.

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

    As a non tester, I didn't test.

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

    As a specialist competitor, I'll compete specially.

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

As a bad tester,I tested like good tester.

→ Reply
»
12 days 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?

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

sus

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

As a setter, I didn't test.

→ Reply
»
12 days ago, # |
  Vote: I like it -98 Vote: I do not like it

Cringe! Just make regular announcements

→ Reply
»
12 days 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

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

Why so few authors? What happened to the rest?

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

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

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

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

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

Only 14 authors :D

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a pupil,IDK why I like to watch grand masters.

→ Reply
»
12 days ago, # |
  Vote: I like it -18 Vote: I do not like it

All problems are tricky but good!

→ Reply
»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG PEPE EMOJI!!

→ Reply
»
12 days 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.

→ Reply
  • »
    »
    12 days 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.

    → Reply
    • »
      »
      »
      12 days 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 ) .

      → Reply
      • »
        »
        »
        »
        12 days 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?

        → Reply
        • »
          »
          »
          »
          »
          12 days 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

          → Reply
          • »
            »
            »
            »
            »
            »
            12 days 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 days 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 days 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.

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

                man got 300+ downvotes from a single comment thread

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 days ago, # ^ |
                    Vote: I like it -40 Vote: I do not like it

                  ratings or downvotes, does it matter ?

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

                  to some extent, yes (30%) for me

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 days 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

                  → Reply
  • »
    »
    12 days 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:

    → Reply
    • »
      »
      »
      12 days 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 )

      → Reply
      • »
        »
        »
        »
        11 days 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?

        → Reply
        • »
          »
          »
          »
          »
          11 days ago, # ^ |
            Vote: I like it -74 Vote: I do not like it

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

          → Reply
  • »
    »
    11 days 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.

    → Reply
    • »
      »
      »
      11 days 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 ?

      → Reply
      • »
        »
        »
        »
        11 days 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?

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

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

    → Reply
»
12 days 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.

→ Reply
  • »
    »
    12 days 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.

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

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

      → Reply
    • »
      »
      »
      11 days 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 :)

      → Reply
    • »
      »
      »
      11 days 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

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

      Guess time to prioritise leetcode now

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

    Thy wish has come true

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

As grey. I hope be specialist next round uWu

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

As a <newbiw i wants to give the round

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant, I like participating.

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

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

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

omg grey round!

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

longest duration contest 2:30 hr.

→ Reply
  • »
    »
    11 days 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.

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

      Yes, but many 6 problems div2 contest lasts 2:15 hr.

      → Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please give me advise? how can I practice hard problems(like 1600+ rating) so that i can solve problem D,E within the contest time? I am trying to up solve but feeling so hard. What strategies can I follow? Thanks in advance.

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I completely ignored the fact that the blog writer has a -14 rating

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

    actually he got negative due to hacking. he was expert.

    → Reply
»
11 days ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

As a contestant, i am waiting...

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

What is "Scoring Distribution: TBD"?

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

tibinyte Orz

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good Luck for everyone

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

vuw

→ Reply
»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Sniff sniff, i smell AmOnGuS!!!

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

Is this Div2 rated for participants with rating < 2100 ?

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

    You can only participate in div 1

    → Reply
  • »
    »
    10 days 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

    → Reply
    • »
      »
      »
      10 days 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.

      → Reply
    • »
      »
      »
      10 days 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

      → Reply
      • »
        »
        »
        »
        10 days 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.

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

        whaaa.. What's your source for that?

        → Reply
        • »
          »
          »
          »
          »
          10 days 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.

          → Reply
          • »
            »
            »
            »
            »
            »
            10 days 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

            → Reply
»
11 days 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...

→ Reply
  • »
    »
    11 days 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

    → Reply
    • »
      »
      »
      11 days 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?

      → Reply
»
10 days 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.

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everybody!!!

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Anything is possible if you put your mind to it :D

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Timing clashing with Leetcode Contest :(

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Maybe I won't be allowed to wait until summer vacation, let's go tonight！

→ Reply
»
10 days ago, # |
← Rev. 2   Vote: I like it +54 Vote: I do not like it

who let a negative rated guy set problems 😡

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

Is this round is rated?

→ Reply
»
10 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone!

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

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

→ Reply
»
9 days 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

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

    set your priorities straight. Mike and the codeforces team isnt here to please everyone with their contest timings and the contest will not be rescheduled for such petty reasons

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

    Finally BCCI postponed IPL

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

    CF>> IPL, even god postponed the IPL Final to today so that we can enjoy both!

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

RescheduleForces!

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

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

→ Reply
»
9 days 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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck

→ Reply
»
9 days 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!

→ Reply
  • »
    »
    9 days ago, # ^ |
    ← Rev. 5   Vote: I like it +21 Vote: I do not like it
    Recommendation
    Good luck!
    → Reply
»
9 days 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

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

    why are you sad when your comparison has 4 >

    → Reply
    • »
      »
      »
      9 days 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

      → Reply
      • »
        »
        »
        »
        9 days 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

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

    Should have given it. Better than watching rain :)

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

    Lol it rained

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Best of luck to me :)

→ Reply
»
9 days 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.

→ Reply
»
9 days 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 :)

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

tourner dans le vide

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

Problem B is s*ck

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

FSTs loading...

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

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 2 contest exists Easy ass permutation problem be like: Did you miss me?

XD

→ Reply
»
9 days 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.

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

    just don't use hashmap lol

    → Reply
    • »
      »
      »
      9 days 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.

      → Reply
      • »
        »
        »
        »
        9 days 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.

        → Reply
  • »
    »
    9 days 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.

    → Reply
  • »
    »
    9 days 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.

    → Reply
  • »
    »
    9 days 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.

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

    Try a stronger hash function

    → Reply
  • »
    »
    9 days 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

    → Reply
»
9 days 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

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

How to solve B div1/ D div2?

→ Reply
»
9 days 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.

→ Reply
»
9 days 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

→ Reply
  • »
    »
    9 days 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).

    → Reply
  • »
    »
    9 days 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.

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me what is wrong with my code for div2C (sorry its java lol): https://codeforces.com/contest/1831/submission/207667860

→ Reply
»
9 days 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

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

how to solve D?

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

    idk

    → Reply
  • »
    »
    9 days 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.
    → Reply
    • »
      »
      »
      9 days 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

      → Reply
»
9 days 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.

→ Reply
  • »
    »
    9 days 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$$$

    → Reply
    • »
      »
      »
      9 days 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?

      → Reply
      • »
        »
        »
        »
        9 days 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.

        → Reply
  • »
    »
    9 days 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.

    → Reply
»
9 days 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.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What is second test case for D?

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

    → Reply
»
9 days 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.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As an average coder, I average code, but I'm not average here.

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

with the whole army of testers and setters the pretests are still this bad + stupid constraints.

→ Reply
»
9 days 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.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve div2 C?

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

Finally a good contest and not Speedforces. B was so time-consuming tho.

→ Reply
»
9 days 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 :(

→ Reply
  • »
    »
    9 days 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.

    → Reply
    • »
      »
      »
      8 days 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?

      → Reply
»
9 days 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

→ Reply
»
9 days 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.

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

    Congrats! What extension do you use?

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

    congrats

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

    Congratulations

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

    Congratulations! I also solved C at last to become GM for the first time.

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

in problem C , my idea was build a normal tree, and if there in a level at least one node that became upove the parent I increase (reading) by one . is this idea wrong ?

→ Reply
»
9 days 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?

→ Reply
  • »
    »
    9 days 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.

    → Reply
    • »
      »
      »
      9 days 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.

      → Reply
      • »
        »
        »
        »
        9 days 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.

        → Reply
  • »
    »
    6 days 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.

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

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

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

so angry with myself. I messed up on B and then was too late for everything else. I was allocating an array of the max size so I got always TLE without figuring out why for more than an hour...

→ Reply
»
9 days 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

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

    OMG

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

    What? How did this pass?

    → Reply
    • »
      »
      »
      9 days 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.

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

        Could you share any resource for the same?

        → Reply
        • »
          »
          »
          »
          »
          9 days 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.

          → Reply
  • »
    »
    9 days 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.

    → Reply
    • »
      »
      »
      8 days 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).

      → Reply
  • »
    »
    9 days 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?

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to approach D ? got stuck , but couldn't think anything in linear time

→ Reply
»
9 days 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.

→ Reply
  • »
    »
    9 days 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)

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

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

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

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

    → Reply
»
9 days 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.

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please guide for B div 2

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

    It's a little hard to explain, but my code should be ok to read. We are essentially finding the longest "streaks" of the same value from each array. Then taking the max of sums each one. (Say if there is a streak of length 2 with value 3 from A, and a streak of length 5, with value 3 from B, we just add 2 + 5, and take the max over all of these values values). Its (kinda?) easy to see that the longest streak in array "C" will be comprised of one subarray from A and one subarray from B.

    Proof that we can do this: We can greedily remove all values before the two subarrays. then merge the two subarrays together. (try to prove it to yourself through simulating it)

    https://codeforces.com/contest/1831/submission/207591101

    → Reply
  • »
    »
    9 days 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]); }

    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

GreatForces

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

C was fun.

→ Reply
»
9 days 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.

→ Reply
  • »
    »
    9 days 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

    → Reply
»
9 days 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.
→ Reply
  • »
    »
    9 days 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.

    → Reply
    • »
      »
      »
      9 days 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

      → Reply
      • »
        »
        »
        »
        9 days 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.

        → Reply
        • »
          »
          »
          »
          »
          9 days 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

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

    Yes, you simply needed to count the largest number of consecutive occurrences of each number in each array separately and take the maximum sum of those sums for each unique number.

    → Reply
»
9 days 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

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

    There should be some basic knowledge of tree to understand the problem statement properly. but this problem can be solved using DFS.

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

      i don't know dfs and bfs...seems like it's the time i should start focusing to learn something new

      → Reply
  • »
    »
    9 days 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$$$
    → Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

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

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

      I don't understand what you said

      → Reply
      • »
        »
        »
        »
        8 days 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

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

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

→ Reply
»
9 days 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.com/contest/1831/submission/207672990

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

→ Reply
  • »
    »
    8 days 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)

    → Reply
»
9 days 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.

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

Can't wait for rating update! :)

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

So happy to. Victory thank, you

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

Very good problems, well done guys!

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

    Thank you! Which one was your favourite?

    → Reply
    • »
      »
      »
      9 days 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).

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

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

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

Thanks for the round, finally blue!

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

D is a great problem with stupid Memory limit

→ Reply
  • »
    »
    9 days 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.

    → Reply
»
9 days 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!

→ Reply
»
9 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain me about problem 2 in div 2

→ Reply
  • »
    »
    9 days 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.

    → Reply
»
8 days 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，

→ Reply
»
8 days 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.

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

    Maybe its because you are passing the Vectors by value in the checkSum function. Try to pass it by reference

    → Reply
»
8 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Problems D seems like a typical atcoder ABC F

→ Reply
»
5 days 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!

→ Reply
  • »
    »
    5 days 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:
    → Reply
    • »
      »
      »
      5 days 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

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

I discovered a strange way to write the exact same code for this so that exact means exact, just the variables are changing, and not encounter plagiarism. below are two codes. https://codeforces.com/contest/1831/submission/207638804 https://codeforces.com/contest/1831/submission/207641923

There must be more identical codes like this; chances are they are high. I'm curious as to whether or not they cheated. Can anyone explain this to me?

→ Reply
»
4 days ago, # |
← Rev. 4   Vote: I like it +7 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.

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

in div 2 i solved 3 problem , may rank was good . Today i saw the massege bellow and my ratin deecrease 100.

Attention!

Your solution 207637749 for the problem 1831B significantly coincides with solutions ciel_/207626402, jubayer555/207637749. 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.

i really don't know what happend, how the user (ciel_ ) can copy my code ? is there any solution to get back my ratting?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

orz sir

→ Reply