Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

By pikmike, history, 2 months ago, translation, In English,

Hello Codeforces!

On Apr/26/2020 17:35 (Moscow time) Educational Codeforces Round 86 (Rated for Div. 2) will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Ne0n25 Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Special thanks to Mikhail darnley Dvorkin for helping in round preparation!

Good luck to all the participants!

Our friends at Harbour.Space also have a message for you:

Codeforces and Harbour.Space

Hi Codeforces!

You really went for it in the last Educational Round! We had an all-time high participation of 21750 people :) We are happy to support such an awesome community, and look forward to growing these numbers in the future!

We are searching for diamonds in the rough — driven, talented humans, passionate about technology and design, undefined by nationality, gender and cultural background. We know that no diamond is born polished, so our mission is to identify and support as many talented young individuals as we can, so that they can fulfill their potential and secure the future they deserve.

If you are graduating or have already completed a bachelor's degree, we are waiting for your applications for fully-funded Master's degree scholarships by the link below.

APPLY NOW→

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 DreamLolita 6 211
2 KrK 6 235
3 Heltion 6 259
4 krijgertje 6 268
5 Temotoloraia 6 272

Congratulations to the best hackers:

Rank Competitor Hack Count
1 liouzhou_101 81:-35
2 j_peters 29:-16
3 eR6 18:-19
4 tonyli00000 14:-15
5 lollihunter 8:-7
281 successful hacks and 925 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A Sevlll 0:00
B This0is0the0AmShZ 0:02
C DreamLolita 0:03
D xb0nS 0:14
E P.Alizadeh 0:17
F chemthan 1:07

UPD: Editorial is out

 
 
 
 
  • Vote: I like it
  • +336
  • Vote: I do not like it

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

Kudos. " You really went for it in the last Educational Round! We had an all-time high participation of 21750 people "

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

Lets cross 25000 this time!

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

    Oh no. Think about CF servers.

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

      On last div3 server works fine with 28k registration. So 25k is going to be regular participation.

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

        I hope so.

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

        But this is ‘rated for div.2’ so there will be less participants. Educational Codeforces Round 85 (Rated for Div. 2) has only 21750 people.

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

        Div 3 isn't rated for many people. The no. of people who actually stay throughout the contest is very less. That might be the reason why 28k wasn't a problem.

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

          Div3 has more official participants than educational round. On last div3 round rating changes for 16k people where rating changes for 11k people on last educational round.

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

Can someone please explain what's a difference between codeforces educational and normal rounds? Thank you.

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

    You can find following difference

    1. Normal codeforces round has a variable points for each problem(500,750,1000 and so on). Each problem has equal points on educational rounds.

    2. In normal coforces rounds you can hack during the contest, in educational round there is 12 hours hacking phase after contest is finished.

    3. Normal codeforces round has 20 penalty for wrong submission where educational round has 10 minutes penalty.

    4. During contest successful submission gives verdict pretest passed where educational rounds gives accepted.

    5. Normal codeforces round judges your last pretest passed solution for each problems and skip other solution for that problem. In educational rounds all your solution will be judged and 1st one will be counted which passes the system test.

    6. In normal round final standing is given based on points earn from all solved problem. In educational round standing is given based on no of solved problem. If no of solved problem is equal then time penalty is used to break a tie.

    NB: Div3 rounds follow the rules of educational rounds.

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

      Thank you, sounds like these rounds are not too harsh and beginner friendly.

      One other thing, How do you hack during a contest or after its over? After some research I found out it gives you points after successful hacks. What I don't found out how you do it?

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

        In normal codeforces round you have to lock you problem first. When you lock your problem you can't resubmit that problem during contest time. After you lock your problem go to room tab and here you can see solutions of other participants who are in that room. You can hack or see solutions for those problem which you have locked.

        Successful hacking gives +100 and unsuccessful attempts give -50.

        In educational and div3 rounds you can see any solution you want. Then you can hack one from status page if you think that solution is not fine enough. This hack has no points.

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

      Are there points for hacks in educational rounds?

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

      In normal round you got -50 penalty if you passed the problem from pretests

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

      As far as I remember educational rounds also have system tests after them, after hacking phase. So #4 is only about name of verdict, isn't it?

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

        Yes it is only name of verdict.

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

          Really? Or the main system tests are just the added hacked test-cases?

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

            As far i know this also happen in codeforces rounds too.

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

              Are all the successful hacks included in the system tests?

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

      Why does the educational round give accepted instead of pretest passed?

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

      Normal codeforces round has 50 penalty for wrong submission afaik.

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

      In normal codeforces round,

      1st solution passed pretests time — 3 minutes into the contest — score 496/500

      same problem

      2nd solutionpassed pretests — time — 10 minutes into the contest — score ?

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

      I have a doubt. If the round is rated for only people less than 2100 rating, why is the rank calculated considering all ratings. And also, is there the case with rating change as well ??

      Just a doubt ...

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

        Contestants with rating >=2100 are one final standing but rating doesn't change for them. Rating only change for them who have rating less than 2100.

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

          yes, but if they are in the ranklist that means the ones who are below them will suffer rating loss and high ranks..is it the way educational round rating system works ?

          Its a doubt !!

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

            They will be not considered while calculating rating. Only rank of official participants will be considered.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thank..so many doubt are now clear..one last question ...is there time for hacking phase after the normal contest like div 1,2??

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

    You can read about educational rounds here

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

