MrPaul_TUser's blog

By MrPaul_TUser, 9 days ago, translation, In English

Hello, Codeforces!

I'm glad to invite you to amazing (we've tried to make it such) Codeforces Round #734 (Div. 3) which will start on Jul/23/2021 17:35 (Moscow time). This round is the first "trial of the pen" of me (MrPaul_TUser) and it seems to be hard to make it alone — a significant contribution was made by MikeMirzayanov, BledDest and DK318.

The round contains 6-7 problems. The difficulties of the problems are expected to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

  • take part in at least two rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to WolfBlue, BlueDiamond, harlequen, -is-this-fft-, le.mur, Bench0310, Reiva5, Golovanov399 and Sho for testing the round and improving tasks.

Good luck and have fun!

UPD

Editorial

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

»
9 days ago, # |
  Vote: I like it +47 Vote: I do not like it

First time being unofficial :)

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

    Reached 1600 yesterday...

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

    Why? This round will be rated for you since your rating is less than 1900.

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

      No, its rated up to 1600, not above.

      "However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially."

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

        So... then what does "only the trusted participants of the third division will be included in the official standings table .... do not have a point of 1900 or higher in the rating." mean?

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

          That means that those people will be included in the official standing table.

          In conclusion that means, not everybody in the official standing table will be rated.

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

            Ah, okay, thanks.

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

              If you want to be rated in Div3 you can refer to my rating graph how to do that ;)

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

    There are many youtube channels which produce solution code during the contest time it is strictly prohabbited plz report these channels

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

    hey! i saw your profile and i'm pretty curious as to how did you become expert in such a small timespan, if possible could you share some tips, tricks or advises? and like what all topics did you practice to reach where you are right now?

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

      I was training kind of hard maybe :) when I was newbie I trained 1600 difficulty problems until I become pupil, after that I started to train 1k8 problems until I reach specialist and expert. Upd: I think the best way to do it is your rating point + 400. (Sorry for my bad english)

»
9 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Now finally my exams are over. I can once again participate in contests.

»
9 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Very glad to see another Div3 in small interval! good luck everyone!

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

Why is it showing registrations completed, does it mean I cant register for the contest now?

»
9 days ago, # |
  Vote: I like it -37 Vote: I do not like it

expert i'm coming

»
9 days ago, # |
  Vote: I like it +67 Vote: I do not like it

I appreciate that the testers are arranged such that their usernames' colors form a palindrome.

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

    If you had not mentioned that I would have never noticed that. Thanks for informing.

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

    Maybe a hint for the contest...XD

»
9 days ago, # |
  Vote: I like it +13 Vote: I do not like it
Spoiler
  • »
    »
    8 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    "..just like you will be upset if many solutions fail after the contest is over."

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

hope there will be strong pretests as last contest was ruined by weak pretests

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

    The contest hasn't even happened yet...

    Edit: as you edited, I hope so too...

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

"I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over."

phew, unlike last contest ;)

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

    Congratulations for becoming an expert for the first time :)

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

see my profile I will never give div 3 I dont know how so many people solve so fast and ACM-ICPC rules sucks too.

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

    The way people solve it fast is practice. I did the last div 3 contest just like you and you spent 1:30 hours on D, which isn't particularly hard if you're familiar with this type of idea. Blaming the ruleset is kind of dumb imo because on different rules the difference is that the problems would be much harder to balance out a longer submission window

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

    You'll never be as fast if you never participate though.

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

    Speed is an acquired skill.

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

Liked the thanking section!! where he used symmetric colour combinations.. :)

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

I registered for the contest before today's one (Specialist -> Expert) and it still says I'm in competition. Just to confirm this contest won't be rated for me right.

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

    I don't think it will be rated for you.
    Enjoy solving problems from the end XD

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

    it will be rated, if you registered as cyan, I've experienced it recently and lost 80 points of rating)

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

      Looks like it says I'm out of competition now?

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

        i haven't seen posts from mike about the fix, but maybe he already fixed it

»
9 days ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

Hope pretest will be strong, not like last contest

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

