Ashishgup's blog

CodeChef December CookOff 2021 (with new contest timing!)
By Ashishgup, 3 years ago, In English

We invite you to participate in CodeChef’s December Cookoff, tomorrow — 19th December from 8:00 PM — 10:30 PM IST.

The contest will be 2.5 hours long. There will be 7 problems in Div 1/2 and 8 problems in Div 3. It will be rated for all three Divisions.

Joining us on the problem setting panel are:

Problem Submission: If you have original problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Prizes:

  • The top 10 Global Division 1 users will get $100 each.
  • The top 100 Indian Division 1 will get Amazon Vouchers worth Rs. 1500 each.

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.

Good luck and have fun!

Admin Note:

Edit:

Congrats to the winners:

  1. tourist
  2. maroonrk
  3. Petr

Also congrats to Nyaan for first AC on Tree and Brilliant Array.

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

Comments Comments (45)
| Write comment?
»
3 years ago, # |
  Vote: I like it +89 Vote: I do not like it

As a VIP problem-setter, I can confirm that the problems are diverse and interesting. :D

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

Just another ping about updating rust

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

    I believe CodeChef is working on updating Rust. CodeChef_admin can provide a better update.

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

      I've been waiting for their D compiler update (or at least for getting some optimizations enabled in their old version) since more than 2 months ago. Right now it's in a very bad shape and anyone using D language is severely handicapped. I did manage to advance to 5-stars even with their misconfigured and obsolete D compiler, but this doesn't mean that the compiler is okay. I won't be participating in any rated CodeChef contests until the compiler update finally happens.

      Yes, the admin said that "We hope to have the next iteration in the next month or two". And I also hope for C++20 support as a part of the compilers upgrade. So that it becomes a really fair competition between the users of all programming languages.

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

Wondering why was it so hard to find

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

No "Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each." anymore?

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

    What about Div2 prizes who are under 200 rank ? Will they get the voucher or not ?

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

How to solve Destructive Nim?

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

    It should be easy to prove if you get this idea.

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

    If there is no pile with 1 stone present then player 1 always wins as he can make any given pile contain 1 stone and make the other player remove from that pile the very next round until there is only one pile left after which he empties that pile.

    Now if there are piles with 1 stone present then just remove them one chance at a time and the player with the chance at the end wins(except the case where all piles contain 1 stone). If a players who has a losing position after all 1's are removed tries to be over-smart and gives some other pile to the opposing player to choose from he will simply remove the entire pile if there are more than 1 non-1 piles else make that pile 1.

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

Any Hints for RGB Construction My Approach --> Create longest chain of RGRG.... or GRGR.. . If Blues are more than the longest alternate chain of RG then print -1 , else assign blue from (1 till blue) in node 1 , 2 , 3 ... then add remaining extra R or G left

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

Just to confirm. will I get the cash prize if I am not in the global top 100 lists (Div — 1) but in the Indian top 100?

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

How to solve Tree and Brilliant Array?

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

    Assume the product of $$$A$$$ is power of a prime $$$p$$$. You can solve this using tree DP. After that, you can combine primes.

    Let's add a new constraint:

    $$$A_1 = \textrm{lcm}(A_2, A_3, ..., A_N)$$$.

    Then, the product of $$$A$$$ will be powerful number. There are $$$O(\sqrt K)$$$ powerful number no more than $$$K$$$, so you can enumerate them all using DFS or std::map in $$$O(\sqrt K)$$$ or $$$O(\sqrt K\log K)$$$ time complexity.

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

How to solve Break the Balance?

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it
    Spoiler
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      O(N) optimization
      → Reply
»
3 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I just sat watching my rank fall from 150 to 258 during the last 10 minutes. Most of these last-minute submissions in the Div2 4th problem(RGB) are exact same.

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

Destructive Nim is pretty much the same as Stones from CEOI 2021.

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

Can someone give a proof for RGB? After some casework, it's relatively straightforward to essentially guess R+G>=B is a necessary condition, and then prove that this is also sufficient from there, but a brief outline for its proof would help...

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

    Necessity comes from the fact that you can't connect 2 blue nodes to one red/green. Sufficiency comes from the construction of the solution.

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

    Consider a tree with B nodes satisfying the conditions and with minimal R+G. All B nodes must be leaves. Root the tree at a non-B node. Consider the parent of any B node; it must only have one B child. Thus there's a bijection between each B node and its parent, implying R+G=B.

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

How to solve Binary String Game?

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

      Will it be correct to say that it is so because for every move done by the first player, if the score increases by 1, then the second player has a way to increase it by 2 and vice-versa due to which the total score increases by 3 after both players make 1 move?

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

      can you please explain these two points:

      1. It's easy to see that f(S) can be increased by at most k.
      2. in one move, a player can increase score by either 1 (by making l=1 or r=N) or 2.

      Edit: my first confusion is suppose i have s="101011010001" and the indexes where s[i]==s[i+1] are 4,8,9 (0-based indexing) so what subarray should we flip to increase the f(s). Original f(s) is 8

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
        ← Rev. 2   Vote: I like it +11 Vote: I do not like it
        Hopefully this helps
        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you for the reply and this helps.

          What is P in your above discussion?

          And if s="0110" so which subarray we should flip? to increase f(s).

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

            P is the current value of F(s), F(s) as mentioned in the problem as count of all i from 1 to n for which this condition satisfied |s[i + 1] - s[i]| = 1. If s = "0110" then you can flip range(1, 2) in 1-based indexing making s to 1010 and the first player wins.

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

              Whats is the meaning of this statement

              if k%3=0, first moving player loses else first moving player wins.

              for example if s=0100010111100 here k=7 which are 2,3,7,8,9,10,11 (0 based indexing)

              here k%3!=0 so the first player i.e., JJ wins but suppose

              JJ flips [3,3] (0 based indexing) we get

              0101010111100 p increases 8 from 6

              uttu flips [12,12] (0 based indexing) we get

              0101010111101 p increases to 9 from 8

              JJ flips [8,8] (0 based indexing) we get

              0101010101101 p increases to 11 from 9

              finally Uttu flips [[0,9] (0 based indexing) we get

              1010101010101 p increases to 12 from 11

              and jj does not have a move and jj loses or uttu wins here k%3!=0 still second player wins which is contradicting the first statement of this comment

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

                In you example, you have counted it wrong actually k is 6 and in your mentioned positions 10 is not valid.

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

                  Ohh sry now it is starting to make sense

                  Thank you very much for the help just one little request explain this k%3==0 concept and i will not disturb you again

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

                  Somebody explained above please check it. Comment link

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

Why did CodeChef replace laddus with amazon vouchers?

→ Reply