SleepyShashwat's blog

Codeforces Round #663 (Div. 2)
By SleepyShashwat, history, 4 years ago, In English

Henlo Codeforces! ^_^

I invite you to participate in Codeforces Round #663 (Div.2) taking place on Aug/09/2020 17:35 (Moscow time). The round is rated for users rated less than 2100, while other users can participate non-competitively.

The round features five problems, and you have 2 hours to solve them. There may, or may not, be an interactive problem; regardless, you should know how to deal with them.

I would, now, like to thank–

Please do not mind the long list of testers (I had to write code to tag everyone here) since the problem set changed significantly after the first round of testing.

We will announce the scoring distribution shortly. The scoring distribution is 500–750–1250–2000–2750.

Good luck, and stay safe!

UPD: Editorial

Here are video editorials by BRCode:

UPD2: Finally, congratulations to the winners!

Div. 1:

  1. tmwilliamlin168
  2. risujiroh
  3. fanache99
  4. LayCurse
  5. Sugar_fan

Div. 2:

  1. 00000010100001100111
  2. PouyaNavid
  3. 420iq
  4. I_want_2400
  5. silxi
  • Vote: I like it
  • +1305
  • Vote: I do not like it

Comments Comments (353)
| Write comment?
»
4 years ago, # |
  Vote: I like it +148 Vote: I do not like it

As a tester I think people will like this round because of interesting problems,diverse topics and short statements

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

    Also (as a tester) wants contribution :)

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

    thanks, I see a lot of orange here in the group.BTW what's polygon, I read it in every announcement MikeMirzayanov for Codeforces and Polygon platforms– Polygon is truly remarkable!

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

      Polygon in basically the platform for creation of programming contest problems. It also supports problem statement writing, test data preparing, model solutions, judging and automatic validation.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it -16 Vote: I do not like it

    how can i increase my rating

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

    Just after reading SleepyShashwat I am feeling sleepy

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

As a tester... Damn there's so many of us!

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

OMG!!! another "as a tester" comments "/

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

    But we can't disagree many of them gives us some useful information about the round.

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

      blobugh , I understand the first part of your username butt why do you like 1373

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

Which ponies are we helping this time?

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

Omg Indian round! So excited

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

*insert cringe proud indian comment here *

→ Reply
»
4 years ago, # |
  Vote: I like it -32 Vote: I do not like it

I hope, we don't have to help Ponies, in this contest, unlike Previous Contest! :|

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

Hope the problem statements are made while you are not sleepy.

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

    Well he was, but I made sure they are alright ;)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +174 Vote: I do not like it

Memes/images should be posted in spoiler!

Indians on CF
As a tester...
How to feign consumer satisfaction to investors
Anton rounds

Disclaimer: The memes aren't specifically for this round, that's for you to decide :) I liked it a lot as a tester.

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

So we'll have video editorials too this time?

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

orz

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

As a participant, all we want is short and clear statement. Hope we won't get disappointed :)

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

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

Props for the 3b1b style video editorials! Sounds really cool, will definitely watch.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
→ Reply
»
4 years ago, # |
  Vote: I like it +30 Vote: I do not like it

As a pony , I hope I'll not find any problem about ponies :(

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -50 Vote: I do not like it

Don't downvote sir

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

SleepyShashwat, AwakeAnay, AsleepAdhyyan, and RestingRajarshi.
Coincidence!? I think not. ;)

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

BRCode for making 3b1b-style video editorials of the problems!

YouTubers who make video editorials after the contest
→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I'm wondering why almost half of the recent contests, including this one, contain $$$5$$$ problems, but not $$$6$$$.

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

    As a tester you will know why 5 is enough :)

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

      I won't be wondering any more if I can have a chance to be a tester

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

    Because , by excluding 1 problem from 5 contests ,they can create a new one.

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

Is this the quartet of last year's IOI from India?

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

"Henlo" ?

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

Hopefully the ponies are grazing grass instead of playing chess coloring games with each other.

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

Happy to see an Indian round Again. :D

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Not as a tester I hope you good luck!

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

Wait did I read it right that there are vedio editorials ? Cool.

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

How many testers do you need?
-YES!
How many pony stories do you need?
-NO!

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

I hope this round will not test our English comprehension skills.

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

