bhishma's blog

By bhishma, history, 22 months ago, In English,

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 [Solved]

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 .

Solution

Thanks to ideas from fram and AleksanderBalobanov Since it's a functional graph we will have exactly one cycle per connected component . We need to color the graph using atmost K colors such that no 2 adjacent vertices have the same color . For any node which is not a cycle we have K - 1 options . For the nodes in a cycle we need to take care of them separately . We can construct a recurrence to find the number of ways to color a cycle in the following way.

Let DP[i] denote the number of ways to color a chain of length i such that it starts and ends with different colors.

DP[1] = 0, DP[2] = K * (K - 1)

DP[i] = (K - 2) * DP[i - 1] + (K - 1) * DP[i - 2]

This is basically saying that we have (K - 2) options for a chain starting and ending with different colors and (K - 1) options for a chain starting and ending with the same color. Another observation is that the number of chains of length i - 1 which starts and ends with same color is same as number of chains of length i - 2 which starts and ends with different colors.

My solution

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 AleksanderBalobanov)

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

Read more »

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

By bhishma, history, 2 years ago, In English,

I've been stuck on this problem for a while (Lazy Cows USACO 2005 US Open Gold) . I was able to get the recurrence correct . But my naive approach () TLEs .

First I compressed the positions by sorting them based on their column and breaking ties using the row number

Then I pre-processed 3 arrays

  1. costH1[i][j] stores minimum area covered using a single horizontal rectangle , from ith smallest position to jth . If it's not possible (cows are not entirely up or entirely down) then its INF.

  2. costH2[i][j] stores minimum area covered using 2 horizontal rectangles . If it can be covered with a single rectangle then its INF.

  3. costV[i][j] stores minimum area covered using a single vertical rectangle . To be more precise , its a rectangle with top left coordinate at (1 , coordinate[i]) and bottom right at (2 , coordinate[j])

Using these 3 arrays

DP[i][j] stores the minimum area covered by i rectangles for a prefix area till jth column.

Base Case

DP[0][j] = INF

DP[1][j] = min(costV[0][j], costH1[0][j])

DP[i][0] = 0

My Submission : Commented Code

Can someone help me in optimising this recurrence relation.

Update

I would like to thank send_nodes for helping me in solving this problem .

AC CODE

Read more »

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

By bhishma, history, 4 years ago, In English,

Problem Link : PMARK

Can anyone please help me with an approach to this problem . I was thinking about it for about 2 days but I couldn't come up with a solution . And is there a general approach to these type of problems .

UDP: Thank you guys for clarifying my doubts.

Read more »

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