SHIRO PROLEM

general
1

I AM NOT ABLE TO UNDERSTAND THIS PROBLEM CAN ANYBODY PLEASE EXPLAIN ME THIS PROBLEM
I LOOKED AT EDITORIAL EVEN THEN THE PROBLEM IS NOT CLEAR TO ME

edit : SHIRO

2

This can be solved by dynamic programming since at every stage maximum number of flags that can be obtained is 100 and numbers of stages is 100 so total flags can be 10000 . so we maintain an array of size a[10000]…where a[i] stores probability of getting ‘i’ flags at any stage.
Now at every stage ‘i’(1 to n) we run a loop ‘j’ (10000 to 0) and we check if a[j]>0 we first add the number of flags obtained at stage i and multiply a[flags(at stage i)+j] with p(probability of getting all flags) and multiply a[j] with (1-p)(probability of getting 0 flags at stage i).
In the last we iterate through all a[i] (i= (sum/2 to sum) and add all a[i](which is our result).(sum is the total number of flags that can be obtained at all stages).
hope u will be able to understand.
You can see the solution also at the problem page…

3

Always attach the link to the problem wheneve you post here asking for help
its really difficult to help out without knowing the question

4

now i got the problem and even understand it but the problem is now why we need to iterate from the end actually this is done to avoid the double counting problem but actually can anyone tell me how double counting is occuring
any kind of help will be greatly appreciated

5

Turn off your capslock.

1 Like
6

consider the dp array obtained after some stages be {0.05,0,0.07,0.12,…} now suppose at the next stage the max number of flags that can be obtained be 3.Now when u iterate from beginning u add 0 to index 0 to get no flag and 3 to index 0 to get all three flags and doing this we will loss the value at index 3 on which we have to work later . so we iterate from last so that no values obtained from previous state get changed.