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!
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.
Ranklist was frozen around half an hour before end, even though you could still see the submissions on the submission pages of respective problems.
How to solve this ? https://www.codechef.com/KOL15MOS/problems/KOL1506
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. :)
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!
The largest antichain has size nC(n/2).
How do you prove this?
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...
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.
yep, that's it. But calculating the power is painfull though.
Yeah i ended up trying to use CRT, Luca's theorem to calculate this. Need to find the easiest way.
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).
Antichains problem setter here. This was the intended solution :)
when will problems be added to practice?
How do you solve the Christmas Cookies problem?