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:
Contest Admins: Ashish Ashishgup Gupta
Head Admin: Alex Um_nik Danilyuk
Tester: Aryan aryanc403 Choudhary
Setters: Takuki tabr Kurokawa, Ashish Ashishgup Gupta, Jeevan JeevanJyot Jyot, Utkarsh Utkarsh.25dec Gupta and Shiven shiven Sinha
Statement Verifier: Trung Kuroni Dang
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:
Also congrats to Nyaan for first AC on Tree and Brilliant Array.
As a VIP problem-setter, I can confirm that the problems are diverse and interesting. :D
Just another ping about updating rust
I believe CodeChef is working on updating Rust. CodeChef_admin can provide a better update.
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.
Wondering why was it so hard to find
No "Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each." anymore?
What about Div2 prizes who are under 200 rank ? Will they get the voucher or not ?
How to solve Destructive Nim?
If all the piles are 1, then the position is losing iff there are even number of piles.
If not all the piles are 1, then the position is losing iff there are odd number of piles that are 1.
It should be easy to prove if you get this idea.
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.
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
Construct any bipartite tree containing R+G nodes with R nodes and G nodes being in different partites. Attach one of B node to each of them as long as you have leftover nodes.
B > R + G => -1.
if B = 2 , R = 3, G = 3 Why is BRRRGGGB not a possible answer ?
As B < R + G so it is possible.
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?
Yes
How to solve Tree and Brilliant Array?
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::mapin $$$O(\sqrt K)$$$ or $$$O(\sqrt K\log K)$$$ time complexity.Solution
How to solve Break the Balance?
Iterate from $$$1$$$ to $$$i$$$
Let the value $$$k$$$ be number of occurences of $$$'('$$$ before $$$i$$$ — number of occurences of $$$')'$$$ before $$$i$$$. Find the minimum number of swaps required to convert all the elements in range $$$[i,i+k]$$$ to $$$')'$$$ using binary search. Minimum of the number of swaps among all the iterations is the answer
Actually, you don't need to binary search the value as for two adjacent indexes the value of k will differ exactly by 1. So we can solve this problem in O(N).
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.
Destructive Nim is pretty much the same as Stones from CEOI 2021.
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...
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.
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.
How to solve
Binary String Game?Let the value $$$k$$$ be number of indices $$$i$$$ such that $$$(1 \le i \le n-1)$$$ and $$$s_{i+1} = s_i$$$. It's easy to see that $$$f(S)$$$ can be increased by at most $$$k$$$. Moreover, in one move, a player can increase score by either $$$1$$$ (by making $$$l = 1$$$ or $$$r = N$$$) or $$$2$$$. So, if $$$k\%3 = 0$$$, first moving player loses else first moving player wins.
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?
Yes. Note that when we choose a range
(L,R), then only the first element in range(Lth)and the last element in range(Rth), will decide the increase inf(s).The elements that are in between the chosen range
(s[L+1]....s[R-1])will not affect f(s) because their relative adjacent change will remain the same before and after the flip.So now, there are 2 possible choices
s[L - 1] == s[L]ands[R] == s[R + 1], which will lead to an increase of 2 inf(s).s[L - 1] == s[L]ors[R] == s[R + 1], which will lead to increase of 1 inf(s).Now, if a player picks second choice such that none of L and R are boundary elements
(i.e. L != 0 and R != n-1, with 0 indexing), then you can observe thatf(s)will not change at all. So, to increasef(s)by 1,either L = 0 or R = n-1.Now, let's see why having
K % 3 = 0will be losing for first player. (Here K is number of positions wheres[i] == s[i + 1])Suppose player 1 increases
f(s)by 1 in first move. Now sinceK % 3 = 0, after first move, there still must be at least 2 indicesi and j where (i < j)such thats[i] == s[i + 1] and s[j] == s[j + 1]. So if second player chooses the range as[i + 1, j], then he will be able to increasef(s)by 2.Similarly, you can work out the case where first player chooses to increase
f(s)by 2, second player will increasef(s)by 1, and thus second player will always be able to nullify the moves made first player.I hope I helped:)
I think K is the number of positions where
s[i] == s[i + 1].yeah, my bad. Edited:)
This is some great level explanation.
Thanks. I tried my best:)
can you please explain these two points:
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
For your 1st point -
The maximum value of F(S) can attain is
n - 1where n is the length and let the current value be P so here he meant thatK = n - 1 - Pwhich is equivalent to what he said, indices for whichs[i] = s[i - 1]that will be the value of K.For your 2nd point -
In one move when you flip the range
(L, R), then there is only two possibilities :-When you flip , the
s(L - 1) != s(L) and s(R) != s(R + 1)in this case you increase F(S) by 2. Example : 1000001 , flip the range(3, 5) in 1-based indexingso you get 1011101.When you flip, only of them is true
s(L - 1) != s(L) or s(R) != s(R + 1)in this case you increase F(S) by 1. Basically one of them will not exist. Example : 0001, flip the range(1, 2) in 1-based indexingso you get 1101.There is no other possibilities, you can not increase F(s) by more than 2. But there is a possibility that you decrease or do not increase the value of F(s) which is invalid move as stated in the problem.
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).
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 fliprange(1, 2) in 1-based indexingmaking s to 1010 and the first player wins.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
In you example, you have counted it wrong actually k is 6 and in your mentioned positions 10 is not valid.
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
Somebody explained above please check it. Comment link
Why did CodeChef replace laddus with amazon vouchers?
Because they can't afford giving goodies