Why is every div2 round having 5 problems now? Is making 6 problems too hard or are you sleepy while writing problems as well?

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

    I prefer 5 problem rounds. They have better problems.

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

(I had to write code to tag everyone here) : How does one write code to tag people? O.o

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

Hope the statements are not sleepy.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

As a tester i want to say that the contest is shit!!!! Thankfully i am not participating in this officially!! sighs: All the specialists brace yourself!!

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -19 Vote: I do not like it

    Deleted:(

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

    Do you mean advanced algorithms as you mention specialists are going to have a hard time? or are you referring to math tricky questions? or ADHOCs? 0_0

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

Typo in spelling of Hello Codeforces Please change Henlo --> Hello

→ Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

Although your Indian English is kinda weird, but the 3B1B-style video is so fantastic!

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

Why am I getting a feeling that this is going to be a MathForces round? I hope it is not though! :P

Also antontrygubO_o as a coordinator (Yay! :D)

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

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

Henlo Codeforces! ^_^ I think here must be "Hello" ^_^

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

    No, they didn't misspell Henlo is a cute puppy language style for saying Hello.

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

Another contest!! As a regular contestant, I need a break :'(

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

As a contestant, I want rounds with aryanc403 as the author

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

I really starts enjoying memes here...

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

Thanks , Codeforces!!!

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

author, how could you misspell the word ,,Hello''? i want to cry((

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

    Henlo is an internet term used for greeting others. It is not misspelt :')

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

    They didn't misspell it. It is a cute puppy language style for saying Hello.

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

Did any tester test anything with Python? Did someone spend the 10 minutes checking if the standrad solution in Python doesn't get TLE or too much memory?

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

    Advise as a community member, You should never worry about TL issues in an Anton coordinated round.

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

Hope the statements are clear. I don't want to walk around the maze :)))

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

soo, if i utterly fail to do the questions then what will happen? (my rank is 0 , will to in minus or increase if yes then how?!

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

    If you don't have a submission then rating will be unchanged.

    If you make at least one submission but solve 0 then rating may increase for new users.

    Check Here for details.

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

Thanks , Codeforces!!!

→ Reply
»
4 years ago, # |
  Vote: I like it -21 Vote: I do not like it

As a tester I think people will like this round because of interesting problems,diverse topics and short statements. Thanks, Codeforces!!!

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

SleepyShashwat please don't sleep during the going contest

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

Happy to see Indian School Students doing great on Codeforces and other CP Platforms! I wish, I also knew about CP while I was in School. Indian Students need to learn that "Apart from IIT JEE, there is also a world called CP". All the best SleepyShashwat for your future endeavours!

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

    Awwwwwwwww, Were you not able to clear JEE, you poor soul

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 23   Vote: I like it +24 Vote: I do not like it

      Poor Soul thinking that only a JEE Failure would write that statement. I think you are in the First Year of an IIT or you are not an IITian. Only some First Yearites(Fachas) at IITs have this attitude that they have cleared JEE and won the world OR this attitude is shown by Butt Hurts who couldn't clear JEE Advanced!

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it -40 Vote: I do not like it

        What if i say i am in third year in an IIT ? What shitty explanation will you give then ?

        In my college "fachas" or first years, whom you are saying shit for no reason, are better than you in CP.

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

          I have seen people mention IITJEE many times before . So , does this university conduct some kind of computer science competition like I.O.I. , because I have seen it quite a few times like on this blog , Indian contest blog , cheater blogs and some ICPC blogs .

          Its a rare thing for universities getting mentioned so it kind of made me curious

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

        The only reason i am offending you is you tried to offend those students who busted their ass in getting a f***** IIT after like 2 years of rigorous studying ( maybe 4 years for some ) and you are into CP for like one year and still nowhere with CP ( to be honest ).

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

          I am also in the third year. And to be honest, you can check my submissions, I only gave contests till December last year. Many first years are better than me in my college also. They are Masters and it happens in all IITs I guess. I know I am nowhere in CP and it doesn't even matter to me. And what I have tried to say is there is a world apart from JEE also- for those who couldn't clear that! We also do CP only to get Jobs in MNCs and they also! I also spent 2 years in rigorous studies and I know that situation. And for your kind info, you are wrong even at judging my "Special and Reserved Community" LOL!!! It is just that some need more time doing CP some don't need that. Some do CP continuously and daily while some don't practice that much and I belong to the second one. I don't practice that much because everyone has different priorities. CP is a backup for some to enter the software/IT sector. They may want to do something else like Management, Civil Services, etc. And there are many such IDs on Codeforces- belonging to IITians, a general category and Pupil/Specialist. So, keeping all factors in mind stop judging people! And for your kind information, study for Internships rather than trying to offend me! And I didn't call first years SHIT. It was you who misinterpreted it! I just said they have that kind of feeling in mind in first years. But second-year onwards they know the situation :P.

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

      or he might have cleared JEE

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

      I cleared JEE but wish I'd rather got to know about CP back in school. I have been good at programming since I was in high school but thanks to the JEE culture in India I never got to know about cp.

      Whats worse, I got to know about cp only in my third year and I have only 1 year in my college life left now. Honestly if i could go back in time, I would tell my earlier self to do CP rather than jee.

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

    What is IIT JEE ? Is it something on the lines of web development or something like that

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

      it is the exam conducted to select students for studying in the most prestigious colleges of india (IIT). and no, u need to learn physics, chemistry and maths to crack the exam and secure the highest ranks possible to take up computer science(which is one of the many streams taught in an IIT).

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

        So are students not aware about cp or they choose not to pursue it

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

          I feel very sorry to say that but the education system in India is totally weird. I hear the word "CP" just some months before(after going to college). When we were in standard till 10. We have absolutely zero knowledge about programming(and we taught in school is totally theoretically especially in CBSE Board(I am from CBSE). In countries like Russia, people start programming in a very early age. They have much more knowledge than us. (Prooving my above statement, Currently there are only 7 red coders from India despite having the largest number of active members in Codeforces(almost double than any country).I am from India, and I really feel for it!!!

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

            you mean that we have not started cp early, so we are not talented as other country's people?

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

              Yes, this is the only reason I can think of!

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

Thank you.

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

Score Distribution?

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

where is editorial for this round?

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

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

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

very excited for round.

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

Very excited for the indian round :)

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

woweeeeeeeeee! 3Blue1Brown style editorials.

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

Half of the coders are giving Goldman Sachs aptitude test now lol

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

    Is it necessary to post it here ?

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

      Just felt like posting man. Everyone posts irrelevant memes, so why not this. Anyways, I apologise I said something wrong.

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

        That's true about irrelevant meme. But what I am saying here is we should try to avoid posting irrelevant stuff here. Is someone is committing some mistake, it doesn't mean that we should also right ?

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

I can't understand what 'even length square sub-matrix' means in problem D.

Does it mean a sub-matrix with even width and even height?

Thanks

@SleepyShashwat

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

    A binary matrix is called good if every even length square sub-matrix has an odd number of ones.

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

    It is described in the sample explanation below the testcases

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

Problem B was too easy , should have been a little harder...

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

After solving A and B what should be the best thing to do?

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

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

Me after solving A and B :-) after-AB

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

Permutation lover SleepyShashwat

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

From today, I started loving permutations because no one knows how you can play with permutations except the master SleepyShashwat. Truly a good and well implementation based round. Only DS can help :)

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

The problem statements were really nice :) But the difficulty could have been a bit higher for C.

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

Determine if the contest is good?

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

    If Tx is the number of people solved task x, then the contest is good if Tj < Ti for any j > i

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

      For now, 13045 — 12108 — 5115 — 1169 — 61.

      • Accepted!
      → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it

My JEE notes help me in solving question C

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

Now this is what I call a Contest. loved it. Kudos to the author.

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

Nice problem set! A good round after a long time :)

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

Waiting for the end of the contest to start discussing the task E

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

    PATH: if diameter of graph >= (n+1)/2 ^) PAIRING: if otherwise, but how to construct?

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

      Do dfs. In dfs tree if there is a path from root to any leaf with length >= (n+1)/2 we have solution PATH. Otherwise we pair nodes at same depth/level in dfs tree(because in worst case we won't pair only one node at some depth and from first check depth of the tree < (n+1)/2 so we will lose at most n/2 nodes during pairing which is valid).

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

    Root at any node. Find a dfs Tree.
    If the height is >=N/2 you have a path. Otherwise pair nodes on the same height.

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

Nice contest, too bad I wasn't concentrated enough :(

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +33 Vote: I do not like it

2 minutes of silence for these people.

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

Solution of C:
https://oeis.org/A059204

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

    :( I recognized how to solve it that permutation must have at least one dip but was not able to generalize the series. Thanks for OEIS link.

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

Pretest 6 For Problem C ????

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

Such a nice D!

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

What's the pretest 3 for problem D

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

I liked the problemset.

How to solve D? (I had understood that for n>=4 and m>=4 the answer is -1, but I don't understand what to do next).

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

    Since $$$n \leq 4$$$ you can do dp[i][mask] in O($$$m * (2^{n})^2$$$)

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

      "mask" means the type of the square?

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

      oh, I should have thought about dp :( nice problem but.

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

      n<=m so you don't need the min and max functions.

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

        Thanks, I guess I need to read problem statements more carefully.

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

        Oof, wasted 10 mins altering it to work in the case where m < 4 and n >= 4 without seeing this.

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

    everybody got that part but man how should we place greedily anyone ??

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

      I don't think that it's possible to do it greedily.

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

        that's why I wasted a lot of time next time I will make sure when dp is possible just apply it.

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

how to solve C please help??///

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

    n!-2^(n-1) is the answer.

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

      why?

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

        number of permutations is n!. And you have to count how many permutation of the form (2,1,3) do you have because that gives you a cycle between 1,2,3. (and 3,1,2 too). The permutations which are not from this type is 1,2,..n (increases) and after n decreases. And that number is 2^(n-1).

        (with 2,1,3 i mean some v[i-1] > v[i] < v[i+1] not just 2,1,3)

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

          Didn't the question asked to find the total permutations of length given n? For n=4, is [4, 2, 3, 1] having length cycle of length 4?

          As per the definition given, vi and vi+1 share an edge for all i (1≤i<k), and v1 and vk share an edge. v1 to vk edge is only possible either of 2 cases 1. n-1 at position and n is at last position 2. n is at first position and n-1 is at last position then only we can form a cycle of length n right? Correct me if I am wrong somewhere.

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

            I agree but i can`t see your point. 4,2,3,1 has a cycle of length 3 so i don't care if has a cycle of length 4.

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

              Sorry I misinterpreted the question.

              From the statement, "Given n, find the number of cyclic permutations of length n. Since the number may be very large, output it modulo 109+7.". I thought, we need to find permutations whose cycle length is n.

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

        Total permutations = n! Permutations without cycles = 2^(n-1) I'll explain how I got 2^(n-1): For any permutation, if there is no cycle in it then it should follow this logic: 1)For any i,(1<=i<n) numbers i+1,i+2,i+3,... n should lie on the same side, if not then the permutation contains cycle. Then start calculating the ways by following this logic. Eg: for n = 4 You can put 1 in either of the ends.(because all other numbers should be on same side of 1) Then 2 possibilities: 1--- ---1 (you have to fill blankns with 2,3,4) Now, 3&4 should be on same side of 2, so, our possibilities are now 12-- 1--2 2--1 --21 .Recursively this gives 2^n-1 ways.

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

    Use simple permutations and combinations and the principle of inclusion and exclusion :)

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

A very nice contest!! Problem statements were short and to the point.

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

People with WA/RTE/TLE on A. Care to explain your soln?
Congrats Beta_R for getting hacked on A twice.

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

how to solve D? I found it really hard to find answer for min(n, m) = 3 because there were too many states

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

    Yeah I also got stuck in that case. Waiting for the editorial!!

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

    there are only 4 states. 1)from {(000), (111)}(consider which of these two require min change) to {(010), (101)} and visa-versa. 2)from {(100), (011)} to {(001), (110)} and visa-versa. check this

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

Has the core idea behind C appeared in a contest in the last year or so? I remember solving a problem which had the same idea (sequence must increase then decrease, find number of ways) not too long ago.

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

3blue1brown styled Video Editorials:

Problem A+B: https://www.youtube.com/watch?v=KJVigs8w-gg

Problem C: https://www.youtube.com/watch?v=vWHUmtiPRQw

Problem D: https://www.youtube.com/watch?v=kspzot42-uI

Problem E: https://www.youtube.com/watch?v=y62jjZev3pY

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

problem D:

if the matrix is 4 by 4 or greater size answer is -1. and for smaller matrixes, we need to get the answer?

where I went wrong please help me?

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

    so far so correct but real question starts after that if you don't want to brute force every case.

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

can we solve D without brute-forcing every case separately?

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

    I think we can XOR the bits (0s and 1s) and come up with a simple approach for dp. I couldn't do it in time though.

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

    if(n>=4) must -1 so we care of n<=3

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

      What should be the states for n==3 ?I couldn't figure it out.

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

        all 1 <= e <=m , arr[0][e] * 4 + arr[1][e] * 2 + arr[2][e] can make the bits. then we can use dp to solve the problem. build the array dp[length][8]

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

    I brute forced for n = 6 and m = 3 and my pc crashed.

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

Problem D: Am I right in thinking that if the no. of 1s in every 2X2 matrix is odd then no. of 1s in every 4X4 matrix will be even hence answer is -1 for all the matrices with n and m >=4? OR am I missing something. If I'm right, then how to go further?

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

    No that's correct, but the hard part is doing the dp for the min(n,m)=2/3 cases

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Shame on me for not reading the problem properly. I didn't read that only 'R' and 'D' were valid directions for problem B, so I implemented something way more complicated to deal with all 4 directions cardinal directions XD.

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

    Maybe this will help you fell better but you are not the only one :D

    I started implementing the solution with all directions, after about 10 minutes I saw that there was more than 2K Accepted solutions so I knew something was wrong, read the full statement again and solved it in 2 minutes :(

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

the intresting fact about this contest was that nobody knew the proof for problem C but everyone solved it :))))

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

    I saw that you can have a cycle iff you have a "dip" in the sequence. 95% sure that that's correct, so then I tried to count every permutation without a dip and saw that for every n, it was double the previous one. You're right, no actual proof though!

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

      The permutations that don't work are ascending and then descending. The number of them is the sum of (n-1) choose k from k=0 to n-1, and it's well known that it's equal to 2^(n-1). So the answer is n!-2^(n-1).

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

        One way you can see why it's the sum of n-1 choose k from k=0 to n-1 is that you have a 1-1 correspondence between subsets of {1,...,n-1} and a not good permutation because you place all the numbers in your chosen subset to the left of n and then the remaining to the right of n (there is only one way to arrange these two subsets). Or you can just think of it as there being two choices for each number, being on the left of n or the right of n.

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

    Non-valid permutations are the one which first increases then decreases, rest all are valid, and number of such permutaions are $$$2 ^ $$$ $$$(n - 1)$$$. So ans is $$$n!$$$ $$$-$$$ $$$2 ^ $$$ $$$(n - 1)$$$

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

Problem C was really awesome and the statements were also quite perfect...

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

Isn't the answer to C is fact(n) - 2^(n-1) ???

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

Nice problemset. I think D can be done by bitmask dp, correct me if I am wrong.

→ Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it
How to determine if a round is good
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Really nice contest! D was the first dp problem I've done in contest in a while.

Solution for D: If n>=4, the answer is -1. To see this, note that each 4x4 matrix is broken up into 4 2x2 submatrices that are disjoint. If the sum in each of these is odd, then the sum in the 4x4 matrix should be even, which is a contradiction.

Now, we do cases on n=1 to n=3.

For n=1, there are no even sub squares, so the answer is 0.

For n=2, each column alternates between a sum of 1 or 0 mod 2, so theres only two cases to check here (whether the first row has sum 0 mod 2 or 1 mod 2), and that can be done in O(m).

For n=3, you can use dp. Let dp[i][j] be minimum number of moves needed to get the first i columns to satisfy the problem constraints, with the ith row equal to j in binary (so, for example, if j=5, then the ith row would be 101). Then, dp[i][j] = min(dp[i][j],dp[i-1][k]+add), where k ranges from 0 to 8 and is the state of the previous row, and add is the number of moves to change the grid ith row to j in binary (so it would be 2 if the ith row was 000 and j=5 = 101 in binary). Answer is min(dp[m-1][j]) from j=0 to 7, and time complexity is O(m*4^n), but n=3, so it passes. There might be a more efficient solution.

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

    I think we can construct 4*3 matrix. I have constructed a 4*3 matrix in my copy?

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

Thanks for such a nice contest!

  • Short and concise, formal statements
  • Good problems
  • Good video Editorials
  • Balanced Contest

We want more such contests :)

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

E is a nice problem

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

Idk if I'm dumb, was anybody else confused with the "Cycle of length n", for n = 4 there weren't 16 cycle of length 4. Although there were 16 perms. which have cycle.

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

My solution for problem C failed on pretest 6 using C++. Later, I changed it to python and it worked. Can someone explain why?

(Did n!-2^(n-1))

C++: https://codeforces.net/contest/1391/submission/89438077 changed to: https://codeforces.net/contest/1391/submission/89443077

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

Nice contest, math lovers for the win. I go back to Div4.

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

How to calculate modulo inverse efficiently ?

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

    Calculate $$$n^{mod-2}$$$ (if $$$mod$$$ is prime)

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

      Only if it's a prime (usually it is).
      If it's not you use extended euclidean (I didn't mean to counter what you told him, but imagine he will be in a contest in the future and he needs inverse modulo not a prime, he will want to kill himself XD)

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

        Thanks for correcting my mistake XD I missed that.

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

          Did you solve problem C with it? I tried to solve it using the binomial coefficient but I had problems with dividing and keeping it modulo. Is this modulo inverse commutative for multiplication, it doesn't matter in which order you multiply?

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

          It looks like it works, but was just a bit too slow (in Java) using modular exponentiation. Thanks, am going to look a bit more into this, looks useful.

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

            I optimised it a bit and it barely passed.

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

              I used BigInteger class at the time of the contest to calculate it but the method is too slow

              → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

My solution to C — tn = (n-2)(n-1)!+2*tn-1

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

Problem C makes you fall in love with CP all over again. Concise and to the point statements. Great round :)

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

C is in oeis but i cant just implement it.

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

Excellent contest; I really enjoyed solving the problems! Here's my screencast and solutions to everything if you're waiting for the editorial.

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

    Well particularly, I was waiting for your editorial. Nice job as always.

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

    You're videos have helped me a lot. Love the way you talk through your thinking process even during the contest. Please Don't stop doing this :)

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

Very Nice, It looks like an educational rounds format (i.e: the statements are formal)

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

For a moment while reading C , I thought the edges are directed and wasted like 10 min on so, But still I think that this version would be interesting one I would really appreciate ideas on this version of question if solvable

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

Another high quality contest. Codeforces back in form.

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

Damn. In problem D I figured out very quickly that n<=3, but then I thought it's greedy after that, and now I see people solved that part with DP! And now it seems so obvious I want to bloody kill myself :<

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

My opinion might be unpopular but I think the formula wasn't too hard to guess.. I came up after an hour into the contest but still I spent 15 mins trying to prove it.. and I couldn't prove it.

It would be better if the formula for the problem is harder to guess from samples else it beats the purpose of the problem...

I mean for problem C.

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

For problem A, How can any permutation work?

Like for n=5, 1,2,3,4,5 can be called as any permutation but does not work for index 1 to 2.

2^3 = 1 whereas length of the array is 2.

I just could not grasp problem A.

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

    It's not XOR it's OR

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

    It's OR not XOR. Man I feel do bad for you if you thought it's XOR!

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

Can any bide tell whats wrong with my d solution?

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

    Most probably, the relation for dp[j][4].

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

      OOO thanx! i will upvote you with all of my acs : )

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        Spoiler
        → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem C was really fun, and in general the whole round was great! I loved reading and thinking about all the problems!

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

    Can you please tell how did you approach C?`` Like did you see a pattern or used oeis?? I want to know how good coders approach such problems

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

      Well, first I thought about what happens with the ID permutation (i.e 1 2 3 4 5..), and I saw that there are no cycles. Immediately I concluded that that the reversed also has no cycles (5 4 3 2 1). Then I tried to make one inversion, such as 1 2 4 3 5, and saw there is a cycle and then I thought that maybe any inversion might mean a there is a cycle, but then I tried to put the max in the middle, and my first example was 1 2 5 4 3. I saw it has no cycle, and that's because 5 has no one larger than him anywhere. Then I thought I had it, I checked 1 2 5 3 4 to see it has a cycle, and of course it did. (because of 5 3 4).
      My conclusion was that any "mountain" structure has no cycles, mountain means that for i < j a point p_i < p_(i+1) and for i >= j, p_i > p(i+1).
      I proved it to myself briefly by saying that if it isn't a mountain, then there is a "Valley", and a valley is just a triplet (a,b,c) where a > b < c (for example 5 3 4), and that creates a cycle!

      So then it became counting the number of "mountain" permutations. The peak of the mountain must be n (the max value in the permutation), and if you choose a subset of elements to be on its left (and the rest on its right), there is only one way to place them — non-decreasing on the left of him, and non-increasing on the right of him.
      So you just need to choose the subset of elements to the left of 'n' out of the n-1 remaining numbers. The number of different subsets of n-1 numbers is 2**(n-1).

      And the solution is (n! — 2**(n-1)). Of course you calculate both those value modulo P through out, and perform the modulo operation after the subtraction.

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

Excited for the 3b1b style video editorials

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

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

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

the problems are very good!

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

Solved div2C for first time but doesn't feel like an achievement because formula was too intuitive I think.But still enjoyed the contest

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

    what was intutive about that?

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

      Sorry if I hurt anybody. I was just saying I don't know how I came up with it and after reading the comments, I thought that the formula was pretty obvious:)

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

    Congratulations! Not that intuitive. The problem was solved by less than 1/3 of the participants. And there were over 13,000 participants.

    What this means is that you are improving! Treat yourself well!

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

I really gotta say, this round was FABULOUS.

  1. Super interesting and formal statements.
  2. No speedforces: great problem D.
  3. Adrenalin of solving problem D in the last moment :P

Hands down, one of the best rounds I have seen upto now (the only round that comes close is AshishGup's #651)

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

Problem C is not that much intuitive. Permutation should increase then decrease to not make any cycle. ex) n=8 1 3 6 7 8(top) 5 4 2

Except top element, we can choose any subset of [1~7] for increasing part, then decreasing part is automatically decided. If we choose [1, 4, 5] then one permutation is made : [1, 4, 5], [8], [7, 6, 3, 2] so 2^(n-1).

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

    Just watched the video, and did read the tutorial severeal times. It is unclear why increase, then decrease.

    I assumed that any triple with the smallest number in the middle is enough to form a cycle.

    So, why is this?

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

      Assume there is last two values x and y which were previously decided and now I put some z next to y.

      [case1: x < y] i) z < x < y ii) x < z < y iii) x < y < z

      [case2: x > y] i) z > x > y ii) x > z > y iii) x > y > z

      Except for case2-(i, ii) no cycle is made. So once previous values started to decrease, then we cannot make it increase again.

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

      If you create a permutation that increases first till you reach the largest element and then add all the remaining elements that form a decreasing sequence, it will mean that there is no cycle as there is no triple with smallest element in the middle. You can calculate the number of such permutations (which increase first, and then decrease) and then subtract the total from factorial(n) to give you the correct answer.

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

        That is not what he's asking. He's asking how you go from the intuition that we can't have a triplet (a, b, c) such that b < a and b < c, to the intuition that the array must be increasing, then decreasing.

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

          Nah, in fact, it was unclear to me what the triple has to do with increasing/decreasing. And I did not notice that the number of increase/decrease is subtracted.

          I tried for like an hour to calculate the number of triples, not the number of inc/dec sequences.

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

            How do you go from the triplet intuition to increasing/decreasing? That's still unclear to me.

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

              A triplet counts if the middle element is the smallest.

              In a sequence which is first increasing, then decreasing there is simply no such triple. No element where left and right would exist a bigger one.

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

                I get that increasing/decreasing -> no bad triplet.

                What I don't get is how no bad triplet -> increasing/decreasing.

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

                  Maybe you did read the terms local maximum and local miminum.

                  The increasing/decreasing sequence has exactly one local maximum, and no local minimum. If you change that fact, (by swapping two elements or the like), then you create such a triple with the smallest number in the middle. This is, because then there is a local minimum.

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

        I think I understood, thanks.

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

Please join me in congratulating SleepyShashwat and the numerous team on a great problemset and contest!

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

Why did the round not allow registrations after the contest began. In general why is it ever beneficial to have this restriction? The contest blog didn't even mention if it was so.

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

In D, Can anyone please find mistake in my code I tried it by generating all possible matrices of 0s and 1s but it giving wrong answer for all m,n<=4

https://codeforces.net/contest/1391/submission/89455694

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

Very good contest, thanks to the authors. The length of the question is also quite appropriate, neither long nor short. After three consecutive unsatisfactory performances, I finally played a bit normally today. After quickly solving a and b, I found that c is not the type I am good at, and I have no idea for the time being. I made a bold decision.skipping c and slove d first. It is not difficult to think about the algorithm ofd, but there are many details in the implementation.(I did not notice the constraint of n<=m, so I copied a part of the code），After two wrong attempts, I finally passed d at 01:50. Looking back at c, I didn’t feel very difficult.But Before I found a conclusion, the game was over. I don't regret slove D first, because if I slove C first, it is likely to pass before the end of the game, or simply get stuck on C. Hope to play better next time.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Great problems :)

SleepyShashwat

And thanks for quick editorials! Will be looking forward for more Indian CF contests ;-)

→ Reply
»
4 years ago, # |
← Rev. 6   Vote: I like it -34 Vote: I do not like it

/*Deleted*/

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

One of the most elegant contests ever. Loved it.

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

I really enjoy these interesting problems!Great contest!:D

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

Kudos to SleepyShashwat for an excellent round with some really nice problems!

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

Very cool contest :)

Here's my video solutions for all problems + very funny moment at the end.

https://youtu.be/c3mjIQR902k

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

My screencast, where you can watch me die on E (includes solutions for A-D)

(quality will be better when youtube processes it)

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

Nice Contest! .I did a dumb act in c by calc. n-1c0.... so on by fermat thrm .and i cracked iit jee maths how?

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

No offence, but it is so strange to me that most people in the comments prefer this to the ponies.

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

Thanks BRCode for such high quality editorial. I pretty much appreciate to your hard work. By the way, are those videos generated by manim?

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

    Thanks! Yep, the animations are made using Manim

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

To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!

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

Thanks for this cool round! I really enjoyed the problemset and +193 rating as well :)

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

My solution to problem C: Use the following recursive formula: a_n = 2*a_(n-1) + (n-2)*(n-1)!. 2*a_(n-1) means that '1' is placed in index 0 or index n-1. (n-2)*(n-1)! means that '1' is placed in the other middle indexes.

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

    I thought of the same: a_n = a_{n-1} * n + ((n-1)!-a_{n-1})*(n-2). But I don't have a explanation for the (n-2) factor. My thought process was if a sequence of len "n-1" has cycles I can insert n at any point and it will still have a cycle, (a_{n-1} * n), if not ((n-1)!-a_{n-1}, don't have cycles) there is (n-2) ways of inserting n and creating a cycle in a sequence that doesn't already have one? That seems to hold but I don't know why. How did you arrive at that relation?

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

      Nvm, there is (n-2) ways of turning a sequence that has no cycles in a sequence that has cycles because every sequence that has no cycles is bitonic and we have 2 ways of inserting (n+1) and still be bitonic, just before the element with value "n" or just after.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Why was there no need to check for cycles in problem B to get AC, for e.g.

RL... ...... ..... ..... ......C wont reach C if we start at the cell 'R'. Then why didnt we need to check for cycles? EDIT: I just realised there were no L or U in the grid. Now i just feel dumb ;-;

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

    Wait, what? There are only two types of cells in this problem — 'R' and 'D'. Why did you use 'L'?? Upd: I see you got it :)

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

Thanks...the problem E helps me review some basic properties of graph traversal...

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

One of my favorite contests!

→ Reply
»
4 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Sorry, I was disqualified for a match with another account, the fact that I'm from Belarus and we during the election, very poor Internet,I was afraid to write from his account, and wrote another,my teacher, and he serves,and I sabanilla for cheating, though he and the code is my main and I passed more, please understand because we have with the Internet is very difficult, and disconnect in the middle of the competition not hunting was a big minus would be. Please understand, this is all because of the situation in the country, if this did not happen, everything would be as usual. If this can be considered fair, you can reset that account to zero participation, and return the rating to this one.

P.S. prove that my account is not a problem

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

explicit,novel and diverse round it is. It is worthy that the round will get more upvotes after finished.

→ Reply