### kevinsogo's blog

By kevinsogo, history, 3 years ago, , 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.

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. Comments (11)
 » 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 nknk-1...n1n0 can be written as n0 + (n1 * 101) + ... + (nk-1 * 10k-1) + (nk * 10k) 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 n0 + n1 + ... + nk-1 + nk (mod p) Similarly for p to be 1-altersum: 10 ≡ -1 (mod p) because then the number becomes n0- n1+ n2...- nk-1+ nk (mod p) Generalizing the above, for any p to be x-sum: 10x ≡ 1 (mod p) x-altersum: 10x ≡ -1 (mod p) So, we need to find minimum x such that 10x ≡ 1 (mod p) OR 10x ≡ -1 (mod p) Now by Fermat's little theorem, ap-1 ≡ 1 (mod p) so 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)).
•  » » » 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 10i ≢ 1 (mod p) AND 10i ≢ -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) = 10qx * 10r Depending on value of 10x and q, 10qx * 10r ≡ 1 * 10r (mod p) OR 10qx * 10r ≡ -1 * 10r (mod p) Since, 10r ≢ 1 (mod p) AND 10r ≢ -1 (mod p), the terms will never be equal to 1 (mod p). That contradicts the Fermat's little theorem ap-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.