CodeChef_admin's blog

By CodeChef_admin, history, 3 years 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

| Write comment?
»
3 years ago, # |
  Vote: I like it -25 Vote: I do not like it

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

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

»
3 years ago, # |
  Vote: I like it -23 Vote: I do not like it

How many testers you want Admin : Yes

Testers:NO

reference previous contest

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

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

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

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

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

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

    I won one but didn't got anything yet.

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

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

How many will qualify for elimination?

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

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

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

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

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

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

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

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

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

    What's your solution?

    • »
      »
      »
      3 years 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
  • »
    »
    3 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    .

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

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

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

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

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

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

I hate GUESSROW.

IMHO hiding this information is too unfair.

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

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

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

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

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

    I have realized that after seeing your comment, LOL

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Thanks to nishuz

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

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

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

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

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

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

When will the ratings get updated?

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

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

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

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

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

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

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

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

      Do 6 months count as "few"?