By awoo, history, 4 years ago, translation, In English

Hello Codeforces!

On 26.04.2020 17:35 (Московское время) Educational Codeforces Round 86 (рейтинговый для Див. 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 Neon 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 Sugar_fan 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 phyzzmat 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 sevlll777 0:00
B Aerosmith 0:02
C DreamLolita 0:03
D xb0nS 0:14
E AaParsa 0:17
F chemthan 1:07

UPD: Editorial is out

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

| Write comment?
»
4 years 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 "

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

Lets cross 25000 this time!

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

    Oh no. Think about CF servers.

    • »
      »
      »
      4 years 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.

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

        I hope so.

      • »
        »
        »
        »
        4 years 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.

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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.

»
4 years 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.

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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?

      • »
        »
        »
        »
        4 years 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.

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

      Are there points for hacks in educational rounds?

    • »
      »
      »
      4 years 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

    • »
      »
      »
      4 years 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?

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

        Yes it is only name of verdict.

        • »
          »
          »
          »
          »
          4 years 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?

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

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

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

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

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

      Normal codeforces round has 50 penalty for wrong submission afaik.

    • »
      »
      »
      4 years 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 ...

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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 !!

          • »
            »
            »
            »
            »
            »
            4 years 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.

    • »
      »
      »
      4 years 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??

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

        No. there is no hacking phase in div1,2 rounds. But you can hack during contest.

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

    You can read about educational rounds here

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

Good Luck everyone

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

  • »
    »
    4 years 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
    • »
      »
      »
      4 years 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

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

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

every time

»
4 years 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?

»
4 years 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

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

    _ (Reference — Evro)_

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

      Damn ,Stealing memes even in codeforces..

      • »
        »
        »
        »
        4 years 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

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

»
4 years 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!

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

    You had to edit your comment thrice to say this?

    • »
      »
      »
      4 years 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 :)

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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

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

            Well, you must not be an expert then :p

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

[removed]

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

What people think simultaneously means??

»
4 years 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 :|

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

simultaneously really ? :( @awoo MikeMirzayanov

  • »
    »
    4 years 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.

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

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

    • »
      »
      »
      4 years 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'

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

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

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

    And 01 has period of 2 :| Omg :(

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

that C killed me

»
4 years 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?

  • »
    »
    4 years 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.

»
4 years 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! :(

»
4 years 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.

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

    that simutaneously word though!! I am irritated!

  • »
    »
    4 years 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.

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

[removed]

»
4 years 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

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

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

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

What is test 3 of C?

»
4 years 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.

  • »
    »
    4 years 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

    • »
      »
      »
      4 years 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)

    • »
      »
      »
      4 years 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

  • »
    »
    4 years 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.

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

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

»
4 years 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'?

  • »
    »
    4 years 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.

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

      Contest should be unrated as problem statement was really confusing

      • »
        »
        »
        »
        4 years 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!

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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.

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

      Your example added more confusion.

      • »
        »
        »
        »
        4 years 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!

    • »
      »
      »
      4 years 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

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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

        • »
          »
          »
          »
          »
          4 years 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.

          • »
            »
            »
            »
            »
            »
            4 years 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.

            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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).

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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

            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

          • »
            »
            »
            »
            »
            »
            4 years 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.

            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

        • »
          »
          »
          »
          »
          4 years 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)

    • »
      »
      »
      4 years 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.

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

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

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

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

»
4 years 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?

  • »
    »
    4 years 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.

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

    .

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

    Another solution described here

  • »
    »
    4 years 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} .$$$
    • »
      »
      »
      4 years 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 :(

  • »
    »
    4 years 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)$$$.

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

    Can you tell how you reduced the problem to this?

    • »
      »
      »
      4 years 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 :)

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

        Thanks a lot for the great explanation

      • »
        »
        »
        »
        4 years 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

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

for future reference

»
4 years 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

»
4 years 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 awoo

  • »
    »
    4 years 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).

    • »
      »
      »
      4 years 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

      • »
        »
        »
        »
        4 years 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.

  • »
    »
    4 years 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.

»
4 years 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

  • »
    »
    4 years 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'

»
4 years 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). :/

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

how to solve F?

»
4 years 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.

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

    wait that wasn't what they meant?

    • »
      »
      »
      4 years 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.

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

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

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

Problem A made me zoned out for 25 mins.

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

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

