Exactly correct!!!
But for the proof and solution to be complete, we need to analyze this
for 7 the answer you have is dp[3]=3*dp[2]+1=3*[4]+1
Now can you see that for dp[2], the number of steps would be
000
010
011
That would be only 3 steps so dp[2] is only 3 . Am i correct?
Regards
karthik
No,
dp[2] is
100
110
010
011
This is3 * dp[1] + 1 = 3 * 1 + 1 = 4 steps
Regards,
Prunthaban
Hi all,
Sorry for the late reply. Anyway here is the solution...
I want to note down 2 facts...
1. With 1 one the maximum reachable is 1
2. Any sequence of move is exactly reversible. You just have to toggle the bits in reverse order.
Now the solution.
With n ones..
1. Use first n-1 ones
hi every1 ,
I m Himanshu Sawhney , MCA student from D.U. Just joined this group .
I've formed a sol. plz chk it out
mark_last_cell(start,end,number)
{
if(start==end)
a[start]=1
return
mid=(start+end)/2
mark_last(start,mid-1,number-1)
hey everybody we all know that we love programming and certainly all
are appearing fro code4bill so instead of mugging in a small place why
dont we move to a group like CODE4BILL ASPIRANTS. we can discuss
problem better there
i got anwser of this question as::65527
as 1st time it would reuire 15(14+1) flips to one then again flip 14 cells to zero now after tht we will reach 14 cell now again flipnext 14 cells to one and then to zero then we will reach 28 cell i.e in every28 filp we gohead 14 cells (except in 1st time
I dont think that this would work either when you flip the first 14 cells to zero. The 15th cell would be still one. This cell you cannot flip to zero since its previous cell is zero. Then as you go on proceeding you would be leaving one cell every 15 cells as 1. You will reach a point where
I solved this problem ( A very very interesting DP solution I guess )The key to the solution is First try to Prove that the last bit can be set using only 15 onesand you will get the solution.Keep thinking!!!
( A clue :- use Mathematical Induction for the Proof and the DP follows)-karthik
can u plz explain how
How about this ?
1) Set first 15 1's
2) Flip 14th and 16th
2) Flip 15th and 17th...and so on
The no. of flips would be:
15 in step 1 +
two flips each for the remaining (32767-15) cells
15 + 2(32767-15)
10 matches
Mail list logo
