Greetings Codeforces Community! We invite you to experience the monthly CodeChef Lunchtime for December. The 3-hour contest will offer 5 challenging problems to solve. It will be a great way to close this year on a happy note with your increased ratings!
The problem statements of the contest will be available in English, Hindi, Bengali, Russian, Mandarin, and Vietnamese. Also, if you have some original and engaging problem ideas, and you’re interested in them being used in the CodeChef's contests, you can share them here: www.codechef.com/problemsetting/new-ideas.
I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
Setters: Nguyen Ngoc Trung (chemthan), Rami Alssadaqa (i_love_islam), Hasan Jaddouh (kingofnumbers)
Tester: Roman Bilyi (RomaWhite)
Statement Verifier: Jakub Safin (Xellos)
Mandarin Translator: Gedi Zheng (gediiiiiii)
Vietnamese Translator: Team VNOI (Songuku95)
Russian Translator: Fedor Korobeinikov (Mediocrity)
Bengali Translator: Mohammad Solaiman (solaimanope)
Hindi Translator: Akash Srivastava (devils_code)
Contest Details:
- Start Date & Time: 28th December 2019 (1730 hrs) to 28th December 2019 (2230 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
- Contest link: www.codechef.com/LTIME79
- 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 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here.
Good Luck!
Hope to see you participating!!
Happy Programming!!
Probably you have wrong date on timezone link :)
Thanks
Hoping for balanced problemset this time!!
How to solve tree query problem ?
My $$$O(Q \log^3 {N})$$$ solution got AC, not sure if that's intended.
The problem asks you to print the weighted centroid of the tree after each query.
Build a new tree resembling the centroid decomposition of the original tree(where every node has weight 1), when answering a query we look at the root of the new tree, if it's the answer we print it, otherwise we go to the child with maximum subtree weight(child with subtree weight greater than half of total tree weight to be precise) and repeat until we get to the answer.
To know which child has the maximum subtree weight fast, we do binary search on the children and store the sum of weights in a segment tree using dfs numbering.
The intended solution is $$$O(Q \log^2N)$$$, but the idea is completely the same.
Just part with the computing child could be done in $$$O(\log N)$$$. You can do descent in segment tree to find the node where the sum becomes greater that a half and then binary search in which subtree this node lies.
Actually, yours is $$$O(Qlog^2N)$$$. Because first time you search on at most $$$N - 1$$$ children. Then next time you search on at most $$$\frac{N}{2}$$$ children, then $$$\frac{N}{4} + 1$$$ children, and so on. Also, you can try using Fenwick Tree and enjoy running time.
But isn't the summation close to:
Yes. You are right. I had a mistake in estimating it. :(
It's a better constant, at least.
How to solve STICK2 partially ?
Use dp with states as number of sides,sum of sides and maximum side taken. for it to be a polygon the condition sum_of_sides>2*max_side_taken mast be satisfied!!
I was using dp with 4 states the position I am at,number of sides,sum of sides and maximum side taken. How can we optimise the first state.
number of sides is not required because the condition sum_of_sides>2*max_side_taken will never be satisfied for n<=2!! So it is not required to take number of sides as states!!
How to solve STICK2?
The problem reduces to "given n, how many subsets of {1, 2, ..., n-1} sum to > n".
We can, instead, calculate how many subsets of {1, 2, ..., n-1} sum to <= n.
That is actually just (the number of sets of increasing numbers with sum <= n)-1 since we subtract the set {n}.
We can calculate the number of sets of increasing numbers with sum <= n with a standard dp[k][n] = number of k element sets having a sum of n. Note that k < sqrt(n).
(The above snippet is from your submission)
While I can observe that the above loop computes dp[k][n] as mentioned in the last line of your comment, I still miss the intuitive for the recurrence in the code.
What would it be in words? or intuitively?
I tried putting it in words, but it does feel a little odd.
(# of k element subsets having sum n) = (# of k-1 element subsets having sum n-k) + (# of k element subset having sum n-k)
From $$$dp[i][j]$$$ you can either go to $$$dp[i][j + i]$$$ which means increase every element by 1, or you can go to $$$dp[i + 1][j + i + 1]$$$ which is add a new element that's equal to 0, then increase every element by 1
http://mathworld.wolfram.com/PartitionFunctionQ.html
Study here how to do distinct partition of any integer n in sqrt(n) time.... then the recursion is ans[n] = ans[n-1] + 2^(n-1) — (number of ways to write all numbers <=n as a sum of distinct integers)