»
4 years 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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    4 years 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 .

    • »
      »
      »
      4 years 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??

      • »
        »
        »
        »
        4 years 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 .

»
4 years 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.

  • »
    »
    4 years 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

»
4 years 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?

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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!

    • »
      »
      »
      4 years 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.

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

        Can you please explain why it wouldn't work?

        • »
          »
          »
          »
          »
          4 years 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}

»
4 years 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.

  • »
    »
    4 years 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!!

»
4 years 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.

»
4 years 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

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

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

»
4 years 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

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

    try this test case :

    Spoiler
    • »
      »
      »
      4 years 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?

    • »
      »
      »
      4 years 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.

»
4 years 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?

:(

  • »
    »
    4 years 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.

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

      Ohh! Thanks. My Bad...

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

»
4 years 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?

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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.

»
4 years 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.

»
4 years 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

»
4 years 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

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

    Why do you post the link of this blog here?

  • »
    »
    4 years 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.

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

    Update the link to submission

  • »
    »
    4 years 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.

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

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

  • »
    »
    4 years 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

  • »
    »
    4 years 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.

    • »
      »
      »
      4 years 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

      • »
        »
        »
        »
        4 years 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

        • »
          »
          »
          »
          »
          4 years 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.

      • »
        »
        »
        »
        4 years 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.

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

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

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

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

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

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

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

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

          Please never take it as the meaning of a simultaneous equation dude

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

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

»
4 years 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

»
4 years 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.

  • »
    »
    4 years 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.

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

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

  • »
    »
    4 years 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 ?

    • »
      »
      »
      4 years 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!

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    4 years 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 !

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

Thanks.

  • »
    »
    4 years 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.

  • »
    »
    4 years 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.

»
4 years 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.

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

Time Limit of problem C was misguiding.

»
4 years 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?

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

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

  • »
    »
    4 years 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.

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

task A

»
4 years 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)

  • »
    »
    4 years 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++.

    • »
      »
      »
      4 years 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 :(

  • »
    »
    4 years 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

    • »
      »
      »
      4 years 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)

  • »
    »
    4 years 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.

  • »
    »
    4 years 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.

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

      can you please explain

      • »
        »
        »
        »
        4 years 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)

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

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

          • »
            »
            »
            »
            »
            »
            4 years 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

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

    You can answer each query in O(1).

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

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

      Came up with the same logic during the round, but sadly my implementation was a complete garbage. :/

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

It is too hard to read the Problem D statement.

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

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

This cost me 3WAs and almost 20 minutes

I'm disappointed

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

    i ll change my username to "Simultaneously" next year as a reminder for today's problem A!

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

Why does life as well as codeforces keep on fucking with me simultaneously! Eh? Thanks to Problem A.

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

i tried solving question C using digit dp as I was recently studying this, while solving I realised it would tle as my dp was having high dimensions for modulus of a and b, can anyone tell me how to do it using digit dp if possible

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

    I dont think so TLE. Because a,b<=200. Should have passed with 3.5 seconds. :)

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

      their lcm can be as high as 40000 , so it might give tle if I set mod variable this high my dp looks like dp[position][tight][start][mod], here mod can be upto 40000, position upto 20, tight is bool, start is bool, plus 500 queries and 100 test cases

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

Please uphack my solution to F. I am not using any kind of bitmask dp.

UPD:Got hacked by one of the authors. That's kinda cool. Thanks Neon.

UPD2:Somehow I made it work in 1.5s just by reserving memory for vectors.

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

Am i the only one who felt much more easier with D than C? For me, D's approach was quite simple, which i can't say for C (and also TL for C kinda confused me).

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

    For me ABCD was quite hard, and, well, E was to hard at all :/

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

Is C solvable with digit dp? If yes, it would be awesome if someone explain the solution with digit dp.

Thanks in advance. :)

»
4 years ago, # |
Rev. 4   Vote: I like it +37 Vote: I do not like it

Problem C can be solved in $$$\mathcal O(1)$$$ per query (assuming it takes constant time to compute GCD) without any preprocessing. Assume $$$a < b$$$ and take some $$$x = qb+r$$$ with $$$0\leq r < b$$$. Then $$$(x\bmod a)\bmod b = (x\bmod b)\bmod a$$$ translates to $$$x\bmod a = (x\bmod b)\bmod a$$$ and thus $$$qb+r \equiv r \pmod a$$$ implying $$$a$$$ divides $$$qb$$$. This gives us $$$\frac{a}{\gcd(a,b)}$$$ divides $$$q=\left\lfloor\frac{x}{b}\right\rfloor$$$. So given $$$l,r,a,b$$$ we're looking for number of $$$x$$$ such that $$$\frac{a}{\gcd(a,b)}$$$ divides $$$\left\lfloor\frac{x}{b}\right\rfloor$$$ which is easy to count solving an inequality or two.

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

    Yes, that is exactly how I solved the problem. I didn't realise there is an easier solution.

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