Hi everyone,

I would like to know whether I can start 8 hours following the competition starting time since the starting time is past midnight for me. (I am new to competitive programming).

Thanks very much. Cheers

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

    No , if you give contest at later time than the mentioned time it wouldn't be considered for ratings . It will become a practice contest . For having yourself in official standings you must give contest at the mentioned time only then only you would be considered for standinds and rating change

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

    You can start a Virtual participation whenever you want after the contest but if you want to make your rating update you have to follow the starting time.

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

    I guess you cant participate later, but if you don't need rating, you always can participate virtual. It will be just like normal participation, but without rating. Cheers and good luck.

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

Now, finally before my exams, I am gonna compete.

And can anyone please spare a minute and tell me in which division do I belong, my rating being 814. Thanks.

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

    You can participate in any contest except those rated solely for Div. 1. This means that you can participate in Div 3 , Div 2 and combined Div 1+2 rounds

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

All the best everyone.

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

Please do not make it like yesterday contest .. try to provide a strong pre test cases.

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

Is there any chance of arranging these contests so they are in the evening or weekends. Anyone who has a job can't enter as they will be working.

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

    I might not be in the evening in your country but It is in mine. So, it would be kinda impossible to keep it in the evening for every country because timezones exist.

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

    If you prefer weekend contests, then AtCoder may be a good choice for you.

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

If I know it early, I'll not get to expert:)

»
8 days ago, # |
  Vote: I like it +3 Vote: I do not like it

So we penalty of 10 min on the wrong submission and not of 50 points. Right?

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

    For every minute, 5 point decreases from the main point. Like, 500->495->490. So, penalty of 10 minutes and 50 points are same

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

      it's not 5 points depends on how many points the problem has the higher points the problem has the more points decrease with time

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

        Your cf graph orz

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

          What does orz mean i read it all the time

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

            It looks like the side view of a man kneeling o is the head, r is the head, z is the bent legs. Took me a while to see it too.

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

Good Luck to Everyone

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

o sweet lords of coding, help me reach 1200.

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

HOPE i can solve more than one question today

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

Whoa..25k participants!!...

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

Last minute tip ! Open this to side : CF Notifications So that you don't need to wait to see AC's

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

