Hello CodeForces Community!

I would like to invite you all to the mirror contest of ACM-ICPC Asia — Kolkata Onsite Mirror Contest ACM-ICPC Asia — Kolkata Onsite Mirror Contest. For those who are prepping for the ICPC onsite regionals this would be a perfect platform to practice as it would simulate the real onsite contest.

**Contest Details**

**Time:** 27th December 2016 (1100 hrs) to 27th December 2016 (1600 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

**Contest link:** https://www.codechef.com/KOL16MOS

**Registration:** You just need to register as a Team on CodeChef. Those who are interested and do not have a CodeChef handle are requested to register in order to participate.

Good Luck! Hope to see you participating!!

Note: The mirror contest will run in parallel to the main contest with an hour delay.

That time you linked is start of mirror, not the start of main contest, right?

yes, of the mirror.

Gentle reminder!! 10 minutes to go!!

That G should be easily doable using binary search + numerical integration, right? That function will behave really good, I think, so I wouldn't expect any problems.

Yes, that's how I implemented it, and it passed without problems. Although, the author's solution isn't bisection, but probably something more high-tech.

Can someone please describe the solutions to problem L (Optimal BST revisited) and problem E (Divide me please)?

For problem E (Divide me please):

Any number N with digits n

_{k}n_{k-1}...n_{1}n_{0}can be written as n_{0}+ (n_{1}* 10^{1}) + ... + (n_{k-1}* 10^{k-1}) + (n_{k}* 10^{k})For any prime p, if we take N (mod p) then for p to be 1-sum:

10 ≡ 1 (mod p)because then the number simply becomes n_{0}+ n_{1}+ ... + n_{k-1}+ n_{k}(mod p)Similarly for p to be 1-altersum:

10 ≡ -1 (mod p)because then the number becomes n_{0}- n_{1}+ n_{2}...- n_{k-1}+ n_{k}(mod p)Generalizing the above, for any p to be

x-sum: 10^{x}≡ 1 (mod p)x-altersum: 10^{x}≡ -1 (mod p)So, we need to find minimum x such that 10

^{x}≡ 1 (mod p) OR 10^{x}≡ -1 (mod p)Now by Fermat's little theorem,

aso we need to find the least divisor of (p-1) which satisfies any of the above two equations. (It can be proven that the answer will always be a divisor of (p-1)).^{p-1}≡ 1 (mod p)Please explain how to prove that the answer will always be a divisor of p-1

You can prove it by contradiction. Assume that x is not a divisor of (p-1) but it satisfies any of the two equations. Since x is minimum value satisfying the equation therefore 10

^{i}≢ 1 (mod p) AND 10^{i}≢ -1 (mod p) ∀ 1 ≤ i ≤ (x-1)You can write (p-1) as qx + r where q is quotient when (p-1) is divided by x and r is remainder (0 < r < (p-1)). Therefore, 10

^{(p-1)}= 10^{(qx + r)}= 10^{qx}* 10^{r}Depending on value of 10

^{x}and q,10

^{qx}* 10^{r}≡ 1 * 10^{r}(mod p) OR10

^{qx}* 10^{r}≡ -1 * 10^{r}(mod p)Since, 10

^{r}≢ 1 (mod p) AND 10^{r}≢ -1 (mod p), the terms will never be equal to 1 (mod p). That contradicts the Fermat's little theorem a^{p-1}≡ 1 (mod p). Hence x has to be a divisor of (p-1).to think of this during a contest is a big task in itself :) thanks

L is dp with state

dp(l,r) denoting you are constructing a bst with values in range [l,r] , to calculate this , you can root the bst here with any value from [l,r] and take minimum cost which is just the number of nodes for which this root is the LCA.