According to A, everyone reached the finish line simultaneously.

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

OK well, why the heck do people write this kind of obfuscated code? only to evade hacking? https://codeforces.com/contest/1342/submission/78201792

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

    This seems to be a consistent obfuscator, his solutions look like this for three contests in a row. MikeMirzayanov awoo

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

    what type of code is this ? i mean it doesn't look like normal c++ codes in english, and how did it got AC?

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

Why would greedy solution not work for problem D?

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

    It works. Maintain a set that stores indexes of test cases ordered by their current size and iterate over the range $$$[1,k]$$$ in descending order (from $$$k$$$ to $$$1$$$).

    In $$$i'th$$$ step, take the index of the test case with the smallest size from the set.

    If it's size is less than $$$C_i$$$ then fill it with the current value $$$i$$$ until its size becomes $$$C_i$$$ or all the array with size $$$i$$$ become used.

    Otherwise, create a new test case and fill it with current value $$$i$$$ until it's size becomes $$$C_i$$$ or all the array with size $$$i$$$ become used.

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

      I find your solution very similar to mine except that i'm getting a WA on test 11. Can you check it why?

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

        Your solution fails on following testcase
        6 2
        1 1 2 1 1 2
        3 1

        Your code prints 3 testcases whereas answer is
        2
        3 2 1 1
        3 2 1 1

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

          Thanks. It seems that I forgot to reinsert the popped element in set.

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

        I was getting WA on test 11 too. Try your code on this input-

        6 10
        5 1 10 8 8 7
        6 6 4 4 2 2 3 2 1 1
        

        The correct output should be-

        2
        3 10 8 7
        3 8 5 1
        
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Why on earth did I solve A for any whole x, y (including negative) ?

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

    I just realized that I solve it for the negative too after seeing your comment. There is a negative number in the example of the question when it introduced the operations (not the test case). That was so misleading.
    https://codeforces.com/contest/1342/problem/A

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

    meetoo

    i am with you init bro.

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

    Because it was problem A and most people just want to solve it ASAP without giving it much time.The people who faced problem due to the word simultaneously would not have faced the problem if they read the samples. But people generally want to solve it as quickly as possible without even reading it completely xD

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

why there are so many successful hacks on C

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

    Maximums of hack submissions of problem C are Time Limit Exceeded(TLE). Because worst cases are not available in the pretest.

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

Am I the only person who didn't even notice the simultaneously word in the contest time but successfully pass the pretests?

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

    You are not alone buddy XD

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

    Maybe because of my poor English, I just read it but did not pay attention to it and passed the pretests.

»
4 years ago, # |
  Vote: I like it -31 Vote: I do not like it

Statement of problem D is difficult to understand + printing the actual answer was really annoying

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

    I thought so many different useless way to print the answer and in the end I just used V[i%Test].push_back(M[i]) after sorting M. Here Test is the Min number of tests.

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

      Yeah I did exactly the same thing (after the contest though lol) But that was annoying I got the min number of test cases like 30 min before the end of the contest

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

    It's actually not hard to print the actual answer. If you just sort the array sizes and assign it to all tests turn by turn greedily, by exchange argument, it will satisfy the condition

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

Does anyone have any idea on Test #16 in D? I can't see why am I getting TLE in my presumably linear desicion: 78188697

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

    Look at this case:

    n = k = 200000, m[i] = i, c[i] = 1

    For every i = k...1 you will iterate from 0 to n-i.

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

Problem C https://codeforces.com/contest/1342/submission/78221117 My code fails on testcase 2..please give some test cases..on which my code fails..

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

https://codeforces.com/contest/1342/submission/78225763 can someone give me a testcase where my code fails?

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

