### Cache's blog

By Cache, history, 19 months ago, ,

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: Fedosik (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.).

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 winners@codechef.com). 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!!

• +111

 » 19 months ago, # |   0 Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).
 » 19 months ago, # |   0 I hope no one solves the last question. :P
•  » » 19 months ago, # ^ |   0 Hope for something better. ;P
 » 19 months ago, # |   0 How to solve TAB GAME subtask 2, (with proof )
•  » » 19 months ago, # ^ | ← Rev. 7 →   +3 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.
•  » » » 19 months ago, # ^ |   0 if (i-1, j-1) = 0, then (i, j) = 0 is obvious by contradiction, but how to prove the converse?
•  » » » » 19 months ago, # ^ |   0 Added the converse.
•  » » » » » 19 months ago, # ^ |   0 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.
•  » » » » » » 19 months ago, # ^ |   0 Sorry, that was a typo. It should be If (i-1, j-1) = 0.
 » 19 months ago, # |   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.
•  » » 19 months ago, # ^ | ← Rev. 3 →   0 I haven't tried yet, but I guess it can be proved by considering a graph just similar to this
•  » » 19 months ago, # ^ |   0 Don't know the proof, but it's similar to my solution. Found out how it works after backtracking for small cases.
•  » » 19 months ago, # ^ |   0 It reduces to a pattern finding problem. As DrumpfTheGodEmperor 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.
 » 19 months ago, # |   +8 Not very important, but did codechef reduce the number of Indian participants getting laddus from 20 to 10?
 » 19 months ago, # |   0 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?
•  » » 19 months ago, # ^ |   0 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.
•  » » » 19 months ago, # ^ |   0 thanks very much for explain to me shaanknight !
 » 19 months ago, # |   0 Can anyone provide the prerequisites and idea for the FCTR question ?
•  » » 19 months ago, # ^ |   +3 algmyr was kind enough to write an editorial here.
 » 19 months ago, # | ← Rev. 5 →   +5 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 .
•  » » 19 months ago, # ^ | ← Rev. 3 →   +20 That solution is wrong. The test cases are pretty weak. 1 3 0 0 0 0 0 1 0 1 0 The correct answer is 0 1 but the code prints 0.Your link is broken btw: https://www.codechef.com/viewsolution/20056532
•  » » » 19 months ago, # ^ | ← Rev. 2 →   +2 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 .
•  » » » » 19 months ago, # ^ |   +18 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
•  » » » » » 19 months ago, # ^ | ← Rev. 2 →   -6 Deleted. As it hurts some
 » 19 months ago, # |   +2 What is the idea behind problem Chef and Lost Story?
•  » » 19 months ago, # ^ |   +65 Let s = 10, such that all entries of M are  < 2sConsider 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