adurysk's blog

Invitation to ACM ICPC Asia-Kolkata Onsite Mirror Contest
By adurysk, history, 9 years ago, In English

Hello Everyone,

I would like to invite you to the mirror contest of official ACM-ICPC Asia-Kolkata Onsite regionals. The contest will start after one hour to the real contest at 11:00 hrs, IST tomorrow (sorry for the very short notice). There are some interesting sets of problems, hope you enjoy cracking them.

Please find details of the contest below:

  • Contest link: https://www.codechef.com/KOL15MOS
  • Start time and date: 11:00 hrs, IST
  • Registration: This is a team contest, so you need to register your team here to take part in it.
  • Note: Please login with your team handle to take make submissions to the problems in the contest.

See you all competing!

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

»
9 years ago, # |
  Vote: I like it +44 Vote: I do not like it

Standings of Amritapuri Onsite Mirror are still frozen, at the same time Kolkata Onsite Mirror standings weren't frozen at all :)

Comparing to Amritapuri regionals — this problemset looks more balanced&ICPC-style.

BTW, today I was receiving strange message You are not allowed to check this content. multiple times (F5 helps fine though); there was no such issue before.

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

    Ranklist was frozen around half an hour before end, even though you could still see the submissions on the submission pages of respective problems.

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

How to solve this ? https://www.codechef.com/KOL15MOS/problems/KOL1506

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 5   Vote: I like it +9 Vote: I do not like it

    I tried this problem when the contest was about to end, so couldn't implement the approach I had but I think it should work. Total complexity is O(N*k+NlogN) per test case.

    First, sort the array. Let x1, x2, x3, ... xN be the sorted array. Then we have to find twice of the following sum:

    Use binomial expansion to get:

    Precompute the binomial coefficients and also the prefix sums $\sum_{i=1}^p x_i^r$ for all r between 0 and k. Once this is done, you can compute each of the k double sums in linear time. Therefore, final complexity is O(N*k+NlogN).

    Hope this helps. :)

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

How to solve the Antichains problem?

https://www.codechef.com/KOL15MOS/problems/KOL1508

I think the largest antichain is the one consisting of all prime numbers or power of a respective prime number but I am not sure if this is correct.

Thanks!

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

    The largest antichain has size nC(n/2).

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

      How do you prove this?

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

        Well, the elements will have the same number of prime factors, cause otherwise the number of elements will be smaller. Now say each of the elements will have k different prime factors, so how many different numbers are possible? that is nCk, where n is the available number of primes. For k = n/2, nCk is the largest. So...

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

      And is the count = (product of all counts) ^ ((n — 1)C(n/2 — 1)) ? If n is odd i thought we should add (product of all counts) ^ ((n — 1)C(n/2)) and if n = 1 answer = count + 1.

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

        yep, that's it. But calculating the power is painfull though.

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

          Yeah i ended up trying to use CRT, Luca's theorem to calculate this. Need to find the easiest way.

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

            We prime factorized upto n, and counted the number of times each prime occurs in n!. The subtracted the number of times each prime occurs in (n/2)! and again for (n-(n/2))!. Finally get the product of prime[i]^count[i] mod (10^9+6).

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

              Antichains problem setter here. This was the intended solution :)

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

when will problems be added to practice?

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

How do you solve the Christmas Cookies problem?

→ Reply