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.

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?

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 .

for

x≥ 40Well, 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.

The use of map per segment is really cool.

How to solve F? I solved it with Heavy-Light decomposition , but I think it has simple solution!

There is an solution with about 10 lines of essential code.

Let's consider any rooted subtree with k vertices. For every integer

xdefinef(x) as the minimum number of operations required to obtain the tree with vertex values nondecreasing root-to-leaves and the root value at leastx. It's obvious thatf(x) is nondecreasing itself andf(x) =kwhenxis large enough. Let's define a multiset "up": for every numberxwe addxto itf(x+ 1) -f(x) times (for example for one vertex subtree that would be just one number equal to the number of this vertexa[v]). The answer for the problem would therefore benminus the number of elements inup[0]. The only thing left is to do a dfs and for every vertexvgetup[v] fromup[u] of all its children. Not hard to see that by definitionup[v] would be a union of allup[u] from which we erase a maximum number which is less thana[v]. Now if we unite these multisets small to big each time the total complexity would be .CodeNice trick — change values and states of dp! I had to write ~200 lines of code to handle these requests with treap :/

How to solve Breaking Sticks ?

Problem Link

//sorry for my poor English

Solve 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] = 1

We 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

you dont need dp, just greedily choose the largest prime factor.

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.

for 12=2*2*3;in increasing order ans=6(1+ 1/2+ 1/(2*2)+ 1/(2*2*3))