Problem-Click Here
Although i solved this problem using bitmasking but I saw a solution which got Accepted by using Combinations (nCr).
Solution using Combinations (nCr) - Click Here
Can Anyone Explain the idea behind the above mentioned solution.How is he calculating ‘r’ in nCr?
Thanks in Advance!
You can calculate the number of ? ( let’s call it n) that need to be replaced by + (let’s call it x) and the ones that need to be replaced by - .
If you cannot find non-negative integers for either then the answer will be 0.
Otherwise, the you can choose the number of spots where the + will go as nCx and the - will go in the rest of the spots.
Answer will be probablity of getting + multiplied by nCx
Thank you @preyam for replying,
Your Explaination was good but i didn’t understand it fully.
Can You please elaborate in more detail on the basis of the solution mentioned above,like how is he calculating ‘r’ in ‘nCr’.
Thanks in advance!
what u wanna ask …full solution or , just what he did in NCR function ?
Look at the solutions for variable names.
The sum that you need in the ? places is (a-b) .
Let’s say that the number of + in the ? places in the final answer is x and the number of - is y.
x+y=n
x-y=a-b
on adding we will get x=(n+(a-b))/2 i.e. number of + that we need in the final answer which is also equal to r.
Thanks for replying,
Please Explain Starting from following line from the code that i mentioned above,
if(((N + abs(a-b))&1) || N < abs(a-b)){A trivial observation is that if the value of (p-s) for any two sequences is the same (where p and s denote the number of pluses and minuses respectively), they have the same final position. I’ll refer to this value as the balance.
Let’s find the balance for the original sequence and the interpreted sequence (ignoring the ? marks). Suppose the balance for the original sequence is 5, and the interpreted sequence is 3, and you have 6 ‘?’ marks in the interpreted sequence.
You now know that you need to replace the ‘?’ marks with a sequence whose balance, when added to 3, makes the entire balance 5. This is obviously 2.
We need to place pluses and minuses such that the number of pluses (let it be p) is 2 greater than number of minuses (let it be m). You also know that p+m = q, where q is the number of question marks (6 in this case).
Your two equations are p+m=q and p-m=2. Solve those, and you get p=4 and m=2.
You now need to count number of ways to arrange these pluses and minuses in the place of question marks. This count is q \choose p.
If number of question marks + the distance covered is odd, there is no way Dreamoon can reach b (because we’re left with an odd parity. We can only reach b - 1, or b + 1). Similarly, if the number of question marks is less than abs(a - b), Dreamoon cannot move to b, even if he chooses all + or all -.
N is the number of ?, so essentially the number of choices that are made.
b is the coordinate where Dreamoon is supposed to reach.
a is the coordinate where Dreamoon is currently standing.
Now Dreamoon has to move a total of abs(a - b) steps. So out of N ?s, we choose exaxtly abs(a - b) and turn them to + (WLOG). Now out of the remaining abs(a - b) ?s, we choose half of that and turn it to +, and the rest to -.
This means we are flipping a total of (N - abs(a - b)/2 + abs(a - b)) ?s. Which essentially simplifies to (N + abs(a - b))/2, which is his r.
Nice explanation , and congo for 5 star 
Thanks!!
@aneee004 @preyam @shivensinha4, I literally want to thank you guys.I was Struggling with this doubt since evening.Now i understood how r is calculated with a much genuine explaination.
Thanks You So much @aneee004 @preyam @shivensinha4 !!!
I solved this problem using two methods
1.Bitmasking - Solution
2.nCr - Solution
And,I think Bitmasking Solution takes O(2^n) time and,
nCr Solution takes O(n) Time.
where, n is the length of the string.
Am i Correct in calculating Complexity?
double num=0.0,den=(1<<q);
for(int i=0;i<den;i++)
{
fin=valu;
for(int j=0;j<q;j++)
{
if(((1<<j)&(i)))fin++;
else fin--;
}
if(fin==val)num++;
}
Is this your bitmask part? This doesn’t look like O(2^n). An exponential example is this:
for(int i = mask; i > 0; i = (i - 1)&mask)
Here we are iterating over all 2^n subsets of mask. But your loop seems to be linear.
[UPD]: I did see the den = (1 << q). If q is proportional to n, then yes the algo is O(2^n).
(But how are both running times equal?)
Yes this is my bitmasking part,and yes i am checking all 2^n subsets but here n is the number of question marks(’?’)
So in Worst Case if whole string string contains ‘?’ then it will be an O(n) Solution.
Am i right?
Yes Both are taking 31 ms, Thats why i asked about the time complexity.
[UPD] My Bitmasking Solution will be O(n*(2^n)) as i am iterating the subsets too.
So Time Complexity is huge for Bitmasking.
Right?
Yes, that is right.
But nCr Solution should take 15 ms , but its taking 31 ms.
Do you know the reason for 31 ms in nCr Solution?
No clue 
. It’s very similar to the one that you have linked in the topic, but still the runtime is twice of that!