How can we split the set of numbers in n parts. For eg set {1,2,3,4,5,6}, we
have to split it in 3 parts using all the elements for eg valid split could be {123,45,6} , {14,23,56} , {13,245,6} etc.
What is max n and max m (size of the set)?
You want to split to exactly n parts, so no part is empty and here is the difference why it’s not n^m (because one of possibilities is that all elements are in one part).
I assume, that n is up to 10 and m up to 1000, than you can simply calculate
F(N) = F(N,0)
where 0 is bitmask of not empty parts.
F(N,mask) = sum( i, 0, n-1 ) { F(N-1, mask || (1 << i ) }
maybe thats not clear notation I’ll explain on your example
F(6, 0000) = F(5, 1000) + F(5, 0100) + F(5, 0010) + F(0001)
recursion ends when N in F(N, mask) is 0
F(0, 1111) = 1
F(0, xxxx) = 0 // where at least one bit (x) is 0 - we have empty part
complexity of this algorithm is O(n*m*2^n).
Thanks betlista for responding. I have been checking the forum if any body has posted yet :).
Actually Size of Set i.e n varies with the input. For eg It is 6. and m which is in how many partitions we can make from that set having n elements by using all the elements.For eg {123,45,6} , {1,2345,6} are some valid cases.
To be precise, I am solving ACM ICPC problem. Magic Rings . Here points make the elements of Set i.e n and magic rings make the m of the set i.e partition.
Now I need to check all the possibilities of m partitions.
I am trying your approach to fit it in this problem. Any thoughts?
Now I am going through your approach.
hi betlista
i understood your soln by writing the cases for n=6 and m=3. Now I am able to make the all possile cases of m partitions i,e 3 .
But I would like to know Can we use DP here as I found we are repeating some cases which we have already calculated.If yes, How would we store the states we calculated.
@deleted: Some mistakes were there
@edit:
F(n,m) = F(n-1,m)*m + F(n-1,m-1)*m
constraints;
F(n,m) = 0 if m>n;
F(n,n) = n!
F(n,1) = 1
F(4,2) = 2*F(3,2) + 2*F(3,1) = 2*(2*F(2,2) + 2*F(2,1))+ 2 = 2*(4+2)+2 = 14
Using recursion with memoization is almost the same as DP (for me it’s a bit easier). In F function you have to remember values for N and mask (M is constant), so you can create 2D array int[n][1<<m] and at the begining of the function ask if you calculated this combination already, if so return the calculated value if not calculate and store the value.
In Java I’m using big int for this (Integer) and null represents value that is not calculated, in C/C++ I’m using another array of chars with flag Y/N or some special value in int array if possible (personally I prefer first variant with char flags).
I was thinking about your approach and the idea seems correct to me, but I’m afraid that the formula is not ok still.
Idea is that the number for those two input is the same
F(4, 0101)
F(4, 0110)
we need to track only the number of parts already created, so basically there are 2 possibilities - 1.) create new part or 2.) use existing one
F(n, a) = x*F(n-1, a+1) + y*F(n-1, a)
the question is what are the values of x and y (a is actual number of parts, we start with 0).
If we want to use existing part, there are a possibilities, if we want to add new one, there are m-a ways.
I did some tests and your formula seems working too 
my idea is as follows: for n size and m partition… you have 2 steps
-
you do n-1 size and m partition and then add the nth one to any of those m partition in m ways
-
you do n-1 size and m-1 partition and then add the nth one as the mth partition which can be located at i’th position in the partitions
(0<=i<=m-1) => m ways
1 Like
just wrote one quick program on my understanding.
package com.acm.icpc.problems;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class MagicRings {
/**
* @param args
*/
int[] set = {1,2,3,4,5,6};
int partition = 3;
public static void main(String[] args) {
// TODO Auto-generated method stub
MagicRings mr = new MagicRings();
mr.generatePartitions(mr.set,mr.partition);
}
HashSet calculate = new HashSet<HashSet<Integer>>();
private void generatePartitions(int[] set,int partition) {
int setLength = set.length;
int setBitsMain = (1 << setLength + 1) - 1;
for(int mask=1;mask <= (1<<setLength-1)-1;mask++){
int a = setBitsMain & mask;
String astr = Integer.toBinaryString(a);
int[] bitArray = new int[set.length];
String[] astrArray = astr.split("");
int k = bitArray.length -1;
for(int i=astrArray.length-1;i>=1;i--){
bitArray[k]= Integer.parseInt(astrArray[i]);
k--;
}
int[] newSet1 = new int[Integer.bitCount(a)];
int[] newSet0 = new int[set.length - newSet1.length];
int j =newSet0.length-1;
int l =newSet1.length-1;
for(int i =bitArray.length-1;i>=0;i--){
if(bitArray[i]==1){
newSet1[l] = set[i];
l--;
}else{
newSet0[j] = set[i];
j--;
}
}
HashSet s1 = new HashSet<Integer>();
HashSet s0 = new HashSet<Integer>();
for(int i = 0;i<newSet0.length;i++){
if(newSet0[i] != 0)
s0.add(newSet0[i]);
}
for(int i = 0;i<newSet1.length;i++){
if(newSet1[i] != 0)
s1.add(newSet1[i]);
}
if(partition-2==0){
calculate.add(s1);
calculate.add(s0);
calculate(calculate);
calculate.remove(s1);
calculate.remove(s0);
}
//calculate(calculate);
if(partition!=2){
calculate.add(s1);
partition = partition - 1;
generatePartitions(newSet0, partition);
calculate.remove(s1);
partition = partition + 1;
}
}
}
private int calculate(HashSet<HashSet<Integer>> caluclate){
if(caluclate.size()==partition){
System.out.println("-------");
Iterator<HashSet<Integer>> it = caluclate.iterator();
while(it.hasNext()){
HashSet<Integer> set = it.next();
Iterator<Integer> setit = set.iterator();
while(setit.hasNext()){
Integer its = setit.next();
System.out.print(its);
}
System.out.print(" + ");
}
}
return 0;
}
}In above program, I am printing out the possible combinations for the input.
What I am doing is :
- Making Combination by bit masking, then removing those bit which are set and creating combination of bits which are not set until partition becomes 2 i.e 1 or 0.
- For above, I am using recursion and keeping check of partition i.e required partition until 2.
I could not use Memoization in above program, But I use masking to take care of it by not running it more than half in the case of partition is 2. Because after half it will just create duplicate sets. For eg 10000 and 01111 both give same combination. Little diff to understand thats why i pasted the program.
Any input guys?
@skatercoder correct me if i am wrong
why not do the problem this way
initially put magic rings on first m (out of n) monster.and find the min distance between 2 rings…
then add monster (m+1,…n) and if the new monster < min distance/2. the rings are fine…
if new monster > min distance/2 create a new ring for the new monster and delete one of the ring of the nodes which had min distance and move the other to centroid of those rings coordinate…
aashish I did not get your point of view properly. I tried to do what you are saying. It wold be good if could explain any of the following cases:
6 2
0 0 1 1 2 2 10 10 10 11 10 12
4 2
0 0 10 0 5 10 1000 1000