After so long time i'm missing a CF rated contest for my Covid. :'( Hope to come back soon.keep me in your prayer. :(

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

Can't even solve A , very bad day

»
8 days ago, # |
  Vote: I like it -10 Vote: I do not like it

div2

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Oof.

»
8 days ago, # |
  Vote: I like it -50 Vote: I do not like it

Worst problemsetter ever.

»
8 days ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it
A,B1 == div 3 
B2,C.. == div 2 
»
8 days ago, # |
  Vote: I like it +16 Vote: I do not like it

A perfect div2 round.

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

A divison 2 contest with Divison 3 participants.

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

you should have said to check D2 before D1 instead of B2 before B1 I didn't get how dominoes are placed until i checked D2

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

    hey can u tell me the logic behind b2, i got what the maximum number of single colour used would be but i could not figure out how to colour them without going against the rules.

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

      any number that exists k or more times must be colored with all k colors and what's left of that number occurrences are zeroed so you need map with vector of positions of that number to do that and other numbers that exists less than k just gather their positions in one vector and color them any way

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for the great contest :)

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

This round is more like a div1+div2 round but not like a div 3 round.

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

I got cheated in the name of div3 :(

»
8 days ago, # |
  Vote: I like it +13 Vote: I do not like it

lovely problems!

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

When can I check the testcases?

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

Loved it. This was my first contest. :)

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

Problem C was incredibly similar to this problem, so much so that I copied over my solution almost verbatim...

»
8 days ago, # |
  Vote: I like it +22 Vote: I do not like it

Perhaps you should read the problem B2 before you start solving B1.

Was this meant to be a troll?

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

This round was too hard for Div. 3

»
8 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Well I found that pretty tough and it wasn't even meant for me

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

    Solved all but D2. Why is problem D so hard?(or maybe I'm being dumb)

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

      I decided to focus on completing D2 instead and that deprived me of the time to attempt E or F. D2 was conceptually fine but the casework and construction is very fiddly.

      Even prior to that, B2 was fine but not Div 3 problem B fine.

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

        I implemented it by assigning different integers to each domino (so casework was on integers, without considering which letter should be used for which domino). Later I processed the integer table as follows:

        • create a graph of neighboring dominos IDs (so that we know which colors are forbidden — if two IDs are connected, we can't assign them the same color);
        • notice that no domino has more than 6 neighbors;
        • this means that you can simply select any color for your domino that is not yet assigned to any of your neighbors in the graph and you will never run out of letters;

        Submission 123498750 containing the color assignment at the end of st() function.

        Changing D1 into D2 took slightly less than 20 minutes.

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

          I did something pretty similar except it was just a row-by-row construction where I incremented a value (mod 26) while it matched any of its above or left neighbours.

          Not conceptually too difficult for sure, but with the different cases (N odd, M odd) I found it a pain, and the kind of implementation that isn't great for a 2 hour contest except for the most efficient coders. But I was too committed by that stage to stop and move on. I have since seen that E in particular was a much cleaner question and had I realised what D2 entailed I would have skipped and solved E.

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

            Makes a lot of sense, thanks for the reply ;)

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

            I did something to make the casework easier-

            We know at least one of n and m is even. So we have two cases-
            1. n(rows) is even
            2. n is odd => m(cols) must be even

            In case 2, we can rotate the table by 90 degrees => n and m are swapped, and all horizontal dominoes become vertical and vice versa, ie. in the rotated configuration, k becomes m*n/2-k. So we only need to solve for case 1, and that's it. (Oh, and we rotate the matrix back before printing)

            For filling the table, filling from left to right and from top to bottom at all times worked cleanly for me. (Had only to check the top, left, and bottom-left dominoes) submission

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

    I was chatting with other people at the same time so I didn't focus. But seriously I wasn't ready for this. Without turning on my brain before the contest, I just wanted to quit the moment I saw B and D.

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

someone please hack my submission.123523305

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

    It looks fine, in my opinion it should pass the system tests ;) I tried to hack you based on the fact that you allocate large arrays statically but it passed ;) Good job :D

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

wasted 1 hour on implementation of B2 :/

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

Hoping to see more such highly balanced contests in the future :D

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

So I did not do very well. any advice or techniques on how to get better? thank you all in advance

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

what is pretest 2 of B2 ? I was not able to figure out till the end

»
8 days ago, # |
  Vote: I like it +29 Vote: I do not like it

The problems were really interesting. Kudos to the authors involved! Would have been much better if this round was half an hour longer though

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

    Exactly, would have been better if it was longer.

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

How to solve D1? I tried 3 cases. Got WA on Test 3.

Cases

Did I miss anything?

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

    If rows are odd, then you need atleast m / 2 horizontal dominoes.

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

I submitted my solution with 22 seconds remaining. I couldnt see the verdict because the page was just loading. Now when i check in my submissions, there is no submission showing. And guess what, when i submitted it in practise it was accepted. Can i be helped??

»
8 days ago, # |
  Vote: I like it -12 Vote: I do not like it

B2 felt misplaced, for me B and D shoud have been swapped. Or C and B swapped. Or B, C, D reversed... whatever, I worked much to long on B2, and finally was not able to solve it.

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

