Hello Codeforces Community!!!
I invite you all to take part in HackerEarth's February Easy contest.The contest will be held on 1st February, 2018 at 22:00 IST.
Problems have been set by me(sinhashubham95) and tested by r3gz3n and harshil.We are grateful to HackerEarth admin r3gz3n for his help.
You will be given 5 algorithmic problems to solve in 3 hours. Partial scoring will be used (you get points for passing each test case). Although the contest is targeted towards beginners, we hope even experienced problem-solvers find one or two problems to be interesting. The contest is rated and prizes will be awarded to the top 3 beginners(i.e. Programmers with a rating of 1600 or less before the challenge starts.
This contest is themed on Naruto and dedicated to my friends rajatanand and hjjobs.
Good luck and have fun.
Update 1 : Close to 7 hours left in the contest.
Update 2 : The contest has started. All the best !!
Can someone explain 'The Great Ninja War' ?
In particular, the dp states.
In the fourth question, how are we using lazy propagation for p >1 ?
Let's say we are working with the segtree responsible for pth powers. Suppose a particular node is responsible for the sections [L,R] and x is the value by which we want to increase all values of this range. Then this node already has the sum A[L]p + A[L + 1]p...A[R]p. Now we want to update it so as to become (A[L] + x)p + (A[L + 1] + x)p...(A[R] + x)p. If we open the latter expression by binomial theorem and subtract the first expression, we get the value that needs to be added to this node to account for the corresponding update. That value after some rearrangement can be written as
We can notice that the term within sigma will already be available in same ranges in other segment trees (ie maintained for different powers) Therefore this node can be updated in at max 10 steps. Since there can be log(N) disjoint nodes and 10 segtrees to update our update complexity is around 10 * 10 * log(N)
For each problem, theres a well written editorial in the Editorial tab in the problem statement page. For any queries to the solution of the problem, you can refer to that.
Yeah, I referred to the editorial. I can not understand the solution to the third problem. Can you elaborate on the DP states?
I don't understand the significance of using the LCM.
Because we don't need more information. The problem ask us to check the divisibility of the special sum for every digit of the troop number, i.e., only from 1 to 9. We don't need to check the divisibility for numbers higher than these. Thats why we only pass the sum%LCM in the state.
But does 2520 help in checking whether the sum is special or not? What if, the special sum doesn't involve all the numbers from 1..9? For example, if the number is 2024. In this case, the sum will be 264, which is not divisible by 2520, even though the troop is special.