Good Luck everyone

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

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

    But we should hope for short and simple problem statements.

    What else we need
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      we do but let's hope that in our hearts I don't think writing hope comments will actually affect the problem statements or how strong pretests are ... just an opinion maybe someone else has a different point of view

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

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

every time

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

just a legendary noobmaster passing by...

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

Pretests have been extremely shit recently. Like seriously does it hurt to make good pretests and spare us from misery?

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

Why the educational round harder than normal div 2 round is it a lie or not

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

    _ (Reference — Evro)_

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

      Damn ,Stealing memes even in codeforces..

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

        My intention was not to steal your content(Evro), I simply found it funny and quite relevant to Codeforces while surfing google. So, I simply posted it to make people relate and smile a little. Now, That I know you made it, I tagged you.

        Peace

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

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

Educational rounds have never let me down.I hope everyone can enjoy this.Good luck and high rating!See you in the top list!

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

    You had to edit your comment thrice to say this?

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

      thrice !! English Language experts prefer to say 'once' and 'twice' instead of 'one time' and 'two times;' but the –ice suffix ends there, –'three times' is standard expression in today's world and not 'thrice. ... To answer the question (title) of this post, 'Yes, 'thrice' is a correct English word; and yes, it is dated! i copy this from google :)

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

        not sure what you mean by "english language experts", but I definitely remember hearing thrice being used so it can't be that archaic

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

          Bro i just search thrice on the google becuase ive never hear that before

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

[removed]

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

What people think simultaneously means??

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

I'm sorry but this round is one of some rounds that mostly made me be confused by its statements :|

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

