deva2802's blog

By deva2802, history, 5 weeks ago, ,

Greetings Codeforces community! You are all invited to CodeChef’s February Cook-Off sponsored by ShareChat. The Cook-Off is a short contest that lasts 2.5 hours and features 5 problems for you to try and solve. The contest problem statements are available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

ShareChat — India’s fastest growing social network is offering exciting jobs and internships to the participants of the Cook-Off. Visit the contest link for more details.

I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

• Editorialist: Deadwing (Hussain Kara Fallah)
• Statement Verifier: Xellos (Jakub Safin)
• Setters: kingofnumbers (Hasan Jaddouh), deva2802 (Devanshu Agarwal), pi-nan (Shivam Gor), Abhinav Jain
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: Team VNOI
• Russian Translator: Fedosik (Fedor Korobeinikov)
• Bengali Translator: solaimanope (Mohammad Solaiman)
• Hindi Translator: Akash Shrivastava

Contest Details:

• Start Date & Time: 17th February 2019 (2130 hrs) to 18th February 2019 (0000 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: https://www.codechef.com/laddu
(For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck!
Hope to see you participating!!
Happy Programming!!

•
• +68
•

 » 5 weeks ago, # |   +22 The contest starts in 3.5 hours
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by deva2802 (previous revision, new revision, compare).
 » 5 weeks ago, # |   +12 How do you solve EVILAND?
 » 5 weeks ago, # | ← Rev. 4 →   +3 How to solve Evil Land?My solution: find the periodicity of F (i.e. ) then get the LCM of the periodicity of each Ai. Finally, remove elements from A which have (in their periodicity) a prime with power larger than the power of the same prime in the periodicity of F (try for each prime in F).This gave TLE because I find the periodicity in for each number.
•  » » 5 weeks ago, # ^ |   +16 Why does taking the LCM help? I'm not able to understand what's going on.
•  » » » 4 weeks ago, # ^ | ← Rev. 5 →   0 If a number X has a periodicity P on a modulo M then Xi will equal all numbers Y such that Y has a periodicity Q where Q is a divisor of P. If two numbers a and b have a periodicity Pa and Pb then has a periodicity of LCM(Pa, Pb).So the problem is now to remove some elements of A such that the LCM of their periodicity of the remaining is not a multiple of the periodicity of F.To prove that, let X be a number which has a periodicity P and Xi equals Y which has a periodicity of Q. Then . Then , which means that Q is a divisor of P. Remember that both P and Q are divisors of M - 1 because Xφ(M) = 1.
 » 5 weeks ago, # |   0 When will the problems be available for practice?
 » 5 weeks ago, # | ← Rev. 3 →   +8 EVILAND: g(x, MOD) = periodicity of x in mod MOD. Make a[i] = g(a[i], MOD) and now the problem is removing some elements so that the lcm of the remaining elements isn't a multiple of g(F, MOD). Didn't submit because I started the contest in the last hour but I'm pretty sure this is correct. To prove this, transform multiplication to addition with a primitive root and the problem is the same but with addition.How to solve TWOARR without persistent implicit treap or lazy updates with persistent seg tree? I solved it using lazy update with persistent seg tree but my constant was complete shit and it barely passed the TL with log^2 updates/queries.
•  » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I did the same in EVILAND but got TLE.For TWOARR: sqrt-decomposition passed in ~2seconds
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +16 You can preprocess the primes and find periodicity in log^2 like this int getId(int x, int MOD) { if(x == 0) { return 1; } int ans = MOD - 1; for(auto p : primes[MOD-1]) { while(ans % p == 0 && fexp(x, ans / p, MOD) == 1) { ans /= p; } } return ans; } It solves each case in O(N*log^2).
•  » » 5 weeks ago, # ^ |   +16 Setter code for TWOARR was n*log^2 . It passes in 1.8sec. There exist sqrt deco solutions too.
•  » » » 5 weeks ago, # ^ |   0 How would you handle the queries using sqrt decomposition? especially the query of the first type.
•  » » » » 5 weeks ago, # ^ |   +5 Decompose array A, into root(n) blocks, then every query of type two can be handled in O(root(n)logn), using a flag to rebuild a block. For this we need to maintain a persistent seg tree on B. adjusting the Block size gives O(nroot(nlogn)) solution.
•  » » » » » 5 weeks ago, # ^ |   0 Yeah. Thought the same. just idea of persistent to handle the update of the value of b slipped out of my mind. Thanks.
•  » » » » » » 5 weeks ago, # ^ |   +3 what is persistent st?
•  » » » 5 weeks ago, # ^ |   +8 Thanks for the problem, got my lazy ass to finally code persistent random BST. https://www.codechef.com/viewsolution/23140693 O(N * logN) expected time solution.
•  » » » » 5 weeks ago, # ^ |   0 hey u coded treap . whats the difference between persistance tree and treap are both same
•  » » » » » 5 weeks ago, # ^ |   0 They aren't. Persistent treap doesn't really work because expected height breaks when you merge a treap with itself (due to how priorities work in treaps) but you can use a different randomization during merge (that I really can't explain why it works other than it makes every node have the same probability of being the root in a subtree). This different randomization is leftSide function in my code, I think you can't call this a treap anymore since it doesn't have heap properties.
•  » » » » » » 5 weeks ago, # ^ |   0 ok
 » 5 weeks ago, # | ← Rev. 2 →   +10 For EVILAND I found primitive root and all its degrees, and sorted that information, that allows to find the discrete log for each number in O(1), giving MlogM + N overall, which passed for me
•  » » 5 weeks ago, # ^ |   -8 what is primitive root. and what is discrete log
•  » » » 5 weeks ago, # ^ |   +4 I don't know, I just googled it!
•  » » » » 5 weeks ago, # ^ |   +3 ok
 » 4 weeks ago, # |   +13 Almost a week since the contest and I still can't find the EVILAND editorial.