Hello CodeForces Community!
We’re excited to announce the September Long Challenge sponsored by ShareChat. Along with the opportunity to boost your ratings and win some cool laddus, there are some exciting full-time job opportunities with ShareChat for professionals across the globe. More details about the job opportunities can be found on the contest page.
Problem Tester: teja349 (Teja Vardhan Reddy)
Problem Setters: (Shivam Gupta ), XORier (Priyanshi Gupta), adamant (Oleksandr Kulkov ), step_by_step (Stepan Filippov), bciobanu (Bogdan Ciobanu), rajat1603 (Rajat De), DOlaBMOon (Max Hsia)
Problem Editorialist: vijju123 (Abhishek Pandey)
Statement Verifier: Xellos (Jakub Safin)
Russian Translator: Mediocrity (Fedor Korobeinikov)
Mandarin Translator: huzecong (Hu Zecong)
Vietnamese Translator: VNOI Team
I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.
Contest Details:
Time: 7th September 2018 (1500 hrs) to 17th September (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.).
Contest link: www.codechef.com/SEPT18
Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.
Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie.
(For those who have not yet got their previous winning, please send an email to [email protected]). First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).
Good Luck!
Hope to see you participating!!
Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
I hope no one solves the last question. :P
Hope for something better. ;P
How to solve TAB GAME subtask 2, (with proof )
Hint: For all points in the set S = {(i, j) | i >= 3 and j >= 3}, (i, j) = 0 if and only if (i-1, j-1) = 0. You can prove this by contradiction.
Proof that if (i, j) = 0, (i-1, j-1) = 0:
Let(i, j) = 0. Assume that (i-1, j-1) = 1. Since (i, j) = 0, (i-1, j) = 1 and (i, j-1) = 1.
Since (i-1, j) = 1 and (i-1, j-1) = 1, (i-2, j) = 0. Similarly (i, j-2) = 0.
Since (i-2, j) = 0, (i-2, j-1) = 1. Similarly, since (i, j-2) = 0, (i-1, j-2) = 1.
Since (i-2, j-1) = 1 and (i-1, j-2) = 1, (i-1, j-1) = 0.
This contradicts our assumption.
So if (i, j) = 0, (i-1, j-1) = 0.
The converse:
If (i-1, j-1) = 0, then (i, j-1) = (i-1, j) = 1. So (i, j) = 0.
So if (i-1, j-1) = 0, (i, j) = 0.
Rest of the solution should be simple.
if (i-1, j-1) = 0, then (i, j) = 0 is obvious by contradiction, but how to prove the converse?
Added the converse.
May be I'm missing something but how did you get this
If (i-1, j-1) = 1, then (i, j-1) = (i-1, j) = 1. So (i, j) = 0.Sorry, that was a typo. It should be If (i-1, j-1) = 0.
Can someone explain the logic behind Bad Shuffle problem?. I tried running the algorithm given in the problem 100000 times and then finding the permutation with maximum and minimum frequency but obviously, it will barely made through the first subtask. As it seems there is propper algorithmic solution to the problem as I saw in this solution here. Can someone explain the proof of this solution.
I haven't tried yet, but I guess it can be proved by considering a graph just similar to this
Don't know the proof, but it's similar to my solution. Found out how it works after backtracking for small cases.
It reduces to a pattern finding problem. As RayPatterson said, you brute force it for for all cases from n = 1 to 8, write down the permutations which have minimum and maximum frequencies and try to find a pattern between them, that gives you a generalized solution for any n.
Not very important, but did codechef reduce the number of Indian participants getting laddus from 20 to 10?
How to solve ANDSQR ? I know that it must be solved with datastructure segment tree or something like that ,but i don't know how to use it in this task . Can someone to explain me solution?
Maximum number of set bits in a number will be 30. Hence the bitwise and value starting from any particular a[i] will change at most 30 times. Go backwards starting from any i and check where the and value (initial value = a [i]) changes . You should be able to do it in 30 iterations max. For this just keep track of the index where the the particular bit was unset for each bit . This way you will be able to find no. Of good sequences in whole array . Use segment trees to find the count of good sequences in range . If you are not clear mention which part.
thanks very much for explain to me shaanknight !
Can anyone provide the prerequisites and idea for the FCTR question ?
algmyr was kind enough to write an editorial here.
I checked the top submission for CHEFLST question . The implementation and complexity is understandable but can anyone explain how are all numbers guaranteed to picked by this algo, please . Link in Traxexeuler's reply .
That solution is wrong. The test cases are pretty weak.
The correct answer is
0 1but the code prints0.Your link is broken btw: https://www.codechef.com/viewsolution/20056532
Thanks for pointing out. If you have solved the question can you please help what is the actual solution for the question ? Is it something related to finding determinant for a matrix as it looks we need to pick up elements from every row , every column , basically what a determinant for a matrix does .
After some more investigation, about half of the 100pt submissions seem to be wrong. That's ridiculous, CHEFLST was the hardest problem!
I did not solve it myself, and now I feel sad for the people who did come up with proper solutions.
I was told that this approach is correct: https://www.codechef.com/viewsolution/20118711
Deleted. As it hurts some
What is the idea behind problem Chef and Lost Story?
Let s = 10, such that all entries of M are < 2s
Consider a matrix H whose entries are polynomials Hij = xMij. Now, if we find the permanent of this matrix under xor convolution, then the answer would be powers with non-zero coefficients. But sadly, we can't find permanent in polynomial time.
Instead, multiply each entry of H by a random integer, and find the determinant, and by Schwartz–Zippel lemma, we would get the right answer with a high probability.
To find the determinant, we can use evaluation and interpolation in a XOR-FFT fashion (considering the resultant as a multivariate polynomial in s variables, and evaluating determinant at roots of unity, (in this case, { - 1, 1}s). Overall complexity is O(n32s)
Link to solution