Sign in to follow this  

Hints on a combinatorics problem

Recommended Posts

Hey guys. I'm working through some practice problems for a programming competition, and one of them is giving me a tough time. The problem goes like this:
For a string of n bits x1, x2, x3, ..., xn, the adjacent bit count of the string is given by x1*x2 + x2*x3 + x4*x4 + ... + xn-1*xn which counts the number of times a 1 bit is adjacent to another 1 bit. For example, the adjacent bit count of 011101101 is 3. Write a program that takes as input integers n (1 <= n <= 100) and k and returns the number of bit strings x of n bits that have an adjacent bit count of k. For example, for 5 bit strings, there are 6 ways of getting an adjacent bit count of 2: 11100, 01110, 00111, 10111, 11101, 110011
Considering n can go up to 100, a brute force solution clearly won't work. So I'm definitely looking at some sort of combinatoric solution. I'm in 10th grade and I'm taking PreCalc H, so any and all combinatoric problem solving skills I have are what I've picked up on my own - and they are very sparse. Can someone give me a little push in the right direction? I'm not sure how to start the problem [sad].

Share this post

Link to post
Share on other sites
Original post by quasar3d
look up dynamic programming.

I know about dynamic programming, but can I get some hint specific to the problem? I'm not sure how to start it, regardless of using dynamic programming.

Share this post

Link to post
Share on other sites
It's a pretty typical dp problem though.

What I'd do is basically:

at each iteration (so for numbers of a given length n), keep a list of all the states so far, and for each state, in how many ways that state could have been reached:

struct State
int numAdjOnes;
int prevBit;
int numWays;

Then using that information, it's should be pretty straightforward to calculate the new state information, for numbers of length n + 1

Then you just repeat this process until you have your information for numbers of the length you needed, and then you select the two states with the correct number of adjacent ones, where on of them will have prevBit to 1, and another one prevBit to 0. Then you add their numWays, which will be your answer.

Share this post

Link to post
Share on other sites
It won't exceed 200 states. The max number of adjacent bits you can have is 99, and the previous bit can be either 0 or 1.

The trick is that you only care about how many adjacent bits have occurred, and what the last bit was. You do not care which bits it actually were that were adjacent.

Since only a tiny bit of the information is relevant, many similar situations can be collapsed into a single state.

For example, say you have the following two states

State a;
a.numAdjOnes = 2;
a.prevBit = 1;
a.numWays = 10;

State b;
b.numAddOnes = 3;
b.prevBit = 0;
b.numWays = 20;

With these two states, the 1 branches of both states can be combined into a single state:

State c;
c.numAdjObes = 3;
c.prevBit = 1;
c.numWays = a.numWays + b.numWays;

Share this post

Link to post
Share on other sites

Thanks to your help, I solved it [grin]

It pleases me to no end to see the judge spit out

Testing AdjacentBitCounts...
AdjacentBitCounts SUCCESS (0.201s)


Once again, thanks a bunch [smile]

Share this post

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this