Help needed in ICPC Amritapuri 2010 problems

Правка en2, от bhishma, 2017-09-08 20:05:56

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 .

Теги 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)