How to solve B2?? I am not able to solve it

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

    I binary searched for the number of elements for each type and then reconstructed the coloring according to it. I think I overkilled it though.

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

      I don't see where binary search was required. I didn't think it was as difficult as the comments mention, but perhaps It was and I was just in form.

      I really liked problem $$$B2$$$, tbh.

      You can look up my code: 123477048

      Incase something isn't clear in the code you can ask me. But, mind you, I'm terrible at explaining.

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

    After having read the solution it is not very complecated.

    Consider f[i] to be the freq of i in a[].

    Then foreach f[i]>=k color the positions of the i in a[] with the k colors. Then put all other numbers in one big group and do the same in that group.

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

    Maintain count and position of each character in hash table, for example if array is 1 1 2 1, the count[1] = 3 and position[1] = 0 1 3.

    Create an array result filled with 0 of size n.

    Next iterate through each unique character in the hash table, now there are two cases:

    1. If count of any character >= k then that means you can paint each position containing that character with paints from 1..k, so iterate over position[character] from 0..k and fill each entry in result at position in incremental fashion, so result[ position[character][i] ] = i + 1

    2. If count of character is < k then push the positions of position[character] in an new array say leftPositions

    Now, at last, pop positions from leftPositions in size of k, and fill the popped positions in with paints ranging from 1..k, while popping in size of k, if at any time the size of leftPosition < k then stop and print result.

    Here is code to this approach: https://codeforces.com/contest/1551/submission/123471900

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

      I am doing something similar to this but failing on testcase 2, can u check it out if u can?123490522

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

        In your code, two same numbers might end up with same color, your case handling for when count >= k is fine, problem lies in your handling of when count < k.

        Consider this small case (it is not a valid test case just taking it to show whats wrong)

        a = 10 11 12 10 .....

        k = 3

        Your code may produce output like this: 1 2 3 1 ..., you see both 10's have same paint 1, that's the problem.

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

          please give a test case if u can

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

            n = 6, k = 3

            a = 1 2 3 1 4 5

            Valid output: 1 3 1 2 2 3

            Above program's output: 1 2 3 1 2 3

            You see that both 1's are getting painted by same color 1, which is invalid

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

          oh right thanks, that was such an oversight on my part

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

Worst performance by me... could only solve 1......I think now i should only attend only virtual contests for a month or so :(

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

    Why attend only virtual contest? I say, you should attend the on-going-contests as well, I suggest you not to care about ratings. Also, during the virtual contests you don't get that feel when you solve more problems than your level. Overall I say that its a different atmosphere when giving on-going-contests vs. virtual contests.

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

i got a WA on test 185 can anyone provide me with a counterexample 123529703

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

    Maybe try :

    n=6 k=3

    a = 2 3 1 2 3 1

    This case helped me to identify my mistake :)

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

Is it only me whose div3 performance is worse than div2?

»
8 days ago, # |
  Vote: I like it +9 Vote: I do not like it
My construction for D2
  • »
    »
    8 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you plz. elaborate your solution little bit more.

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

      The main idea is we partition the grid into as many 2x2 blocks as possible, with each 2x2 block being able to hold two horizontal or two vertical dominoes. If $$$n$$$ or $$$m$$$ are odd (only at most one of them can be per problem constraints), then we will have an extra strip on the end (the purple and brown region in the diagram). That extra strip can only be populated with dominoes in the same direction as the strip (so horizontal if the strip is horizontal, and vertical otherwise). Now, since we don't have as many letters as dominoes, we will have to reuse some, and I make sure two touching dominoes don't share the same letter by encoding same letters on diagonals, as shown in the diagram.

      I don't have the most rigorous proof for why this construction covers all cases, but the main idea is you have the wrong parity of $$$k$$$, then there's no way to evenly fill the grid without having a gap in the end that a domino of the opposite orientation cannot fill. On the other hand, if the parity is correct, this construction covers it.

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

Tried to implement C for more than 1 hour..May be extra 15 minutes could make the job done..sigh

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

Isn't this output that my code generates for B2's sample input correct? Showing WA on test 1

1 1 2 3 0 1 2 2 3 3 
1 2 3 4 
1 
1 1 1 0 1 1 1 1 0 0 0 1 0 
1 1 1 2 1 1 1 2 2 2 0 2 2 
1 1 1 2 1 2 2 2 3 3 3 3 0 
»
8 days ago, # |
Rev. 13   Vote: I like it 0 Vote: I do not like it

why is this submission for E giving WA 123523281 on test case 5 I constructed a

$$$dp[i][j]$$$

whose states describe that we have arrived at i th point in the prefix with j moves done. To do that I first precalculate the

$$$pre[i][j]$$$

which says the number of elements in the suffix

$$$i,i+1,...,n$$$

