Hello Codeforces Community!!!

I invite you all to take part in HackerEarth's January Easy contest.The contest will be held on 1st January,2018 at 22:00 IST.

Problems have been set by me(shubhamgoyal__) and tested by MiteshAgrawal.We are grateful to HackerEarth admin prat33k 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).

Good luck and have fun.

UPDATE1: Close to 3 hours left in the contest.

UPDATE2: Contest has started.

I was trying to solve this problem which recently appeared in a hackerrank contest. The editorial mentions a solution based on geometric interpretation of the question.But since a lot of tree path questions can be done using centroid decomposition,does anyone know how to solve it using centroid decomposition?

Can someone please help me out with this problem.
problem link
I saw a few accepted solutions and I'm guessing that the expected complexity is n*sqrt(n).

Can someone please explain how to approach this problem using centroid tree decomposition. Problem Link-> https://www.codechef.com/problems/BTREE

Can someone please explain how to solve this problem https://www.hackerearth.com/march-clash-15/algorithm/counting-on-tree-1/description/ using centroid tree decomposition.

Can someone please explain the suffix array approach to this problem: http://www.spoj.com/problems/MINMOVE/

Can someone please help me out with this problem. https://www.codechef.com/TCFST13/problems/TCFST05 My aprroach: I was thinking of a dp approach..dp[i][0] would denote expectation value obtained from first i shots given we miss the ith shot...dp[i][1] is defined similarly but this time we hit the ith shot. dp[i][0]=dp[i-1][0]+dp[i-1][1]. dp[i][1]=p[i]*(1-p[i-1])+dp[i-2][0]+dp[i-2][1]+p[i]*p[i-1]*(1-p[i-2])*2*2+dp[i-3][0]+dp[i-3][1]+p[i]*p[i-1]*p[i-2]*(1-p[i-3])*3*3+dp[i-4][0]+dp[i-4][1]...so on.. I am not able to figure out how to calculate dp[i][1] in O(n) time.. Please Help.

Can somebody please help me out in this problem https://www.codechef.com/CDWR2014/problems/CW2/ My approach: Consider any number i.We can calculate its contribution in final sum.There are n-i numbers bigger than i.We choose any j of them and arrange them before i and rest (n-j-1) numbers are arranged after i. Thus the formula: This sum can then be divided by n!. I saw a few AC codes and somehow people have reduced it to sum of harmonic series,however Im not able to reduce my formula further. Can somebody please help!!.

Can somebody please explain how to use the Möbius function to solve this problem. https://www.hackerrank.com/contests/w3/challenges/gcd-product