## USACO help again

Moderator: Board moderators

h_s_potter2002
New poster
Posts: 6
Joined: Fri Nov 12, 2004 2:33 am

### USACO help again

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
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, fact, string;

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.

eleusive
New poster
Posts: 9
Joined: Tue Sep 28, 2004 6:57 am
Location: United States
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.

h_s_potter2002
New poster
Posts: 6
Joined: Fri Nov 12, 2004 2:33 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.

h_s_potter2002
New poster
Posts: 6
Joined: Fri Nov 12, 2004 2:33 am
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, fact, string;

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
1101100000011110101011111010011
--------------------------
Thanks

h_s_potter2002
New poster
Posts: 6
Joined: Fri Nov 12, 2004 2:33 am
Everything is okay now, I figured out how to solve the problem.

Alessandro
New poster
Posts: 27
Joined: Mon Jun 14, 2004 10:33 pm
Location: Latina, Italy
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
Alessandro Piva, Member of the Italian Team at the International Olimpiad in Informatics 2004
Email: alex.ander@infinito.it