such that the elements after the ith index (including i) have

$$$a[i]-(i-j)=0$$$

, i.e. we have done j moves and after that j moves the number of elements which are now standing at the required index. Now we can iterate over the moves done and check if

$$$dp[n][j]>=k$$$

and return the minimum j . please help if you can? The transitions are as follows

$$$dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+pre[i+1][j]-pre[i][j-1])$$$

second transition is as follows you deleted at the ith index. so

$$$pre[i+1][j]$$$

calculates the new sum that should be added now that we have made j moves and only the index after i is affected as the left shifts happen from these indices. Final number of elements which are equal given that we have made j moves are in

$$$dp[n][j]$$$

and now we can simply iterate over j from 1 to n

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

    I did exactly the same, except my dp[i][j] is the maximum good indices considering a prefix of length i with j elements kept.

    The transitions are much easier:

    $$$dp[i + 1][j + 1] = max(dp[i + 1][j + 1, dp[i][j] + (A[i] == j))$$$

    and

    $$$dp[i + 1][j] = max(dp[i + 1][j], dp[i][j])$$$

    (A is 0-indexed and every element is subtracted by 1 beforehand).

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

      Niceeee so instead of keeping the number of elements deleted you instead kept the number of elements which remain. But I think my solution should work too? Is there a bug in my code> :(

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

    Also I don't think the pre thing is needed.

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

    Hey I have exact same solution as yours. You can look at the implementation here. 123524901

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

happy thing: accepted (during contest)

sad thing: accepted (1 minute after the contest)

worse thing: unfortunately, your solution of problem X has been hacked

worst thing: wrong answer/time limit exceeded in test set X (main test)

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

Did anyone solve D with DP ? I used dp on columns for each two columns c and c + 1 I may put [0, 1, 2, .., min(n, k)]

they will be placed greedily from top to bottom on column c and c + 1 and the remaining cells on c and c + 1 will contain only vertical dominos, if c == m — 1 i can only place vertical dominos on c;

I really don't know why this works, but I have intuition that when placing the horizontal dominos they can form some kind of connected block, and hence I can try different shapes for this CC

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

Thank you! The contest was really interesting!

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

Is it only me Or B2 was harder for it's position?

»
8 days ago, # |
  Vote: I like it +5 Vote: I do not like it

In today's contest , problems were great but time was less and problems were more.

»
8 days ago, # |
  Vote: I like it -30 Vote: I do not like it

Trust me, even I would have set better questions for Div3 than this.

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Trollforces

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

Cannot say I really enjoyed the problems, it was more of a Div 1.5 for me.

»
8 days ago, # |
  Vote: I like it +7 Vote: I do not like it

Two contests ago I reached expert so this was unrated for me, yet I was only able to solve A and B1. Clearly I still don't deserve my rating

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

Help needed! There is something wrong with my lambda expression below, but I have no idea why it turned out this, from my point of view, both a & b is in the range of [0, n), but it can be some invalid value, more exactly in this code, when n >= 17, it would be a mess. I would appreciate it if anyone could help!

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        int n; cin >> n;
        vector<int> sz(n), r(n);
        for (int i = 0; i < n; i++) {
            r[i] = i;
        }
            sort(r.begin(), r.end(), [&](int a, int b){
//                 cout << "a = " << a << " b = " << b << '\n';
                if (a < 0 || a >= n || b < 0 || b >= n) {
                    cout << "@" << a << ":" << b << ":" << n << '\n';
                    return false;
                 }
                return sz[a] <= sz[b];
            });
    }
    return 0;
}

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

    I have no idea about "invalid values" but you should never use <= or >= in custom sort comparator.

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

      Thank you so much! I change the '<=' to '<', the annoying value disappeared! But why? Is it a property of the lambda expression?

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

        No, it is not related to lambda.

        Take a look at the parameters part of https://en.cppreference.com/w/cpp/algorithm/sort and the requirements of a comparator https://en.cppreference.com/w/cpp/named_req/Compare .

        Always keep this in mind.

        I have no idea what will happen exactly if you use <=, (I assume it is a UB — undefined behaviour?) but UB always leads to disaster.

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

