Greetings Codeforces community!
This March, CodeChef is celebrating 10 years of cooking delicious problems and I would like to invite you all to participate in the March Long Challenge, sponsored by ShareChat. The long challenge is a 10-day long contest with 8 problems for you to solve. This month, there are some additional birthday gifts up for grabs! For more details, head over to the contest page now!
ShareChat — India’s fastest growing social network is offering internship and job opportunities to participants of March Long Challenge. The contest and job opportunities are open to programmers across the globe and problem statements will be available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese. Visit the contest link to know more.
I hope you will join your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:
- Admin: teja349 (Teja Vardhan Reddy)
- Tester: Enchom (Encho Mishinev)
- Editorialist: taran_1407 (Taranpreet Singh)
- Statement Verifier: Xellos (Jakub Safin)
- Setters: Abhinav Jain, adityad1998 (Aditya Dimri), aleex (Alexey Filinovich), Dalgerok (Andrew Orap), Ashishgup (Ashish Gupta), danya.smelskiy (Danya Smelskiy), kingofnumbers (Hasan Jaddouh), mgch (Misha Chorniy), KUMAR_PRANJAL_RAI (Pranjal Rai), Wild_Hamster (Volodymyr Mykytsei), yashChandnani (Yash Chandnani)
- Russian Translator: Mediocrity (Fedor Korobeinikov)
- Mandarin Translator: huzecong (Hu Zecong)
- Vietnamese Translator: Team VNOI
- Bengali Translator: solaimanope (Mohammad Solaiman)
- Hindi Translator: Akash Shrivastava
Contest Details:
- Start Date & Time: 1st March 2019 (1500 hrs) to 11th March 2019 (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone
- Contest link: https://www.codechef.com/MARCH19
- 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. First to solve each problem except challenge — 100 laddus. 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!!
You promise editorials on time ??
Yeah, no
:P
Oh no, the new admin is my archnemesis teja[some numbers]!
The organization took over codechef, but don't worry the mad sp Hououin Riela will protect cf.
seem's this long will be interesting...
Please don't extend it this time .
When will you add the remaining two problems to the contest? It's been almost half a day since the contest started.
Before the contest ends.
P.S. — In case they fail to follow this deadline. They will extend the contest. So, that they can meet this deadline. :P
Time limits could have been less strict :\
Hey Enchom, you have tagged pranjalr34 instead of me. Please correct the blog, if possible. Thanks.
Apologies. Updated the blog.
Codechef is celebrating double digits by maintaining a single digit number of problems
Any hints for Perfect Tree Problem? Btw, Enjoyed a long challenge so much, after a long time. Nice Problems !
Think in terms of sqrt(Square Root).
If sum of some values is n, then number of distinct values can be atmost O($$$\sqrt{n}$$$)
Though, I found TL of this problem too strict.
Did you have $$$O(\sqrt{n})$$$ or $$$O(\sqrt{n} \log n)$$$ time complexity per query? I had no problems getting the former accepted.
I got really angry at the TL in the Sonya and Tree problem, though.
How to solve in $$$O(\sqrt N)$$$ per query? I somehow manage to squeeze $$$O(\sqrt N log(N))$$$, but it was hard enough and as far as I understand such solutions shouldn't pass.
Basically u need to calculate some powers and some sums of gps rootn times. U can calculate power in O(1) by precomputing. Like if u precompute all powers a^x and a^1000x for x<=1000 then a^y = a^(y/1000)*a^(y%1000) For the gp thing, basically what u get is Sum of gp with r = a^x and n = y. You can use the sum of gp formula but inverse will be log(1e9+7) or calculate gp in log(y) where y is very small and if you do some complexity analysis, u'll realize its ammortized O(1) See my code — https://www.codechef.com/viewsolution/23391726
How does a^y = a^(y/1000) * a^(y%1000)? Also, can you explain how you compute the gp in O(1)?
Edit: Did you mean (a^1000)^(y/1000) * a^(y%1000)?
Say you have blackboxes which can compute $$$a^k$$$, $$$1+a+a^2+\cdots+a^{k-1}$$$, $$$a+2a^2+3a^3+\cdots+(k-1)a^{k-1}$$$ in $$$O(\log k)$$$ time for any $$$a, k$$$ (it's a pretty straightforward binary lifting).
After $$$O(n \sqrt{n})$$$ preprocessing, each query boils down to computing the sum of $$$O(\sqrt{n})$$$ values of the form
(the number of vertices is non-decreasing at consecutive heights; each S corresponds to the interval of $h$ consecutive heights where this number is equal to $$$w$$$).
Compute the sums from top to bottom. Say that we computed $a^{t_0}$, $$$a^w$$$ and $$$\sum_{j=0}^{w-1} a^j$$$ from the higher layer. Then $$$a^{t'_0} = a^{t_0} (a^w)^h$$$, $$$a^{w'} = a^w \cdot a^{\Delta w}$$$, $$$\sum_{j=0}^{w'-1} a^j = \sum_{j=0}^{w-1} a^j + a^w \left(\sum_{j=0}^{\Delta w - 1} a^j\right)$$$. Using all these formulas, we can update the values above and compute a single term $$$S$$$ in $$$O(\log h + \log (\Delta w))$$$ time.
Let's prove this gives us $$$O(\sqrt{n})$$$ time per query. Now, I think there should be a couple of simpler ways to do it, but let's do it my way. We compute $$$S$$$ for a series of values $$$(w_1, h_1), (w_2, h_2), \dots, (w_k, h_k)$$$ such that $$$w_i < w_{i+1}$$$ and $$$\sum w_i h_i \leq n$$$. As $$$w_i \geq i$$$ and $$$h_i \geq 1$$$, we get that $$$\sum_{i=1}^{k} i h_i \leq n$$$ and $$$\sum_{i=1}^{k} i \Delta w_i \leq n$$$. Using AM-GM inequality, we get that
One can optimize the function in the end to see that the maximum is attained at $$$k \approx O(\sqrt{n})$$$, giving $$$O(\sqrt{n})$$$ time complexity. Exactly same bound can be produced for $$$\Delta w$$$'s.
Thanks for explanation! Now I understand that my solution's complexity is also $$$O(\sqrt N)$$$ per query because of reasons you mentioned :)
I got all of this except for one thing: how do you compute $$$a+2a^2+3a^3+...+(k-1)a^{k-1}$$$ in $$$O(\log k)$$$? More specifically, how do you avoid computing the modular inverse of $$$a-1$$$, which takes $$$O(\log(mod)) = \log(10^9)$$$? This modular inverse is the bottleneck which is causing me TLE...
(You also compute $$$1 + a + a^2 + \cdots + a^{k-1}$$$ and $$$a^k$$$ at the same time.)
This inverse was also the bottleneck in my solution (everything else was O(1) per "step" — by step I mean group of consecutive levels in the subtree having the same number of vertices). I used a very simple fix: if k is small (<= 20), just compute the sum in O(k) time :) Otherwise just use the usual logic (which involves computing the inverse). That was enough to pass the test cases. I'm not sure if they were just weak or there can be some proof behind it (no time to think about proofs — I barely had time to compete at all).
But computing the sum in O(log(k)) is much more elegant. I even remember using this "trick" in the past for some similar types of sums, but I didn't think about it this time.
You could have avoided the inverse simply by cancelling it out with numerator in sum of GP. And Your Solution is $$$O(\sqrt{Nlog(MOD)})$$$. Most of these solutions would have failed if test cases were strong. But you could have further improved on this if you maintain inverse for small values (say till 1e7). Than the complexity reduces to $$$O(\sqrt{Nlog(100)}) $$$.
Does it cancel out though? The expression I have is:
$$$1 + 2a + 3a^3 + ... + ka^{k-1} = \frac{ka^{k+1} - (k+1)a^k + 1}{(a-1)^2}$$$
Since the inverse is squared in the denominator, it doesn't fully cancel out with the term in the numerator of the GP. Is there a different expression such that it cancels?
You don't need to produce the closed form. I'm computing $$$x(k) = a + 2a^2 + 3a^3 + ... + (k-1)a^{k-1}$$$ using some kind of binary lifting:
We need to simultaneously compute $$$y(k)=1+a+a^2+...+a^{k-1}$$$ and $$$z(k)=a^k$$$ in a similar fashion to achieve the constant time transitions. This enables us to compute any $$$x(k)$$$ in $$$O(\log k)$$$ time.
Yes, exactly. That's the form I also used. I cancelled out one (a-1)^(-1) (actually I replaced it by the inverse of (y-1), where y is the argument of the query — this inverse is computed only once per query, so it's fine). But I couldn't cancel out the 2nd one. So, as I said, when k is small, I just computed the sum directly in O(k) time instead of using the formula which required the computation of (a-1)^(-1).
Yes, I understand your method and I've gotten AC with it. Thanks for the help!
I'm now trying to understand what appears to be a simpler solution where the modular inverse cancels out in the closed form. I don't see how it works though.
Sorry, I didn't meant that you wont need binary lifting. As you said you can cancel out one power. Then you are left with $$$ka^{k}-ka^{k-1}-\sum_{i=0}^{k-1} a^{i} $$$. You will still need binary lifting but now problem reduces to calculating sum of GP (instead of AGP) in $$$O(logk)$$$ instead of $$$O(k)$$$. You can also compute the sum of AGP directly in $$$O(logk)$$$ as already mentioned
I see, thanks.
How to solve Sonya and Tree?
I see it is tree version of problem "seats" in IOI 2018.
Let's solve the easy subproblem first (the tree is a path; a path rooted at one of its ends). Consider the following process: say that all vertices are uncolored first. Then paint all vertices blue in the increasing order of their indices. Throughout the process, maintain the number of pairs $$$(v, p)$$$ of vertices where $$$p$$$ is parent of $$$v$$$, $$$v$$$ is colored, and $$$p$$$ is uncolored. (For simplicity, assume that the root has an artificial parent that stays uncolored forever.) Then each beautiful path will become the set of the colored vertices exactly once during the process. We therefore need to count the number of moments of time when the set of the colored vertices is a path. This happens when the number of pairs described above is exactly $$$1$$$.
For any two connected vertices $$$(v, p)$$$ where $$$p$$$ is the parent of $$$v$$$ (possibly an artificial one), the number of pairs above is increased by one exactly when $$$p$$$ is colored and $$$v$$$ is not; that is, it happens if $$$v < p$$$, and the number of pairs is increased for $$$\mathrm{time} \in [v, p-1]$$$. Note also that at any (positive) moment of time, the number of such pairs is always at least $$$1$$$.
Build a segment tree over the moments of time (disregard the queries at the moment), keeping in each base node the minimum possible number of pairs $$$(v, p)$$$ in the time interval, and the number of time points where such minimum is attained. Then the number of beautiful paths is the number of times the minimum number of $$$(v, p)$$$ pairs is attained in the $$$[1, n]$$$ time interval.
--- Now, say the tree is not a path anymore, but each vertex degree is limited. One can see that the set of colored vertices is a path if and only if all the following conditions hold:
We can check the first two conditions by maintaining:
This is pretty nasty to maintain, but it's doable (and possible to update in logarithmic time, independently on the degree vertex). The third condition is then checked by exactly the same segment tree as above, in $$$O(\max \mathrm{deg} \cdot \log n)$$$ time: when a vertex label changes, simply consider all adjacent pairs of vertices.
--- Now assume the tree is arbitrary. The only thing we need to fix is the number of updates in the segment tree. To do that, notice that we don't need to maintain the information for all adjacent pairs of vertices; third, fourth, etc. smallest child of any vertex can be simply disregarded as they already fail the first condition above. Therefore, we only count the number of vertex pairs $$$(v, p)$$$ where $$$p$$$ is the parent of $$$v$$$, $$$v$$$ is colored, $$$p$$$ is uncolored, and $$$v$$$ is the smallest or the second smallest child of $$$p$$$.
This is enough to do all the updates in $$$O(\log n)$$$ time.
I had a solution which ran in O(sqrt(N)) time per query/update (even in the case of general trees). For general trees it was O(deg) for "light" vertices (deg <= sqrt(N)) to perform some updates, and then had some special logic for "heavy" vertices (deg > sqrt(N)). The hardest case for my solution was when one "light" vertex had many "heavy" neighbors and the swaps involved such a light vertex and a heavy vertex. However, surprise-surprise, none of the large test cases had any heavy vertices! So you could just recompute the minimum and 2nd minimum neighbor of each updated vertex in O(deg) time (because deg was always <= sqrt(N) in the official large test cases).