CodeChef_admin's blog

By CodeChef_admin, history, 2 months ago, In English

We invite you to participate in either CodeChef’s November Cook-Off or SnackDown Pre-Elimination, this Sunday, 21st November, rated for all. Cook-Off’s Div-1 and SnackDown Pre-Elimination will have the same problems.

Time: 9 PM — 12 AM IST

On the problem setting panel are:

Users who have qualified to participate in the SnackDown Pre-Elimination cannot participate in the Cook-Off. The Pre-Elimination will be rated for all users participating in it.

The Div-1 Cook-Off and Pre-Elimination ranklists will be merged to determine the winners of the cash/Amazon voucher prizes. Prizes for Cook-Off and Lunchtime Div-2 and Div-3 have been stopped from this month.

Plagiarism checks are being done on all the Snackdown rounds, and will be announced within a week, after which the Pre-Elimination ranklist will be finalized. Cheaters caught will be permanently banned from the platform.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

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

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

Why both contests at same time? Is there any reason?

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

    simply , because they have shortage of problems for div-1 and pre-elimination round.

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

How many testers you want Admin : Yes

Testers:NO

reference previous contest

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

Plagiarism checks are being done on all the Snackdown rounds, and will be announced within a week, after which the Pre-Elimination ranklist will be finalized. Cheaters caught will be permanently banned from the platform.

This puts a smile on my face.

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

    Can we say that Snackdown was a bait from CodeChef for the cheaters? Let's see what will happen!

    ... background: where is my popcorn? ...

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

    Shouldn't plag should be checked in cook-off also if the problem set for both of them is nearly same.?? Literally everyone's solution for div2 D is exact same

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

    But if I tell you the reality, the cheaters have changed their code just a little bit such as func name or added some extra lines and they are not being taken into consideration. If you don't believe me then go to the slippers problem and check the successful submission check the last 100 and more than 90 have the same code just a bit changes

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

Prizes removed from div2 and div3 and I wasn't able to win once.

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

    I won one but didn't got anything yet.

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

The Pre-Elimination will be rated for all users participating in it....

Then if i attend only on pre-elimination then i rated as global round of all div, sir ? CodeChef_admin

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

How many will qualify for elimination?

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

    top 500 + [80 slots for global children, indian children + girls]

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

      Isn't "+ girls" unfair?

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

        no, its totally fair. girls in India don't know much coding, or are very smart so they need special prizes for them just to make them feel comfortable.

        Otherwise, direct competition with boys will destroy their self esteem.

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

      and how will they know who are children and girls??

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

Reminder: Contest starts in ~45 minutes.

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

Are the 4 problems shown in the contest in a seperate category part of snackdown?(it should consist of div2,div3 only problems)

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

    Those 4 problems are not a part of the contest. The "Non-scorable" heading was missing. They were totally removed after the first couple of minutes. Apologies for the confusion.

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

Maybe not

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

