Help needed in ICPC Amritapuri 2010 problems

Правка en5, от bhishma, 2017-11-11 08:02:39

Recently we were solving problems from past Indian ICPC regional . We weren't able to solve these 2 problems , and I couldn't find any editorial either . It would be really helpful if you guys can give me some hints to these problems.

Chemicals

Description

There are N bottles each having a different chemical. For each chemical i, you have determined C[i], which means that mixing chemicals i and C[i] causes an explosion. You have K distinct boxes. In how many ways can you divide the N chemicals into those boxes such that no two chemicals in the same box can cause an explosion together?

Constraints

  • T ≤ 50
  • 2 ≤ N ≤ 100
  • 2 ≤ K ≤ 1000

My Ideas

I thought of modelling the given dependencies as a graph and we are asked to find the number of ways to partition the graph into independent sets . But I realised that counting independent sets is intractable , so there must be a much more efficient or different way to solve this problem .

Dividing Stones [Solved]

Description

There are N stones, which can be divided into some piles arbitrarily. Let the value of each division be equal to the product of the number of stones in all the piles modulo P. How many possible distinct values are possible for a given N and P?

Constraints

  • T ≤ 20
  • 2 ≤ N ≤ 70
  • 2 ≤ P ≤ 109

Idea (thanks to ABalobanov)

We represent every partition as p1a1 * p2a2 * ... * pkak, where p1, p2, ..., pk are primes up to 70. We can achieve this value for a given n iff a1 * p1 + a2 * p2 + ... + ak * pk ≤ n . So the partition looks like p1 + p1...a1 times + ... + pk + pk...ak times if the value is less than n we can add extra 1 .

My solution

Теги acm-icpc amritapuri, graph, math

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский bhishma 2017-12-02 15:03:01 0 Solved Chemicals (published)
en8 Английский bhishma 2017-12-02 15:01:05 14
en7 Английский bhishma 2017-12-02 14:59:17 1209 (saved to drafts)
en6 Английский bhishma 2017-11-11 08:04:33 8 solved dividing stones (published)
en5 Английский bhishma 2017-11-11 08:02:39 513 (saved to drafts)
en4 Английский bhishma 2017-09-08 21:37:57 38 (published)
en3 Английский bhishma 2017-09-08 20:55:08 483
en2 Английский bhishma 2017-09-08 20:05:56 235
en1 Английский bhishma 2017-09-08 19:55:40 958 Initial revision (saved to drafts)