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 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.