Is there a soln to DECSUBK that works in $$$O(n ^ 3)$$$ or similar or are they just troll constraints? I got AC with an $$$O(n \cdot logn)$$$ solution but I can't think of any simpler idea with worse complexity.

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

    Brute forcing the solution by checking for each index the minimum number possible on that position will work in O(n^3 log(n))

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

    My $$$O(n^3log(n))$$$ solution was to greedily assign the elements from $$$1$$$ to $$$n$$$, checking if it's possible by seeing if the minimum possible longest non-decreasing subsequence length is $$$<= k$$$. If [min possible] <= k <= [max possible], k must be achievable.

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

    My soln was $$$O(n^3*logn)$$$ and it aced in 0.34s. I found LIS of $$$O(n^2)$$$ sequences in $$$O(n*logn)$$$.

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

    I did it in O(n^3).For every element in the sorted array I made an LIS array and checked at which position can the current element be inserted so as to not exceed LIS by k.

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

    What's your solution?

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

      Lets make some observations:

      • If an element $$$i$$$ appears $$$x_i$$$ times, the length of the longest non-decreasing subsequence is at least $$$x_i$$$. So the answer doesn't exist if there exists some $$$x_i \gt k$$$.

      • The length of the longest non-decreasing subsequence of an array made up of $$$k$$$ strictly decreasing segments is at most $$$k$$$.

      • If for each element $$$i$$$, we place its $$$x_i$$$ occurrences in $$$x_i$$$ contiguous segments $$$[l_i, l_i + x_i - 1]$$$, such that $$$l_i \lt l_j$$$ if and only if $$$i \lt j$$$ and all $$$k$$$ segments are non-empty, the length of the longest non-decreasing sequence is exactly $$$k$$$.

      • To produce the lexicographically smallest non-decreasing sequence in this manner, it is optimal to make as many of these segments (from left to right) as possible have exactly one number, and for this number to be as small as possible.

      This yields a simple greedy where if we have placed the occurrences of the first $$$i - 1$$$ elements in the first $$$j$$$ segments till now, it is optimal to place the element $$$i$$$ in the range $$$[j, j + x_i - 1]$$$ or $$$[k - x_i + 1, k]$$$ if $$$j + x_i - 1 \gt k$$$.

      This can be implemented using a map or array of the number of times an element appears in O(n logn) or O(n) respectively.

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

    .

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

Why is pre-elim round rated? I've qualified, but at what cost T_T

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

CodeChef_admin Will the top 500 of this round get T-shirts?

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

    Same question.But I think in this round 580 people will be qualified and 80 of them will not get a t-shirt as the rule states top 500 contestants of eliminations will get t-shirts.

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

    NO, this was pre Elimination round. This is mentioned on the prizes page.

    Top 500 participants from the Elimination round will get a cool SnackDown t-shirt.
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      Top 500+80 will qualify for the elimination. So the top 500 out of those 580 will get T-shirt!! Does not seem right for me

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

I hate GUESSROW.

IMHO hiding this information is too unfair.

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

    I ran my solution locally with different seeds, it used in average 590-620 queries per test, then I chose the best seed for my interaction (which was probably as good to any other interactor as any other seed) and submitted, assuming that there are not a lot of tests and I can force it to pass in an expectedly finite number of attempts; it only took one.

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

      Yes, so your situation is OK. For me, who was not very clever, it was something like 600-650, and it was impossible to tell appropriately from the information available from the statement when to stop improving the solution.

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

    Hating the problem seems a bit too much (though your opinion was shared by the coordinator...) but what you say about the number of tests is correct. It would have been better to say the number of tests explicitly.

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

In SLIPPERS only after third wrong attempt I've realized that there is a second sample test, don't do that.

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

    I have realized that after seeing your comment, LOL

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

    I also didn't notice it.I think they should give explanation only after giving all the samples.

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

      I do agree, sadly codechef interface does not allow for it.

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

    https://github.com/jmerle/competitive-companion was the only reason I realised there is 2nd sample.

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

    I realized it after seeing your comment and made 6 WA's which could have been avoided.

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

    Let me join your club of "super-attentive-and-scrupulous-coders". To be honest, I don't understand why they couldn't place the samples together, before or after the explanation.

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

Why $$$M=1$$$ in MEGAMU2...

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

    Was it a special case for your code? I am asking because it was not special for the official solution, so I don't see what's wrong with it.

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

      I can say for myself, that I noticed that the sequences where $$$\mu$$$ is nonzero can be described as follows:

      1. Delete all zeroes.
      2. Let the part before first element greater than $$$2$$$ be $$$p$$$, the remaining part be $$$s$$$.
      3. Delete all ones from $$$s$$$.
      • either $$$p$$$ is an even number of twos, or $$$p$$$ has an odd number of twos before the first one;
      • $$$s$$$ consists of blocks of type $$$(x+1)^+(x)^+$$$ and $$$(xx)^+$$$;
      • $$$s$$$ does not have falls by at least two.

      Then I calculated some dp, and I had to handle $$$M = 1$$$ manually to calculate the number of valid $$$p$$$-s.

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

        Thank you, now I see the point (I knew about this solution, but I completely forgot about it when writing the above comment).

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

        That is exactly what I did. Thanks for the explanation.

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