Problem D2 reminded me of this problem if anyone wants to try.

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

Problem E was very similar (though not identical) to task from XIV Polish Olympiad in Informatics: statement in Polish

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

Hi ! I encountered something weird in my submission for todays 'C'.

Firstly I have made a 'vector of vectors' which store the property of each string i.e. the number of a's,b,c,d,e. Then while checking for character 'a', I am sorting this 'vector of vectors' according to the difference between count of a's and rest of characters.

Driver code

But this is getting RTE in the comparator function:

Comparator

While Debugging for Test case 2, 2nd test.. I found that the size of 2nd vector passed in the comparator is coming out of be 0 at one stage (but all the vectors in my 'vector of vectors' are of size 5), and obviously RTE is generated there ..

Can somebody tell more about this ambiguous behaviour ? and how to correct it ( while using the comparator function only )

PS: In Comparator i have passed as vector<ll> &v1 only idk why it's showing vector&v1 here. Also my complete code is very ugly, so that's why am only putting snippets here !!

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

How are the multiple answers tested?, like in today's B2

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

    Put every colored element in a set. Let's say that in correct solution the size of each color's set is n, now check for the given output if the size of set is equal to n and there are no repeated elements.

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

How to solve C ?? I am not able to solve it.

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

    Let's define how interesting a given letter in a string as follows:

    • The number of occurrences of a given letter $$$-$$$ the number of occurrences without that letter. Let's call this value $$$x$$$.

    For example, in the string $$$bac$$$, $$$x_a$$$ would be $$$-1$$$ because $$$a$$$ occurs once and the number of non-$$$a$$$ letters is two. $$$1 - 2 = -1$$$.

    Another example is $$$aaada$$$, $$$x_a$$$ would be $$$3$$$ because $$$a$$$ occurs four times and the number of non-$$$a$$$ letters is one. $$$4 - 1 = 3$$$.

    We can find how interesting a given letter is for each letter $$$a, b, c, d, e$$$ and find the longest subsequence with a sum greater than $$$0$$$.

    This is equivalent to finding the longest subarray with a sum greater than zero when sorted.

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

      Why is that equivalent? Any intuition?

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

        Well, greedily, we're trying to find the maximum subsequence sum, and when we sort it (in descending order), the largest elements in the array come first (obviously).

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

Can problem A be solved using binary search?

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

can someone kindly tell me why am I getting a TLE in this code for problem B2 ? It will be very appreciated..thx 123532079

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

    You are getting TLE because it is taking a long time to parse such big preprocessor statements. Upd: Oh you removed your unformatted code from the comment lol. The actual reason is allocating array of size 2e5 in each test case and there can be upto 1e4 testcases. So you're taking time for allocating arrays of size 2e9. This will TLE.

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

      then it should get tle in test case 1 but its getting in test case 2

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

        Having irregular font size is undefined behaviour in C++

»
8 days ago, # |
  Vote: I like it +1 Vote: I do not like it

This is not the div.3 we wanted but this is what we needed.

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

Is there any way to get all test cases? My program for B2 constantly crashes on test 2 case 3901 and I have really no clue what's going wrong. 123544433

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

    You have to use if conditions, its not pleasant but it works if the input is not too large. run your solution for test case 1, then for test case 2 print the input for T=3901 for others just take input and don't print anything.

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

    Check my submissions for B2 where i printed the failing tc for 3901 ( using your code )

    8 4

    4 5 4 3 5 3 3 3

    Your Ans: 1 1 2 2 3 3 4 0

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

Can anybody helps me with my code in E it gives WA on test 4

code: https://codeforces.com/contest/1551/submission/123549241

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

