### Enchom's blog

By Enchom, history, 8 months ago, ,

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:

#### 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
• 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!!

• +53

 » 8 months ago, # |   +16 You promise editorials on time ??
•  » » 8 months ago, # ^ |   +77 Yeah, no
•  » » » 8 months ago, # ^ |   0 :P
 » 8 months ago, # |   +14 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.
 » 8 months ago, # |   0 seem's this long will be interesting...
 » 8 months ago, # |   +31 Please don't extend it this time .
 » 8 months ago, # |   +29 When will you add the remaining two problems to the contest? It's been almost half a day since the contest started.
•  » » 8 months ago, # ^ |   +26 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
 » 8 months ago, # |   -11 Time limits could have been less strict :\
 » 8 months ago, # |   0 Hey Enchom, you have tagged pranjalr34 instead of me. Please correct the blog, if possible. Thanks.
•  » » 8 months ago, # ^ |   +13 Apologies. Updated the blog.
 » 8 months ago, # |   +32 Codechef is celebrating double digits by maintaining a single digit number of problems
 » 7 months ago, # |   +11 Any hints for Perfect Tree Problem? Btw, Enjoyed a long challenge so much, after a long time. Nice Problems !
•  » » 7 months ago, # ^ |   +4 SpoilerThink in terms of sqrt(Square Root).
•  » » 7 months ago, # ^ |   +4 SpoilerIf 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.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   +11 SpoilerDid 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.
•  » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 7 months ago, # ^ | ← Rev. 3 →   0 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
•  » » » » » » 7 months ago, # ^ | ← Rev. 2 →   0 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)?
•  » » » » » 7 months ago, # ^ |   +19 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 $S(a, t_0, d_0, w, h) = \sum_{i=0}^{h-1} (d_0+i) \sum_{j=0}^{w-1} a^{t_0+iw+j}$(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$). Obviously, $S(a, t_0, d_0, w, h) = a^{t_0} \left( \sum_{j=0}^{w-1} a^j \right) \left( \sum_{i=0}^{h-1} (d_0 + i)(a^w)^i \right).$ 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 $\sum_{i=1}^{k} \log h_i = \log \left( \prod_{i=1}^{k} h_i \right) = \log \left(\frac1{k!} \prod_{i=1}^{k} ih_i \right) \leq -\log(k!) + k\log\left(\frac{\sum ih_i}{k}\right) \leq -k \log \frac{k}{e} + k \log \frac{n}{k} = k \log \frac{ne}{k^2}.$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.
•  » » » » » » 7 months ago, # ^ |   0 Thanks for explanation! Now I understand that my solution's complexity is also $O(\sqrt N)$ per query because of reasons you mentioned :)
•  » » » » » » 7 months ago, # ^ |   0 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...
•  » » » » » » » 7 months ago, # ^ |   +5 $a + 2a^2 + 3a^3 + \cdots + (2k-1)a^{2k-1} = (a + 2a^2 + 3a^3 + \cdots + (k-1)a^{k-1})(1 + a^k) + k a^k (1 + a + a^2 + \cdots + a^{k-1})$(You also compute $1 + a + a^2 + \cdots + a^{k-1}$ and $a^k$ at the same time.)
•  » » » » » » » 7 months ago, # ^ |   +13 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.
•  » » » » » » » » 7 months ago, # ^ | ← Rev. 2 →   +9 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)})$.
•  » » » » » » » » » 7 months ago, # ^ |   +10 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?
•  » » » » » » » » » 7 months ago, # ^ |   0 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 know that $x(1) = 0$. given $x(j)$, we can compute $x(j+1)$ in constant time (simply add $jx^j$). given $x(j)$, we can compute $x(2j)$ in constant time (using the formula I mentioned above). 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.
•  » » » » » » » » » 7 months ago, # ^ |   0 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).
•  » » » » » » » » » 7 months ago, # ^ |   0 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.
•  » » » » » » » » » 7 months ago, # ^ |   +5 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
•  » » » » » » » » » 7 months ago, # ^ |   0 I see, thanks.
 » 7 months ago, # |   +11 How to solve Sonya and Tree?
•  » » 7 months ago, # ^ |   +16 I see it is tree version of problem "seats" in IOI 2018.
•  » » 7 months ago, # ^ |   +16 My ideaLet'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: no vertex can have three colored children, no vertex can have two colored children and a colored parent, the number of vertex pairs $(v, p)$ where $p$ is the parent of $v$, $v$ is colored, and $p$ is uncolored, is exactly $1$. We can check the first two conditions by maintaining: for each vertex $v$, a set of its children sorted by their indices (and especially its second and third smallest child), for each vertex $v$, a set that for each child $c$ of $v$ stores the second smallest child of $c$. 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.
•  » » 7 months ago, # ^ |   0 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).