kevinsogo's blog

Invitation to ACM-ICPC Asia — Kolkata 2016 Onsite Mirror Contest
By kevinsogo, history, 7 years ago, In English

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.

  • Vote: I like it
  • +40
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Gentle reminder!! 10 minutes to go!!

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Please explain how to prove that the answer will always be a divisor of p-1

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          to think of this during a contest is a big task in itself :) thanks

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

    → Reply