Блог пользователя CMaster

Codechef May challenge
Автор CMaster, история, 8 лет назад, По-русски

Закончился Codechef May challenge.

Давайте обсудим задачи.

Почему в задаче SANDWICH это ответ -->

Как решать задачу KILLER?

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been translated by CMaster (original revision, translated revision, compare)

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

The minimum number of sandwiches is . Suppose we give K to each of them. We have used too many meters of sandwich. We have to take out a bit from some sandwiches in such a way that it sums up to what we need to erase.

Recall that the number of ways to write N as a sum of K non-negative numbers, where order matters is . You can prove this by bijection.

Combine these observations and you end up with an equivalent formula for the problem.

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It says in the problem statement that we have to find this value mod P. When P is prime, we can find it by using Lucas Theorem. But how will we solve it when P is a composite number? (I know it involves Chinese Remainder Theorem but I think I'm missing something.)

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +12 Проголосовать: не нравится

      We need to find some C(N, K) modulo M. We can factorize M into different P^q and use Chinese Remainder Theorem to find an answer.

      Now, our aim is to find C(N, K) modulo some P^q. How to do that? First of all, let's try to use formula N! / (N — K)! / K!. But we can't divide as (N — K)! and K! are not co-primes with P^q. We can actually compute factorials without P's and calculate degree of P in C(N, K) afterwards.

      So, what does the factorial without P mean? Pseudo-code is here:

      int f = 1;
for (int i = 1; i <= n; i++) {
  int x = i;
  while (x mod P == 0) x /= P;
  f = (f * x) mod P^q.
}

      Let's call this factorial N!!.
      Then C(N, K) mod P^q is N!! / K!! / (N-K)!! * P^k, where k is degree of P in C(N, K). As K!! and (N-K)!! both aren't divisible by P, they are coprimes with modulo and we can easily divide by multiplying to inverse numbers.

      Last step is finding out how to calculate N!!. Let's have a look what N!! is: 1) First, we multiply all numbers which are not divisible by P. 2) Let's have a look at multiplies of P. They are P, 2P, 3P, ..., floor(N / P) * P. After dividing by P, these numbers become 1, 2, 3, ..., floor(N/ P) and we can solve recursively.

      Finally: N!! = (N / P)!! * multiplication_of_numbers_which_are_not_divisible_by_P mod P^q.
      Second part is easily calculated in O(P^q).

      → Ответить
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

First we know that the maximum number of groups will be [Ceil], which actually will consist of (floor) partitions with value = K and one partition with value N%K. Now we can see that we can not decrease the the size of partition N%K, because then we'll have to increase the size of other partitions which will violate the conditions. Now we can increase the size of this one partition from N%K to K, which means we are getting some values from the other partitions. So, We can increment it's size from 0 to (K - N%K). That means we have to find the non-negative integrals solutions of this equation t1 + t2 + ... + tx =  Δsize where X =  floor and Δsize is from 0 to (K - N%K). So for a particular Δsize our answer is .
Now we have to find summation over all the Δsize. Let us denote R = K - (N%K). Now we have to find sum of this value . Now, write . If we combine this term with , we get . Now combine this with other terms, you will finally get . [Note : We have combined two terms using the property ]

→ Ответить
»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Hi!

Can someone please explain the following solution for the KILLER problem? Thanks!

https://www.codechef.com/viewsolution/13623489

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I also still don't know how to solve this problem. I'm especially curious why does chemthan's solution work. I know a similar trick called "LiChao segment tree", but I don't see why does it work for parabolas too (the trick by default is for line functions). If someone knows can he/she explain. Thanks in advance.

    → Ответить