simultaneously really ? :( @pikmike MikeMirzayanov

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

    Till the last 10 minutes, I thought both of them have to end up at 0 together in a single step and then I see in the contest announcement that x=1 and y=0 become x=0 and y=0." simultaneously" didn't let me solve any further questions.

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

      Even after seeing the announcement, I thought it could have gone from 1, 0 -> 1, 1 -> 0, 0 since x & y have to reach 0 simultaneously!!

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

    I feel for you, this took my 40 mins ... RIP Rating

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

      Same here :( I didn't feel like solving any more questions after I wasted time on 'simultaneuosly'

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

    This round should be unrated IMO because of the ambiguity of questions

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

    And 01 has period of 2 :| Omg :(

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

that C killed me

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

I'm really confused that when I choose not to see unoffical participants I see load of yellow and red names in the first 100.How are the D2 participants' rank calculated?Does Codeforces calculate our ranks removing them?

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

    Yes, they appear on the official scoreboard but don't count when calculating the rating distribution.

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

Sorry to say,but problem statement of A was not clear enough,which caused unnecessary penalty for many contestants.Also there were too many Announcement during the first hour.Hope,next time problem statement will be clear enough! :(

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

contest is still running(only 6 mins remaining) and i haven't been able to solve a goddamn single problem. wanna die.

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

    that simutaneously word though!! I am irritated!

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

    just realised my mistake, in first question i thought in second operation we're doing x+1,y-1 or x-1,y+1. I SHOULD HAVE READ THE PROBLEM CAREFULLY.

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

[removed]

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

Your goal is to make both given integers equal zero simultaneously : this statement cost me 5 WA + 63 min to submit

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

    Yeah , the term "simultaneously" is diverging from the actual question.

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

      Besides, according to Einstein, simultaneity is relative.

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

What is test 3 of C?

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

Am I the only one who dislikes problems like D where you need to print one of the solutions rather than just saying what the minimum value of best solution would be? Seems annoying to code.

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

    I don't think it requires much additional coding: Just put the elements in a cyclic order into the output arrays:

    https://codeforces.com/contest/1342/submission/78163277

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

      It doesn't require much coding, but it feels like it was put there just to trip up contestants who didn't read carefully. (I'm also biased because I got tripped up as well)

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

      Can we print the cyclic order starting from the smallest element? Thank you

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

    Sometimes I like that style; often (like today) it's a big hint to contestants that the solution to the problem is greedy and not dp.

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

Problem C — test case 3. Can I have some example?

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

    I guess those were like this:

    1
    17 110 2
    100 200
    50 300
    
»
2 months ago, # |
  Vote: I like it +58 Vote: I do not like it

In problem A, the word 'simultaneously' has been used in a very wrong way. Because of this, I thought if we have states (0,1) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and complete waste of 1 hr.

How about using 'both' instead of 'simultaneously'?

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

    We used this word to cover the fact that you cannot make, for example, $$$x = 0$$$, then make $$$x \ne 0$$$, and then make $$$y = 0$$$ without making $$$x = 0$$$. And the notes for the first example showed that $$$(0, 1)$$$ to $$$(0, 0)$$$ is possible.

    I don't think that there is a perfect wording for such problems (''both'' implies some questions like ''can we make $$$x = 0$$$, then make it non-zero, and then make $$$y = 0$$$''). Perhaps a lot of inline-examples would help, but make the statement much more cumbersome.

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

      Contest should be unrated as problem statement was really confusing

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

        I too got 2 wrong submissions and it caused confusion to a lot of people, but simply because of that you cannot make whole round unrated!

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

        I don't think so , i was able to understand problem statement very easily ,Although ,i am not a native english speaker.

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

          I politely disagree with you. If you will see some other questions here, simultaneously implies that both reach together. The distinction is that of "simultaneously reaching zero" and "simultaneously being zero" I think, and in this question they meant "simultaneously being zero".

          Though in contest one can always ask question and clarify, I did that. But rating suffers if one is not able to solve other questions.

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

        Did you mean to write "because my rating nosedived"?

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

      Your example added more confusion.

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

        exactly! instead of saying that the word simultaneously is not to be considered!The explanation was more confusing!

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

      How though would it make a difference if you didnt cover up that fact?

      The word "simultaneously" used in this context literally (in all sense) means that going from state 0,1/1,0 to state 0,0 is not correct

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

        Why does it mean so? If we go from $$$(0, 1)$$$ to $$$(0, 0)$$$ then both numbers are $$$0$$$ simultaneosly.

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

          Because "simultaneously" means "at the same time" or "at the same instant" (try googling it)

          and making x and y to 0 simultaneously means making them 0 at the same time/instant

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

          This is from the problem statement "Your goal is to make both given integers equal zero simultaneously". Here, you didn't make both given integers equal zero simultaneously because one has been already zero the other non-zero.

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

            The last operation makes them both $$$0$$$ at the same time, so the condition is met.

            Okay, there might be more than one way to understand it, but the example notes and the clarification system are working for exactly this reason — if you think that you don't understand something, ask a clarification.

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

              Well, I thought I understood the problem as the way I explained, and sadly that interpretation of the problem statement works on the sample cases.

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

                But it does not work on notes (which are part of the statement).

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

                  I don't think an explanation to a test case justifies an incorrect statement. Everybody is more likely to read the statement and the testcases rather than the explanation to the testcases, especially for problem A

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

              It wasn't one of they way one could understand it. It was the right way to understand. Yes, one could have got the intended meaning by looking at the notes, so to demand that contest be unrated is not sensible at all.

              But please refrain from using words you don't know the exact meaning of.

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

            No, problem statement is correct. They are zero at the same time instant (simultaneously) at the end of the operations. That's it. The fact that one of them was zero beforehand does not matter.

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

              in a way that is simultaneous (= happening or being done at exactly the same time):

              this is from the dictionary, which clearly states being done at the same time. x and y would be 0 after the operation does not mean x and y became 0 simultaneously.

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

                I am not disagreeing that it could have been worded better to avoid any confusion at all. But the author's usage of simultaneously is not wrong.

                Regardless, the round should remain rated.

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

                  The author's usage of simultaneously is incorrect

                  The statement specifically mentions

                  "Your goal is to make both given integers equal zero simultaneously"

                  If it did not have the word "make" I would have accepted the problemsetter's interpretation of things, but adding the word "make" in the same sentence suggests that both x and y have to BE MADE equal to 0 at the same time and not that they have to both BE 0 at some time.

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

                  Regardless, the round should remain rated

                  I never said anything about the round being rated or unrated. Just wanted the authors to know that statement was misleading for some people which could have been avoided.

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

                You're trying to make them both be 0 simultaneously, not change them to 0 simultaneously, and the problem statement obviously said the former way.

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

                  Exactly, making them zero at exactly the same time , that's what simulataneously means. And honestly if you are differentiating between make and change then by doing so even you are agreeing that it was ambigous.

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

                  the statement said "make both", not "make both be"

                  make both suggests changing them to 0 simultaneously

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

                  If you change one to 0 after the other, you're still making both given integers equal zero at the same time, not implying you have to change them at the same time. I don't get the confusion.

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

                  The debates reached maximal permitted depth Let us stop, we both are viewing it from different angles and thus it seems different to both of us.

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

              Your goal is to make both given integers equal zero simultaneously, i.e. $$$x=y=0$$$

              "Make ... simultaneously" might be taken to mean that both numbers become equal to 0 at the same instant, not just that they are both 0 at some moment in time. Given the clarification $$$x=y=0$$$, the word "simultaneously" could have been safely omitted.

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

          yes both numbers are zero simultaneously, but the statement says "your goal is to make both numbers equal to zero simultaneously". This is a dangling modifier as it is unclear whether "simultaneously" refers to the numbers being equal to zero, or to making the numbers equal to zero.

          I think removing the "simultaneously" actually makes the statement clearer. If you want to emphasize that both numbers need to be zero at the end, I would prefer phrasing it as "your goal is to make both numbers zero after all the operations"

          (just sharing what I think people are complaining about, I understood the statement in one try because of the example)

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

      You could perhaps say, at the end of all operations, $$$x$$$ and $$$y$$$ must both be $$$0$$$. The current statement wasn't optimal (the announcement could have been part of the problem statement), but I agree that the question itself wasn't ambiguous.

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

test 2 for problem A is just making me nuts..

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

    me too. T_T

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

    I guess you missed "long long". The answer is overflowing integer limits.

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

      Not really. Used JavaScript for fun, turned out to be not so fun :D And most annoying thing — the solution was correct.. Congrats to me — I've played myself.

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

    me too :c

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

I reduced the problem E to the following:

Distribute n distinct objects into n-k distinct bags such that each bag gets at least one object. This is solvable through Inclusion-Exclusion but how to do it efficiently? Is there any other way to solve the problem?

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

    yes, i also reduced to exact same, but cant move ahead after that.

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

    .

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

    Another solution described here

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

    The number of ways to put $$$n$$$ objects into $$$n-k$$$ bags is $$$(n-k)^n$$$. This also counts all the configurations with one empty bag, so we should subtract $$$(n-k-1)^n\cdot\binom{n-k}{1}$$$ (number of ways to choose the 1 empty bag, and put $$$n$$$ objects into $$$n-k-1$$$ bags). Now, this subtracts off too many configurations with two empty bags, so we should add $$$(n-k-2)^n\cdot\binom{n-k}{2}$$$. Continuing this gives the answer as

    $$$\sum_{j=0}^{n-k} (-1)^{j} \cdot (n-k-j)^n \cdot \binom{n-k}{j} .$$$
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Thanks emma, I just saw your submission. Damn it! It didn't occur to me to use binary exponentiation to solve it. I just gave up after reaching the expression :(

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

    After you've decided a distribution with positive integers $$$a_1,...,a_{n-k}$$$ and $$$\sum a_i = n$$$, you can arrange them in $$$\frac{n!}{\prod a_i!}$$$ ways. So the answer is coefficient of $$$x^n$$$ in $$$\left(x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots\right)^{n-k}=\left(e^x - 1\right)^{n-k}$$$. Now you can expand it with binomial theorem and extract answer in $$$\mathcal O(n)$$$.

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

    Can you tell how you reduced the problem to this?

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

      To attack every empty cells, either every row or every column contains a rook (both only if $$$k = 0$$$). Now notice that , if, say, you have decided to fill every column, you will have to group pairs of attacking rooks within the different rows. A row will consist of possibly $$$0$$$, or more rooks. $$$n$$$ rooks means $$$n-1$$$ pairs, for $$$n \geq 1$$$. Now we are almost there for the reduction. There will always be $$$n-k$$$ groups of row (or "used" row if you prefer). If less, it can be shown that there are too much pairs. If more, there are not enough. The $$$n-k$$$ rows are the "bags". The position of the rooks in the columns is important. That is why you have the forumla $$$(n-k)^n$$$ at the beggining.

      $$$ $$$

      At the end you also need to multiply by two if $$$k=0$$$ (because of what I said at the beggining) and... you have to take into account that you also have to ditribute the "bags" ($$$n-k$$$ of them) to the different rows ($$$n$$$ of them). This is yet another binomial coefficient.

      $$$ $$$

      I hope this was somewhat helpful, the editorial should be better at explaining the solution anyway :)

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

        Thanks a lot for the great explanation

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

        I would like to add an explanation for "why exactly n-k groups of row?" Let q denote the number of chosen rows. Assume our chosen rows are r(1), r(2) ... r(q). Let Cr(i) denote the number of rooks in each row. As the number of attacking rooks for each row is Cr(i)-1 , so we have this equation: Cr(1)-1+Cr(2)-1+ .. +Cr(q)-1 = k
        From this we can get Cr(1)+Cr(2)+...+Cr(q) = k+q
        So q = Cr(1)+Cr(2)+...+Cr(q)-k = n-k

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

for future reference

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

Video tutorials here for some of the tasks, you can also join my discord server for more insights

C

D

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

Wierd Runtime, please help! I am getting Runtime Error on submitting div2D on Codeforces on 1st sample, but same code & input runs & produces perfectly correct output on online IDE at Codechef.com/ide !

https://codeforces.com/contest/1342/submission/78209696

How is that possible? I have correct code but can't get accepted because of this. MikeMirzayanov pikmike

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

    When weird stuff like this happens, this usually means that your code has undefined behavior (like indexing an array with an invalid index or using the value of an uninitialized variable).

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

      I cross verified, there seems no variable uninitilaized. set I am using, made sure to only erase if a value exists. That makes me believe, there is no undefined behaviour. Please point out if I am missing something. Thanks Be_dos

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

        RTE is because you are looping through set and erasing from it both in the same loop. for (auto cq: mem) and mem.erase(cq);. Mike might not be able to offer any help here.

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

    same thing happens to me also.

    https://codeforces.com/contest/1342/submission/78207115

    My code also gives a runtime error. I tried on CodeChef ide also, it works perfectly. But I can't find the reason.

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

"Your goal is to make both given integers equal zero simultaneously"

Why on earth did you have to use the word "simultaneously"? I thought it means we have to use operation 2 to go from 1 1 to 0 0 (to make it simultaneous) I wasted more than 20 mins on this until i read the description of the test case and asked the question to the setters

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

    lmao same, just added to consider the case 'a' on both x and y and it got accepted

    EDIT: sad thing is, i just noticed that problem statement says 'move from 0:1 to 0:0 is valid'

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

I missed placing exactly n rooks part in E and tried solving this problem for almost entire duration of the contest: placing some x rooks on the board such that either all rows are occupied or all columns are occupied (or both). :/

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

how to solve F?

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

The word simultaneously in the text of Problem A was seriously misleading. It made it seem like the last operation must have been of type 2 so that both values would arrive at 0 simultaneously.

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

    wait that wasn't what they meant?

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

      Apparently the values could arrive to 0 at different steps, as well. They made an announcement stating that during the contest.

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

        oh wow. I was just looking at the questions thank god I didn't give the contest. I mean what its not like I could go any lower lol

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

    correct! atleast make the round unrated

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

I misunderstood the term "simultaneously" and wasted 15 mins.

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

Problem A made me zoned out for 25 mins.

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

Upsolving C and D live on YouTube: https://youtu.be/XeK6lYKd8W4

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

So my code for problem 'C' decided to run correctly 10 seconds after the contest cool cool cool cool cool cool cool cool cool cool cool cool cool cool

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

    Try this .
    1
    3 4 1
    12 12
    Ans should be zero but your code gives 1 .

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

      include

      include

      include

      include

      include

      include

      include

      include

      include

      include

      include

      include

      include

      include

      define endl "\n"

      define pb push_back

      define ll long long int

      using namespace std; int main() { int t; cin>>t; while(t--) { ll a,b,q; cin>>a>>b>>q; if(a==b) { for(int i=0;i<q;i++) { ll l,r; cin>>l>>r; cout<<"0"<<" "; } cout<<endl; } else if(a<b) { ll k=0;

      for(int i=0;i<q;i++)
          {
              ll l,r;
              cin>>l>>r;
              ll cnt=0;
      
             cnt=r-max(l,b)+1;
            if(b%a!=0)
             cnt-=b*((r/a)/b-(max(l-1,b-1)/a)/b);
             else 
             {
                 ll g=__gcd(a, b);
                  cnt-=b*((r/g)-(max(l-1,b-1)/g));
             }
      
              cout<<max(cnt,k)<<" ";
          }
          cout<<endl;
      }
      else 
      {
           ll k=0;
           for(int i=0;i<q;i++)
          {
              ll l,r;
              cin>>l>>r;
              ll cnt=0;
      
             cnt=r-max(l,a)+1;
             if(a%b!=0)
             cnt-=a*((r/a)/b-(max(l-1,b-1)/a)/b);
             else 
             {
                   ll g=__gcd(a, b);
                   cnt-=a*((r/g)-(max(l-1,b-1)/g));
             }
              cout<<max(cnt,k)<<" ";
          }
          cout<<endl;
      }

      } return 0; }

      how about now??

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

        At least put your code in spoiler ....
        1
        9 12 1
        1 192
        Ans is 121 and your code gives 169 .

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

In problem A, the word 'simultaneously' confused me. Because of that, I thought if we have states (1,0) first we have to go to (1,1) and then to (0,0). It cost me 3 penalties and waste of 25 minutes.

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

    just simple English, simultaneously means at same time. so A and B have to be zero at same time. you're not even supposed to have 1 0 in first place

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

      What i meant to say is if we have (2,1) and a=1,b=10 then with use of Simultanouesly i calculated 10+1=11 as cost whereas actually it meant 2*(1)+1=3

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

Hi, I tried a greedy solution for D. I sorted an array and added tests from the smallest, for each of them checking how many more I could add to one testcase. It got WA on test 11.

What do you think is the counterexample?

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

    Try this:

    5 3
    1 2 3 2 1
    2 1 1
    

    You can construct an answer with 3 multitests instead of 4 as given by your code.

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

      I cannot understand why this test case would give WA for greedy, I think it works!

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

      Thanks! This is what I missed. The greedy solution doesn't work for repeated elements.

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

        Can you please explain why it wouldn't work?

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

          You can make such testcases: {1 2} {1 2} {3} Whereas my solution would give: {1 1} {2} {2} {3}

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

Hey MikeMirzayanov, I got unnecessary 2 WA in problem A because I considered the condition to make both x and y simultaneously zero. Though I can't ask back the overall time lost due to this but if possible can those two penalties be removed! Thanks in Advance.

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

    in correction too! it was not mentioned correctly that simutaneously is not to be considered! worst educational round!!

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

A and B again supersimple problems hidden in complecated text.

In A I needed half an hour to get it that we cannot use opposite signs in operation b. Of course the statements states so, but that was mostly invisible to me.

And D, sorry, simply to much words, I am not able to understand the sentences.

Usually posting like this get downvotes. I know. Thanks.

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

What's wrong with my solution of F?

What's the meaning of "wrong answer 'to' position should be in [1, 14] (test case 4)"?

my submission

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

    It looks like you print an auxiliary action somewhere in test case 2, so the numeration changes.

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

      Well,I thought that I had printed the same answer as the example ouput,in test case 2.

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

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

Can someone tell me where my greedy approach for D fails. Here is what I did I sort the tests with respect to their sizes. I pick the array with largest size and put it in first testcase. Now I pick the next largest array , say of size X and the testcase with minimum tests till now and check if No. of tests in this testcase + 1 <= c[X]. If the condition holds, I put this test in the chosen testcase, otherwise make a new testcase. I got a wrong answer on TC 11

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

    try this test case :

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

      I couldn't understand how the greedy solution with your test case would give a different answer. Can you provide any other test case?

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

      Kill me !! Kill me. My Greedy approach is correct . There was a single line I missed in the implementation. I used a min heap and I forgot to insert the previous topmost element(which I had popped) whenever I am creating a new testcase. It got accepted now and I am confused why could not I find this in more than an hour.

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

        It happens...

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

        can u pls explain your appraoch in brief I'm not able to get the min heap part .

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

In Problem C,

O(test * 3 * gcd(a, b)) times remainder calculation cost TLE on test 4. Does the remainder calculation cost this much?

:(

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

    Your time complexity for solution 78195345 is O(test * q * a * b). For every test, for every query you iterate x at most len times (which can equal to a * b) so you have around 100 * 500 * 200 * 200 = 2e9 operations times constant. You also have remainder calculation so I guess it is a rather predictable verdict.

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

      Ohh! Thanks. My Bad...

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

      But how this solution passed 78177360? I think it is also O(T*q*a*b). The time limit was 3.5 sec though.

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

        Then I was wrong and this solution passes because it has precalculated remainders and the previous one did not.

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

How is 78182933 doesn't get TLE?

It has linear complexity for every query or did I miss something?

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

    As far i understand he calculates curr in the loop which is never used after that. As it is never used so compiler removes that loop as a part of optimization. As a result the loop doesn't get a chance to run so there is no tle.

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

      Thanks, you were right. I don't know that compiler can skip unnecessary operation.

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

Question C: Which number $$$x$$$ in the range $$$[100,200]$$$ other than $$$141-149$$$ gives $$$(x \mod 7)\mod 10 = (x \mod 10)\mod 7?$$$ The answer is $$$91$$$, so there should be $$$10$$$ such numbers.

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

Fail on 1605th number.

Oh cmon? How can I debug? 78209018

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

Got no idea what's wrong with my C submission.

Could anyone take a look at it? https://codeforces.com/contest/1342/submission/78197703

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

    Why do you post the link of this blog here?

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

    You should've at least posted your submission (78197703) here and not the link of the blog entry.

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

    Update the link to submission

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

    Try below test

    1
    4 6 1
    1 10
    
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    one major thing is the for loop from l to r.

    the range can be way orders of magnitudes over 10^9 .. so you'd get TLE even if your solution passed test 3.

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

is it possible to solve C without prefix sum / dp ?

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

    There's a dp/prefix sum solution for C?

    I just excluded the numbers from i*LCM(a,b) to i*LCM(a,b)+max(a,b) for i=0,1,2,3.. from the range l to r

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

    Yes it can be solved. You can check my submission https://codeforces.com/contest/1342/submission/78176991

    You can use the fact that x%a%b == x%b%a occurs at every multiple of lcm(a, b) for exactly max (a, b) times. You just get that and you have your answer in O(1) for each query, or log(n) if you consider GCD.

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

      I've tried things similar to this but it's not working for me https://codeforces.com/contest/1342/submission/78229431

      can you tell any counter case on which this will be failing ?

      UPD: Just figured I was unnecessarily assuming that if a and b are divisible then the o/p will always be 0. thanks for the help tho

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

        i also assumed the same and was getting WA on test 2 can you pls explain why that assumption is wrong my submission on c

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

          I also put the same condition though, and mine is accepted, so it must be something else, I will try looking into test cases after system testing.

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

        The problem was not the a and b divisible condition, but you did not take inputs when they were divisible. You just printed 0 q times. you should also take left and right inputs.

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

that fucking simultaneously word in problem A .......

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

    I don't even understand what are you talking about.

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

      they have mentioned that we have to convert x and y into zero simultaneously and later they made an announcement that it is not req.

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

        I agree that it might be misleading but I didn't have any problem with understanding that word. I take it as the meaning of a simultaneous equation and didn't notice that word until I see this comment.

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

          Pls don't take it as the meaning of a simultaneous equation...

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

simultaneously means at the same time, doesn't it?

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

    exactly bro but then they later said that it is not req.

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

      This is evident. It didn't help me at all.

      If they made it more explicit than in input 1 0, the answer would be a, I would understand.

      "In particular, it is possible to move from x = 1, y = 0 to x = y = 0."

      In my mind: 1 0 1 1 0 0 ans = a movement with A and one with B.

      When you are participating in a contest, you just need to know code. When you create an EDUCATIONAL, you at least need to make understandable statements.

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

(https://codeforces.com/contest/1342/submission/78163668)

(https://codeforces.com/contest/1342/submission/78134634)

Exactly same solutions[user:MikeMirzayanov][user:pikmike] Disqualify both of them from contest

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

Hm, my idea for E was wrong, but I don't know how:

Something like, when $$$0 < k < n$$$, we know either all rooks will be on distinct cols or all rooks will be on distinct rows, (and not both since $$$k \neq 0$$$), since two rooks sharing a col and two rooks sharing a row would leave some row and some column untouched (and thus the square at their intersection untouched). Then, we can WLOG assume all rooks are on distinct rows.

Consider all the columns that contain a rook. If we consider all the rooks on that column a path graph, we see that it contributes exactly the number of edges it has to the number of pairs that attack each other. However, we also know that there will be $$$k$$$ edges in total, and since the whole graph is a forest, there should be $$$n-k$$$ components, i.e. $$$n-k$$$ columns containing rooks. So, the question then becomes how to partition $$$n$$$ objects into $$$n-k$$$ nonempty components (stirling # of second kind), and then multiply that by the $$$n-k$$$ columns that the rooks can occupy, and then multiply that by 2 to account for distinct columns cases.

Anyone know where the error in this logic is? I plugged the formula into wolfram (mod[2*stirlings2[1337, 1295]*(1337 choose 1295), 998244353]) for test 4 and it was incorrect.

EDIT: As BledDest pointed out, one just needs to multiply this final formula by $$$(n-k)!$$$ to index the columns for specific subsets, then it should be fine.

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

    When you multiply the stirling # of second kind with a coefficient to choose $$$n - k$$$ columns, you should consider the fact that the subsets in definition of stirling numbers are not indexed.

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

      Ah, good catch! Simple change to the formula. Thank you!

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

    shouldn't answer be simply stirling(n,n-k)*chose(n,n-k)*2 ?

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

      Stirling number would count all required possible arrangements. Let one such possible arrangement be set1. Set1 would contain n-k elements, each element would correspond to a valid arrangement for a column.

      Then you have to select n-k columns from the board to place those valid arrangements (combinations), let the set of selected columns be set2.

      Then each different function from set1 to set2 would correspond to a different way you can arrange the rooks. (The function needs to be one-one and onto i.e invertible). Number of different functions from set1 to set2 is (|set1|)! or (n-k)!.

      You can also think of it as you have n-k diffrent objects and you need to put them in n-k different slots, how many ways are there to do it (permutations).

      Hope it helps!

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

    a counter test case in case it helps : 1 248 12 2 491 1289 839 1234

    o/p for this should be 551 243 .

    Hope this helps !

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

Thanks.

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

    The only contest u joined is an April Fools’ Contest. Why would u even expect it to be a rated round.

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

    The first contest you took part in was April's Fools so it was unrated There is a 12 hour hacking phase after the contest so wait and you will get your rating tommorow.

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

My rating and confidence level is going down simultaneously....Thanks for problem A.

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

    xD same happened with me too!

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

    similar situation i was in last contest where i took around 90 minutes to solve A. Then past 2 days i solved around 20+ Div.2A from contest page 1; it really helped today

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

    you can't have a bad day as bad as mine ! I made a small typo in A initially, after making changes I forgot resubmitting it... :(

    Thanks to standings table that i finally submitted it after more than a hour .

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

Time Limit of problem C was misguiding.

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

For problem B, I approached the question the same way as others. Printing "01" up to s.length() times. But in the clarification panel, the value of k for string "0011" is 4 but it is 2 if we print "01" up to n times(n == s.length()). Can anyone explain what am I missing here?

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

    I think you are right. The statement of B make me confused!

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

    it just states the definition of a period. Explanation in clarification panel is not much related to original problem.

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

task A

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

Wait darn solved ABD and didn't get C...played around with gcds/mods and found some progress but whatever. Why doesn't O(ab(t+q)) pass? It's the naive solution but it seems to be well within the time limit of 3.5 seconds (2.4*10^7 operations -- i've had solutions with more operations and less time pass)

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

    You can do it in O(t*(ab+q)) if you precalcutate a prefix array. Such solution of mine took 498ms.

    This is one thing and the second is maybe Java is slower than C++.

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

      Ah ok, I should have done prefix array, maybe the complexity would have been reduced by a constant factor and pass but yeah C++ is definitely faster than java too :(

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

    can you please tell me how many max operation can be done in 1 sec

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

      Not entirely sure but somewhere between 10^7 and 10^8 (since for some problems O(N^3) for N=500 passes and some other variants which have >=10^8 operations)

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

    and also how mush time should i spend on C and then jump to D.

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

    Yeah, I also didn't get why the TL. No idea why my solution failed. But in the end I managed to do O(1) per query. The main thing to notice was that every number from b to lcm-1 is good. So you don't even need to precalc anything first and can answer each query in constant time.

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

      can you please explain

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

        First you need to check how many numbers are there between 1 and lcm-1 that satisfies the property. Let's say a is smaller. Then any number X greater than or equal to b will satisfy. We can prove this as follows.

        Let's say X = bq+r, Then (X%b)%a = r%a. Now we need to write (X%a)%b in similar form. Here notice that bq is less than X, and since X is less than the LCM, bq is also less than LCM. Therefore it can't have a as a factor.

        So bq = aq'+r'. Therefore X = aq'+r'+r. Taking modules, we will get (r+r')%a.

        Since r' is neither 0 nor a, therefore it is different than r%a. Thus any number greater than equal to b satisfies.(Upto LCM that is)

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

          how are you comparing (r+r')%b and r%a???

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

            (X%a)%b is reduced to ((r+r')%a)%b. If you notice, the second modulo by b is unnecessary as (r+r')%a is always less than b. So it reduces down to comparing r%a and (r+r')%a