Quote: 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, 110011Considering 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].
Hints on a combinatorics problem
Author
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:
Author
Quote: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.
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.
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.
Author
Hm. Maybe I'm just being dense, but wouldn't we end up with 2^100 states if n=100?
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;
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;
Author
WOOHOO!
Thanks to your help, I solved it [grin]
It pleases me to no end to see the judge spit out
[lol]
Once again, thanks a bunch [smile]
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)[lol]
Once again, thanks a bunch [smile]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
