### kevinsogo's blog

By kevinsogo, history, 7 months ago, ,

Hello Codeforces Community,

I invite you all to join HackerRank's World Codesprint 12 starting on 14 December 2017. The contest duration is 48 hours.

The winners of the contest will win up to 1000USD cash prizes. Also, there are opportunities to win some nice hoodies.

The contest will be rated. If two persons get the same score, the person who reached the score first will be ranked higher. There will be 7 algorithmic challenges in the contest.

The problems are prepared by sreka11, krismaz, Shaikhidoshik, forthright48, muratekici, shashank21j, pkacprzak, Xsquare, extraVirgin20, Golovanov399, niyaznigmatul and myself.

Good luck, and I hope you enjoy the problems!

P.S. I hope I got all the CF handles right.

•
• +69
•

 » 7 months ago, # |   +36 As Hackerrank can't send hoodies to some countries, will people from such countries excluded from list of hoodie winners and first people with >100 rank added?
 » 7 months ago, # |   0 can anyone give me a hint on how to solve Factorial array(https://www.hackerrank.com/contests/world-codesprint-12/challenges/factorial-array) ,See just for finding the factorial of 10^9 only we would get TLE,how to approach this type of problem , should we use square root decomposition trick, I am having trouble in the range update(+1 for all l to r ) part how to do it efficiently .
•  » » 7 months ago, # ^ | ← Rev. 2 →   +4 for x ≥ 40
•  » » 7 months ago, # ^ |   0 Well, I solved it using the property that (x!%10^9) = 0 for x >= 40 . For update and query I used square root decomposition wherein for each block I maintained two things an integer for keeping track of pending range update and a map which kept track of the frequency of the element in the block. So for range update, I just incremented the pending integer. In query, I checked if the pending integer was less than 40 if no then all the elements in that block would be 0, if it was less than 40 then I only had to check the range for which the sum of the element+pending integer would be 39 which could be at most 39 checks per block. For point update, I needed to first set the pending integer to 0(Think about why?) and then updated the element and the map this took max sqrt(n) time for the update.
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 The use of map per segment is really cool.
 » 7 months ago, # |   +6 How to solve F? I solved it with Heavy-Light decomposition , but I think it has simple solution!
•  » » 7 months ago, # ^ | ← Rev. 2 →   +41 There is an solution with about 10 lines of essential code.Let's consider any rooted subtree with k vertices. For every integer x define f(x) as the minimum number of operations required to obtain the tree with vertex values nondecreasing root-to-leaves and the root value at least x. It's obvious that f(x) is nondecreasing itself and f(x) = k when x is large enough. Let's define a multiset "up": for every number x we add x to it f(x + 1) - f(x) times (for example for one vertex subtree that would be just one number equal to the number of this vertex a[v]). The answer for the problem would therefore be n minus the number of elements in up[0]. The only thing left is to do a dfs and for every vertex v get up[v] from up[u] of all its children. Not hard to see that by definition up[v] would be a union of all up[u] from which we erase a maximum number which is less than a[v]. Now if we unite these multisets small to big each time the total complexity would be . Codeint n; vector a; vector> nb; vector> up; void dfs(int v, int p) { for(auto u : nb[v]) if(u!=p) { dfs(u, v); if(up[u].size() > up[v].size()) swap(up[u], up[v]); for(auto x : up[u]) up[v].insert(x); } auto it = up[v].lower_bound(a[v]); if (it != up[v].begin()) { it--; up[v].erase(it); } up[v].insert(a[v]); } int main() { scanf("%d", &n); a.resize(n); for (int i = 0; i < n; i++) scanf("%d", &a[i]); nb.resize(n); up.resize(n); for (int i = 0; i < n-1; i++) { int u,v; scanf("%d %d", &u, &v); u--, v--; nb[u].push_back(v); nb[v].push_back(u); } dfs(0, 0); cout << n-up[0].size(); } 
•  » » » 7 months ago, # ^ | ← Rev. 2 →   0 Nice trick — change values and states of dp! I had to write ~200 lines of code to handle these requests with treap :/
 » 7 months ago, # |   0 How to solve Breaking Sticks ?Problem Link
•  » » 7 months ago, # ^ |   0 //sorry for my poor EnglishSolve each a_i independently Now, assume that we are solving a_i = x First, get all the factors of x first. This spend O(sqrt(MAX(a_i))) . Then, we can solve it with dp dp[i] means the best answer for solving a stick which has length i, initially, dp[1] = 1We can get the transform: dp[i] = max( dp[j]*(i/j) + 1, for all j such that i%j==0 and i!=j )This spend about O( (factor of x)^2 ) times
•  » » » 7 months ago, # ^ |   +10 you dont need dp, just greedily choose the largest prime factor.
•  » » 7 months ago, # ^ |   0 Just find the largest factor of the given number. We can use the property that factors come in pairs so for finding the largest factor we can find the smallest one and then divide the number by that. Do that until we reach 1 and at each step just add the largest one to the answer.
•  » » 7 months ago, # ^ |   0 for 12=2*2*3;in increasing order ans=6(1+ 1/2+ 1/(2*2)+ 1/(2*2*3))
 » 5 months ago, # |   +10 It's almost been 2 months, any news about prizes?