Hello everyone. After the round was over I have started to examine some problem "Slippers" solutions and they were all suspicious identical. Judge yourself:

Submission #1

Submission #2

Submission #3

Submission #4

unfortunately, almost all the submissions were like this.

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

    I have noticed suspiciously big jump in number of AC for SLIPPERS approximately half of hour before end of contest. Then after contest was finished I decided to check couple SLIPPERS solutions which were made in the last half of hour and ACed from the first try and a lot of them (1,2,3,4) are identical. So indeed there was some leaked solution, unfortunately. Fingers crossed for CodeChef's MOSS system.

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

      Another interesting finding is that masoom_41 placed 305 with a single problem solved. Is it some weird platform glitch?

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

        Most likely he ACed one of 4 problems before they were removed. /cc CodeChef_admin

        Upd: His cc profiles says 2 acs SNCKPE21: ODDSEVENS, PRDTPAIN but ODDSEVENS was non scorable in snackdown.

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

          Thanks for reporting this. Yes, it was a glitch with just this 1 user due to the non-scorable problem being removed during the contest. It has been fixed.

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

how to solve slippers.

  1. Read GP of IMO J
  2. ???
  3. win
»
2 months ago, # |
Rev. 4   Vote: I like it +8 Vote: I do not like it

Thanks for the contest, very nice problemset.

For GOODRANKING, I did some randomization and it passed: https://www.codechef.com/viewsolution/54143464. Not sure why though, my check function works in O(n^2) in worst case, so overall worst case time complexity should be O(n^3).

UPD : Code works even without randomization. No idea how xD

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

Very nice contest, specifically the part authored by dario2994. Much better than I expected from CodeChef. Hopefully the elimination/finals will be as nice.

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

BTW how the rating update works? Div.1+pre-elimination merged ranklist or separate ranklist?

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

Thanks to nishuz

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

    It's probably because the elements are not necessarily distinct.

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

      Can you elaborate ?? or provide a case where non-unique elements can cause problem
      In one of my test cases I tried with two same elements but answer with AC code and ternary search code is same

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

          THANK YOU!! very much for providing that test case
          Learnt a bit more about about ternary search today
          I modified my code so that there are only distinct values when I ternary search
          If anyone interested in ternary search solution Code

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

during the 25 last minutes of the contest, there are about 400+ accepted solution for "Guests like slippers".

most of them are the first submission, i.e. no penalty.

that's great ! hope the next round will also be fantastic like this ! everyone knows suddenly how to programming...

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

Really enjoyed solving D, the observation was cute and felt rewarding (though I'm not sure if I had the intended solution).

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

When will the ratings get updated?

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

    I think it is completely unreasonable to expect fast rating updates AND thorough plagiarism checking.

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

When will the November Cook-Off rankings will be out? Why it is taking so much more time than usual?

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

CodeChef_admin I have seen that my rank in SnackDown Pre-Elimination jumped up by ~40 positions and that the rating were updated. Does it mean that plagiarism checks were done already? And if so — why all solutions from my and 3 out of 4 solutions from DoIGetConribution's comment weren't removed and authors weren't banned from appropriate contest and from platform at all?

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

    CodeChef_admin I investigated submissions history of this one guy from DoIGetConribution's comment who was removed and I guess I know what's going on. You guys have removed from the scoreboard participants who have submitted solution for both SnackDown Pre-Elimination and November Cook-Off and preliminarily updated ratings but plagiarism checks are still pending/in progress. Is it correct?

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

Its more than a week ...... How much time more codechef take to ban cheaters...

»
7 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

CodeChef_admin my rank in snackdown pre elimination was 905 and rating was updated according to it but now my rank is 715, still the rating is the same. Is it expected or it will be fixed?

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

    It is expected. Ratings will be recalculated for all contests only after a few more months when all plagiarism checks have been done.

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

      CodeChef_admin Are Plagiarism checks for all rounds of Snackdown done ?and when can we get final list of users participating in elimination round?