Doh! Just now saw that problem E specified "n rooks". I was trying to solve it for an arbitrary number of rooks, which is much, much harder :-(

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

    How would you solve it if you can have ANY number of rooks? I also didnt read the 'n rooks' condition at start. To make it a bit simpler lets say the constraints arent a problem. How can we calculate the answer in the best possible time complexity?

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

      Ok, here's about how far I got. Let's start by giving a number of rooks X; we'll come back later to which values are valid.

      Let f(r, c) be the number of ways to fill an r×c grid (1 <= r, c <= n) with X rooks such that every column has at least one rook. I think this can be computed with inclusion-exclusion in O(n³). Next let g(r, c) be the number of ways to fill an r×c grid with X rooks such that every row and column has at least one rook. Again, I think inclusion-exclusion can compute this (from f) in O(n³).

      There must be either a rook in every row or in every column (or both) to attack all empty squares. Let's consider the "every row" case, and assume exactly c columns are occupied. Then K=2X-n-c so we can solve for X, and take g(n, c) times a suitable binomial coefficient. Repeat for all values of c, and treat the all-columns case similarly.

      That should give O(n⁴) time overall, assuming I haven't missed anything. I feel like there might be some clever way to reduce it to O(n³) but I'm not seeing it at the moment.

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

    I missed n rooks part too. But I went back to reading the statement when I realized you can't even find out the number of ways of placing k rooks in an n x n board (without any constraints) in time better than $$$O(n^2)$$$.

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

    I missed the statement 'each empty cell is under attack' and spent 30 minutes solving the task without it.

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

I'm trying to solve C by utilizing the fact that x%a = (x%b)%a For example if a is 4 and b is 6, then I'll find the count of numbers having remainder (0 with 4 & 0 with 6), (0 with 4 and 4 with 6), (1 with 4 and 1 with 6), (1 with 4 and 5 with 6)....(you get the idea).

I find the count of numbers having some (p,q) remainders with (a,b) respectively by finding anyone such number, then every other number with same remainders will (I assume this) be situated at a distances of multiples of LCM(a,b).

I could get the sample tests to pass but failed the next test by an error of 1. Is the approach correct?

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

    take x = 6 ,a = 4 ,b = 5 x%a = 2 x%b = 1 ==> 1%a = 1

    so x%a != x%b%a

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

https://codeforces.com/contest/1342/submission/78205413 can someone help me on why this code failed on large values (problem B)...I know i should have printed characters one by one rather than storing in string variable..but why can not a string variable contain 200 characters ??

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

    it have to resize that t1 thats why it is giving tle

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

      Thank you!!..I made a char array now instead of string with size more than maximum number of characters it should hold and it got accepted now.

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

    Either resize t1 to necessary value or use push_back operation. Your t1 has size 0.

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

How to solve problem F?

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

    Suppose we don't have any constraints on the order of elements, the resulting array just should not contain any duplicates. Let's build the result one element after another in ascending order, so each element we create is strictly greater than the previous. To create an element, just use some subset of elements and merge them into new element. This process can be efficiently modeled with the following dynamic programming: $$$dp_{cnt, mask}$$$ is the minimum value of the last element, if we merged all the elements from $$$mask$$$ into $$$cnt$$$ ascending numbers. To model transitions, we simply iterate on the mask of elements that will be merged into a new one, and check if its sum is greater than the last element we created. This runs in $$$O(n3^n)$$$.

    Okay, how about maintaining the order? When we create an element by merging some elements of the original array, let's choose some position of an element we use in merging and state that all other elements are added to it. Then, to ensure that the result is ascending, the position of this element should be greater than the position of the element we chose while building the previous number. We can add the position we have chosen for the last element to the states of our dynamic programming, so it becomes $$$dp_{cnt, mask, pos}$$$ — the minimum value of the last element, if we merged the $$$mask$$$ of elements into $$$cnt$$$ numbers, and the last element originally had index $$$pos$$$ in the array.

    Using some greedy optimizations (for example, we should not iterate on the position we are choosing to merge — it can be chosen greedily as the leftmost position after the position of previous element we are taking into consideration), we can make it $$$O(n^2 3^n)$$$, yet with a small constant factor.

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

      I got $$$O(n 3^n)$$$ 78249435 because I conjectured that the minimum value of the last element can be implicit in $$$dp_{pos,mask} = $$$ (the minimum number of operations, the minimum value of the last element), What do you think ?

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

how many iterations is one second in codeforces?

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

    1,2 or 3s are just to manage the constant factor. In general, if N is 10^6, then O(NlogN) solution will pass, given some caveat. There's a big hurdle of printing, which is the slowest part of the code. So if there's a lot of things to print like, maybe a matrix per test case, or answer to a lot of queries, then that can also affect the time.

    In case of C, I think most of the TLs are because of that.

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

      I agree with you but I would like to know how many iterations are approximately one second in codeforces because what runs on my PC in 5 or more seconds in codeforces gives me in 1 second what left me surprised. I always did the calculation with 1 second as 1e8 iterations and I think this is not the case.

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

I couldn't manage to solve C during the contest even though the recurring pattern was visible.

Here is my submission.

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

My logic was based around multiples of lcm+max(a,b). If someone can find something wrong in the solution please hack it. Thanks in advance!

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

I have logic for C plz indicate what is wrong with it. let a<b. now we can calculate the answer for range [1,b], now as the modulo function is periodic now we can easily manipulate this to get and for the given range.

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

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

I submit to problem C a solution in O (T*(Q + log( max(a , b) ) ) ) and it accepted. You can see it here: https://codeforces.com/contest/1342/submission/78217111 . I would like to be told if it is correct or not.

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

    78195754 Can someone help me know why this soln exceeds the Time limit. Thanks.

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

      Your LCM can be around 40000, so in worst case, you'll have this much iteration per query.

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

      your complexity is $$$O(tq\operatorname{lcm}(a,b))$$$ which can be $$$O(100\times 500\times 40000)=O(2\times 10^9)$$$, which could easily exceed time limit.

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

        So a prefix sum based solution should work right?

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

          my prefix sum based solution passed.

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

I did many unsuccessful hacking attempt will it result in any negative points? Please guide me!

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

I was trying to solve Prob.D using priority queues , but I'm getting TLE

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

I tried keeping time O(N) but maybe because I'm copying entire pq.top() in temp each time I'm getting TLE. But how do I avoid this ?

I simply tried using (pq.top()).push_back(A[i]) but it throws some error saying "passing ‘const value_type’".

can someone help me resolve this ?

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

    You can check out my solution: Soln

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

    The priority_queue does not allow you to change the values inside (because it might change the order), so it only returns a const reference with .top() and you have to pop and then push the elements again.

    To fix it, you could e.g. use vll* or shared_ptr<vll> inside your queue, which is cheap to copy.

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

I have seen many solutions for problem D failing on 11th testcase .What was that can anyone tell me??

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

How does https://codeforces.com/contest/1342/submission/78244632 pass but https://codeforces.com/contest/1342/submission/78244302 fails? There is only one line change, and that line never gets executed. The 'cout << "???"' line never gets executed, since the test passes.

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

Can someone explain why greedy works for problem D? I have a hard time wrapping my head around it.

»
4 years ago, # |
  Vote: I like it -28 Vote: I do not like it

Is it still going to be rated?

A lot of users were affected by the incorrect English in problem A

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

    тогда rated для РУССКИХ!

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

    Yeah i think they should not have mentioned the word "simultaneously". I too was confused. But seeing the number of submissions in first few minutes i think it was clear that there was no need of overthinking.

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

      "But seeing the number of submissions in first few minutes i think it was clear that there was no need of overthinking."

      I disagree with this. Quite frankly, I would have to overthink to interpret it the way the problemsetter did. I'll continue to stand by my claims of the author's interpretation being incorrect given that none of my points have been addressed.

      Maybe this was a result of a lack of testers(nobody's been mentioned on this post)?

      awoo, for future edu rounds, could you at least get more testers(or even people to read over the problem statements)?

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

    IMO, if we make this round unrated, it'll be unfair for people performed well.

    Problem A itself is mainly correct, with a minor(maybe?) mistake

    The word "simultaneously" is not specially marked with bold,that means we don't have to pay much attention to it,although it's a bit misleading.

    However, since the sample explanation is added soon after the contest started, it would be clear what "simultaneously" really means.

    Hope there'll be less confusing statement like this in the future

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

Can someone explain the first test case of Div2E?

What are the 6 arrangements? Isn't this a valid arrangement?

x..
.x.
.x.

x are the rooks, . is an empty cell.

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

I'm new to educational rounds! My solution to B problem was accepted during the contest but now its gone red and i wasn't rewarded for that Question and now its again green. Can anyone explain why so

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

    your solution was incorrect, someone found test where it fails :(

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

    If you made a failed submission for a problem,then the problem will become red during systest.

    But don't worry, once your solution passed the systest, it will become green again.

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

Is Problem F the real-life application of Problem D?

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

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

78261468 can someone please provide a test case where this code fails

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

when will ratings update??....i am eager to see my new rating

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

The educationals have never been friendly to me :-(

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

can anyone please help me what's wrong in my code for C,I checked for numbers of type k*lcm(a,b)+max(a,b) which are in range. https://codeforces.com/contest/1342/submission/78265046

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

Can anyone understands me the div2D. Mainly i don't understand the test 2 first line output . Why that is 2.plz anyone explain. Sorry for poor english.

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

    2 means minimum number of test cases you must have,to satisfy the given condition. And next there will be two line describing those test cases.

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

    In case you don't understand the question: You can assume the problems like this,

    • Given N items with weight [1,K]

    • Given C1,C2,..,Ck which means the item with weight >= K in 1 packet must be at most Ck

    • The task is to separate the items so that the rules no.2 in fulfilled with the number of packets as minimum as possible

    Test case 2:

    6 10

    5 8 1 10 8 7

    6 6 4 4 3 2 2 2 1 1

    N=6 K=10

    Items = {1,5,8,8,7,10}

    C = {6,6,4,4,3,2,2,2,1,1}

    Answer:

    You can separate the items into {10,8,1} and {8,5,7} or {10,7,5,1} and {8,8} or even {10,8,5,1} and {8,7}.

    You can check my solution : https://codeforces.com/contest/1342/submission/78196440 (it's kind a mess tho)

    In overall, my greedy solution goes with:

    -Put the highest weight as the priority

    -While it is available to put them in the packet 1, put 'em. else go to packet 2 and so on.

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

      EDIT:

      For every weight, while it is available to put them in the packet 1, put 'em. else go to packet 2 and so on.

»
4 years ago, # |
  Vote: I like it -15 Vote: I do not like it

System sent me a letter,it said that my code is similar to another person, so I write this comment. I solved 1342D quickly, and then, I had had been thinking about how to solve problem E, but my math ability is not very good, so I can't solve it. train2004 is my friend, all right. After contest, we talked a lot. His opinion is same to me, but I didn't see his code. I haven't thought about the case now. Through this experience, I konw that I should add some personal codes to try to avoid these cases. Thanks for reminding me, I'll notice these by now! Thanks!

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

Nice problems! Everytime I can learn a lot from educational round! Thinks a lot to codeforces!

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

I found out that I would be more likely to drop rating in edu-rounds.

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

Where is the editorial?

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

I have done problem D using greedy approach and I think time complexity is (n+k)log(n+k), but still I am getting TLE on test 16 78266716???

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

I seen all have almost same approach for Problem C. Can anyone tell me how we reached to that approach ? I mean what topic knowledge is required to think for that approach?

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

    just print x% a % b and x % b % a and same or not, for the given example a=4,b=6 and choose like l=1, r=100 you can see the pattern and you can conclude you need the lcm, then it's basic stuff from here.

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

After this contest,system sent me a message:"Your solution 78191609 for the problem 1342D significantly coincides with solutions 78180150".However,I wrote my code by myself,and our code are different.Even if some part looks same,but that is a very common way for solving greedy+priority_queue problems.What can I do? Sorry for poor english.

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

    Ask awoo or MikeMirzayanov for help

    Sorry but I have to say... you're so "lucky"

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

    awoo Could you please check this?Thanks.

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

      No offense but code looks very similar.

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

        Well,if you think this problem like this"greedy is ok.if I can add this m[i] into the smallest set,then do it;otherwise,make a new set",then write code.It's easy to look like others who have the same idea.(And we are classmates,so we have similar code style...)
        But after all,our code really looks very similar.
        So I think I should change my code style to avoid this situation next time. Sorry for my poor english.

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

Why all task were on one topic?

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

I don't know how to solve problem E. Could you help me?

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

Why not to post editorials just after the contest ends (learn from atcoder, codechef ) ,if problems and solutions are already prepared ,then why let others wait for so long ... I am checking after every hour from yesterday for editorials but they are still not posted...

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

    This seems to be limited to Educational rounds and Div. 3s, (most of) the other problem writers seem to have it ready straight away and it's pretty disappointing when it isnt ready hours afterwards.

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

why the editorial is still not uploaded ? (i need hints for problem D)

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Hello, Orange!

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

Can anyone help with TL on problem F?) https://codeforces.com/contest/1342/submission/78328093

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

I've solved it