We invite you to participate in CodeChef’s Starters 86, this Wednesday, 19th April, rated for all.
Time: 8:00 PM — 10:00 PM IST
Note that the duration is 2 hours. Read about the recent CodeChef changes here.
Joining us on the problem setting panel are:
Setters: Satyam satyam343
Statement Verifier: Kanhaiya notsoloud1 Mohan
Video Editorialists: Sundar K Letscode_sundar, Madhav jhamadhav Jha, Suraj jhasuraj01 Jha, Jwala jwalapc, Rohit ezo_tihor Oze
Text Editorialists: Nishank IceKnight1093 Suresh
Contest Admins: Satyam satyam343
Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest.
The video editorials of the problems will be available for all users for 1 day as soon as the contest ends, after which they will be available only to Pro users.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Hope to see you participating. Good Luck!
UPD:
I hope you liked the problems!!
Congratulations to the winners of Div 1!
I liked solving the problems and hopefully you all will also like the problems
omg satyam343 round
what exactly does "contest admin" mean? I've seen a lot of different contest admins for CodeChef in the starters announcements. Is the contest admin the person who writes the round?
they manage everything like a manager
PREFIXMAX is a mastapeece!
LEASTSIZE: we can make min score always 1 by choosing centroid. Is this idea Right or Wrong?
Yep, right.
Thanks. With 5 more min, I can complete my implementation. Again a bad contest :'(
https://www.codechef.com/problems/TREESAREFUN is an interesting problem. You have to observe that $$$\sum F_i = N$$$ implies that $$$F_i$$$ can take at most $$$\sqrt N$$$ distinct values. I have used this idea with small to large merging in my solution
Your solution isn't really intended, unfortunately I don't believe it came up while testing and so there weren't any tests against it ($$$N = 10^6$$$ should be an indication that $$$\mathcal{O}(N\sqrt{N})$$$ probably isn't intended :))
The intended solution is plain $$$\mathcal{O}(N\log N)$$$ with DFS and a segment tree, and is imo quite neat.
Well, I didn’t use this fact and coded the standard merge small to large. To avoid divisions, I have a segment tree to find the product of all numbers. Adding/removing a number is handled by recalculating the value of the leaf where this value is represented.
My solution has complexity $$$\mathcal{O}(n\cdot \log(n)^2)$$$. To be honest, I coded it only because there was not enough time to think about optimizations. I expected an obvious TLE, and I was a bit surprised when I saw it was accepted.
is it possible to solve Largest Y using binary search?
I think it is binary lifting.