Any ideas for F?

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

    If k = 2, you can pick any 2 nodes so answer is nC2. For k>2

    Let's say we can pick k nodes such that each node has a distance D with the other. Since all of these nodes are equidistant from each other, and the number of nodes is >=3, this has to be a star formation with one "unselected" node at the centre, and all the selected k nodes are equidistant from this centre (distance of D/2 to be precise, D can never be odd). Let's call the centre X. Let's root the tree at X.

    Also note that, any 2 selected nodes will have LCA equal to centre (meaning any path from one selected node to the other must go through centre, otherwise their distance will become shorter). What this means is that from the subtree of each child of X, only one node can be selected. If the number of children X has is <K , we can't select K nodes as the question states. If it has more children (C is the number of children X has) -

    Do dfs from each child of X and for a height h, let's say there are n1, n2, n3 ... nC nodes at height h in each child-subtree respectively. Since from each child-subtree, we can only select 1 node. The task becomes selecting K nodes (one from each child) given the above information. This can be done with dp.

    DP[a][b] means the number of ways we can select b such nodes (at max one from each child-subtree) from the first a children.
    
    DP[a][b] = DP[a-1][b] + na * DP[a-1][b-1]
    // Don't select a node from ath child + Select any 1 among the na nodes from the ath child.
    
    ans += DP[C][K]
    

    Looping over the root node X and height H and then solving the dp for each such combination yields the final result. You can look at my code, but my implementation is a bit messy with some extra code.

»
8 days ago, # |
  Vote: I like it -11 Vote: I do not like it

Finger crossed,for not to repeat last round hacking drama & to be specialist for the first time which missed yesterday due to hacking drama

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

    It's not a drama. You had an incorrect solution for which you were rightfully penalized!

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

      Yes, but it was massive for two problem, problem b was hacked/failed maintest about 3k and for problem D it was about 1.8-2k. Total standing was changed!

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

Can someone help me on problem B2 i am getting WA on test 2

I did binary search on the number of elements for each i from 1 to k

Submission https://codeforces.com/contest/1551/submission/123550847

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

EDIT : SOmeone told me , i got it now ! Hey , why does this solution does not works for b2 ? I understand the other, more smarter way to code it, but I am wondering why does my solution does not works (for tc 460). I have seen that it says that "Not all colors have equal number of elements", so i tried my code on a lot of tests then checking for the occurences of the colors, to see any counter examples, but even after running it for a long time, it does not work ( my code for stress testing is included, just commented).

Thanks in advance ! :)

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Wasnt at all div3 types

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What a div 2 round!

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me solution fails.... 123541241

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Clean code for B2 : Code

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Only 4 different characters are needed in D2: 123522856

Idea:
»
7 days ago, # |
  Vote: I like it +1 Vote: I do not like it

editorial?

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone kindly tell me why am I getting TLE in this code for problem B2? 123566277. I really don't know why it get TLE T_T

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

    in every testcase you are initializing 2e5 memory ..may be thats why..you don't need to because ai<=n

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

      Thank you very much! I get AC after fixing

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How long does it take to update the rating?

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

    Come on, man. We can literally see that this is not your first Div.3 round. Why these useless comments?

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

      Where did it mentioned that it will be rated for first div 3 contest?

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

        What he is saying is, you should have already known that ratings will be updated in a short time.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this contest made unrated? I can't see any change in my rating nor in the ratings of top contestants.

»
7 days ago, # |
  Vote: I like it +3 Vote: I do not like it

i must say this wasn't div3 contest , problem C was tough for me.

»
7 days ago, # |
Rev. 2   Vote: I like it -13 Vote: I do not like it

Thanks for Round!

»
7 days ago, # |
  Vote: I like it +10 Vote: I do not like it

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

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Great round, thanks

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

How the ans of this testcase of problem E is 4.

testcase

I think ans is 3

{7,5,4}, {1,8,2}, {7,9,10}

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help in memoizing this recursive code for problem E since I get TLE: Problem E

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

    I don't think it is memoizable considering the recursive function has 6 dimensions. Try optimizing this and bring that 6 down to a 2.

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

i missed vovuh :<

»
7 days ago, # |
  Vote: I like it 0 Vote: I do not like it

please share hint for C.

»
5 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone help me with a test case for which my solution for problem E fails.

https://codeforces.com/contest/1551/submission/123833545

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

Nice contest