OJ Board

Posted: **Mon Dec 20, 2004 7:43 pm**

I'm on problem kimbits,

Consider an ordered set S of strings of N (1 <= N <= 31) bits. Bits, of course, are either 0 or 1.

This set of strings is interesting because it is ordered and contains all possible strings of length N that have L (1 <= L <= N) or fewer bits that are `1'.

Your task is to read a number I (1 <= I <= sizeof(S)) from the input and print the Ith element of the ordered set for N bits with no more than L bits that are `1'.
PROGRAM NAME: kimbits
INPUT FORMAT
A single line with three space separated integers: N, L, and I.
SAMPLE INPUT (file kimbits.in)

5 3 19

OUTPUT FORMAT
A single line containing the integer that represents the Ith element from the order set, as described.
SAMPLE OUTPUT (file kimbits.out)

10011

And I'm using the algorithm mentioned here after trying about 10 other ways to do the problem. I'm having trouble though on test case 12 -

--------------------------
31 26 123456789
--------------------------

Here are the respective outputs:

----- our output ---------
0000111010110111100110100010100
---- your output ---------
0001000001100110000110010110101
--------------------------

, I don't know where to start debugging my program -

Code: Select all

#include <stdio.h>
#include <math.h>

FILE *input, *output;
long long numbits, numones, ith, count, total;
long long wrong[2], fact[33], string[33];

long long fac(long long num, long long start)
{
	long long i, f=1;
	
	if(fact[num] > 0 && start == 1)
		return fact[num];
	
	for(i=start+1; i<= num; i++)
		f *= i;

	if(start == 1)
	    fact[num] = f;
	
	return f;
}



int main()
{
	long long i, length, numright=0, k, temp=-1, j, numwrong, ornum;

	input = fopen("kimbits.in", "r");
	output = fopen("kimbits.out", "w");

	fscanf(input, "%lld %lld %lld\n", &numbits, &numones, &ith);

	ith--;

	for(j=1; j<numbits; j++)
	{
		temp = numbits-j;
		numright = 0;
		
		for(i=0; i<=numones && i<=temp; i++) //figure out the number of strings of length temp that fit //the decription
		{
			if(i > numbits-i)
				numright += fac(temp, i)/fac(temp-i, 1);
			else
				numright += fac(temp, temp-i)/fac(i, 1);
		}
		
		if(ith >= numright)
		{
			ith -= numright;
			numones--;
			fprintf(output, "1");
		}
		else
			fprintf(output, "0");
	}
	if(ith >= 1)
	{
		fprintf(output, "1");
	}
	else
		fprintf(output, "0");
	fprintf(output, "\n");
	
	return 0;
}

I think it has something to do with the piece of code with comment, but I really don't know. Does anyone know where I'm going wrong, or a different way to figure out the number of strings of length temp that fits the description? Thanks.

Posted: **Tue Dec 21, 2004 4:38 am**

You shouldn't be using factoral to find the number of combinations. Factorial is for finding permutations, and you are looking for combinations (since order on the positions of the different 1's in multiple positions doesn't matter), so try using binomial coefficients.

Posted: **Tue Dec 21, 2004 5:04 am**

Here's the forumla I've always been taught, where L goes from 1 to L -

N!/(L!*(N-1)!)

which is what I'm using, and I think is the same thing as binomial coefficiants, I'm sure since I'm not that good at math. I'm just implementing this forumla a little differently.

Posted: **Tue Dec 21, 2004 10:58 pm**

I found out what was wrong, which I have bolded in the new code.

#include <stdio.h>
#include <math.h>

Code: Select all

FILE *input, *output;
long long numbits, numones, ith, count, total;
long long wrong[2], fact[33], string[33];

long long fac(long long num, long long start)
{
   long long i, f=1;
   
   if(fact[num] > 0 && start == 1)
      return fact[num];
   
   for(i=start+1; i<= num; i++)
      f *= i;

   if(start == 1)
       fact[num] = f;
   
   return f;
}



int main()
{
   long long i, length, numright=0, k, temp=-1, j, numwrong, ornum;

   input = fopen("kimbits.in", "r");
   output = fopen("kimbits.out", "w");

   fscanf(input, "%lld %lld %lld\n", &numbits, &numones, &ith);

   ith--;

   for(j=1; j<numbits; j++)
   {
      temp = numbits-j;
      numright = 0;
      
      for(i=0; i<=numones && i<=temp; i++) //figure out the number of strings of length temp that fit //the decription
      {
         if(i > [b]temp[/b]-i)
            numright += fac(temp, i)/fac(temp-i, 1);
         else
            numright += fac(temp, temp-i)/fac(i, 1);
      }
      
      if(ith >= numright)
      {
         ith -= numright;
         numones--;
         fprintf(output, "1");
      }
      else
         fprintf(output, "0");
   }
   if(ith >= 1)
   {
      fprintf(output, "1");
   }
   else
      fprintf(output, "0");
   fprintf(output, "\n");
   
   return 0;
}

And here's the new test case that I'm having trouble with. I still think the problem is still in the same part I mentioned, becuase I checked it with a debugger, assuming it was right, but i couldn't tell what was wrong with the program, so it has to be that part.

--------------------------
31 26 1234567890
--------------------------

Here are the respective outputs:

----- our output ---------
1001001100101100001010010011011
---- your output ---------
1101100000011110101011111010011
--------------------------

Thanks

Posted: **Wed Dec 22, 2004 4:40 am**

Everything is okay now, I figured out how to solve the problem.

Posted: **Fri Mar 04, 2005 11:26 pm**

I think you used the algorithm I suggested ^_^

I just posted to say this: let be bincoeff(n,k) the binomial coefficient of n elements of class k, we have:

bincoeff(n,0) = 1
bincoeff(n,n) = 1

otherwise:

bincoeff(n,k) = bincoeff(n-1,k-1) + bincoeff(n-1,k)

Don't use factorials, just use DP!

Goodbye
Alessandro

OJ Board

USACO help again

USACO help again