dynamic programming: (minimum days of not eating icecreams)

Question

Minimum Days Not Eating Ice-cream

Ram decides to eat ice-cream for N days. On each day the ice-cream shop can have chocolate flavour or mango flavour or both or none. The availability of ice-cream flavour is represented as 1 for chocolate, 2 for mango, 3 for both and 0 for none. Ram do not like to have the same ice-cream flavour on any two consecutive days. Find the minimum number of days that Ram do not eat ice-cream.

Boundary Condition(s): 1 <= N <= 100000

Input Format :

The first line contains the value of N. The second line contains N integers separated by space(s).

Output Format: The first line contains the minimum number of days that Ram do not eat ice-cream.

Example Input/Output 1:

Input:
5
1 2 1 0 2

Output:
1

Example Input/Output 2:

Input:
8
2 1 1 1 3 3 3 2

Output:
2

Explanation:
On the 1st day, ram eats mango flavour.
On the 2nd day, ram eats chocolate flavour.
On the 3rd day, chocolate flavour is available but he cannot eat same the flavour on two consecutive days. So he does not eat anything. On the 4th day, ram eats chocolate flavour.
On the 5th day, Ram eats mango flavour.
On the 6th day, Ram eats chocolate flavour.
On the 7th day, Ram eats mango flavour.
On the 8th day, Ram do not eat anything.

Hidden case:

I/P:

3001

1 1 0 3 1 3 2 0 3 0 1 2 3 0 2 1 2 2 0 3 3 2 0 3 1 1 2 3 0 1 0 1 3 1 1 3 0 0 3 3 0 0 1 2 0 3 3 3 1 2 1 3 1 1 0 3 0 1 0 2 2 0 3 0 2 2 1 1 2 0 3 1 1 1 0 0 1 2 1 2 2 1 0 2 3 0 2 2 3 1 0 3 2 2 0 1 3 2 0 2 3 3 1 2 2 0 1 2 2 2 2 0 0 2 1 0 3 3 1 3 1 3 0 3 2 3 1 3 3 0 0 1 3 2 3 1 0 3 1 0 2 0 2 3 0 1 3 0 1 3 0 3 3 0 3 2 2 1 1 3 1 0 3 0 0 1 2 2 3 2 1 1 2 0 1 3 1 2 0 1 1 2 1 2 0 2 0 0 3 0 0 1 0 1 3 2 3 0 1 3 1 3 1 2 2 3 3 1 3 3 0 0 3 2 3 0 0 2 3 2 0 0 0 2 2 3 2 0 0 1 2 2 0 0 1 1 2 3 3 0 3 2 3 2 3 2 1 0 3 1 3 1 0 0 1 2 1 3 0 0 0 0 1 0 2 1 0 2 0 3 3 3 0 2 0 1 1 3 1 2 2 2 0 0 2 2 1 1 2 3 0 2 0 0 3 1 1 1 2 2 3 2 0 1 2 2 1 0 1 3 1 1 1 2 1 2 3 2 2 3 0 1 1 2 3 1 2 0 3 1 0 0 3 0 3 1 3 1 2 3 0 2 3 0 1 3 0 2 0 1 0 3 1 1 0 3 1 1 0 0 1 0 2 0 0 3 0 1 0 2 3 1 0 0 2 0 1 1 0 0 3 0 0 1 2 0 0 1 2 2 0 1 3 3 0 0 2 1 3 1 0 0 2 3 1 2 1 0 3 3 0 1 1 1 2 3 0 3 2 0 2 0 3 0 2 3 0 0 0 2 2 2 3 2 0 3 1 2 1 2 2 3 1 2 2 2 3 2 3 0 1 0 2 3 0 0 1 0 2 0 1 2 2 1 2 3 0 0 3 3 0 1 1 2 0 2 2 3 3 2 2 0 3 3 2 1 0 3 3 0 3 1 1 2 0 2 3 0 0 1 3 1 0 3 2 0 1 2 1 2 3 3 1 0 1 1 1 0 0 1 0 1 2 2 3 1 2 0 2 0 0 1 2 1 3 3 2 3 2 0 2 1 3 0 0 2 2 3 0 2 0 3 0 1 0 0 2 3 2 3 2 2 2 2 3 0 1 3 2 3 1 0 0 0 3 3 2 3 2 2 2 0 1 1 3 3 3 0 2 0 2 0 0 1 0 0 0 3 3 0 1 1 1 3 3 3 3 3 3 2 2 0 0 2 3 2 3 3 1 1 3 0 2 1 1 0 0 0 2 1 1 3 2 1 3 1 3 3 1 1 0 3 0 3 1 2 2 3 0 0 1 1 2 0 2 0 3 3 1 1 3 1 1 0 0 1 2 3 1 3 1 2 1 1 1 0 0 2 0 2 0 2 2 1 0 2 3 3 1 2 1 3 3 1 1 3 2 3 2 1 3 3 2 3 2 1 3 0 2 3 2 1 2 3 0 0 3 3 2 0 0 1 2 1 0 3 3 2 2 3 0 3 3 0 0 1 2 2 0 0 3 2 2 2 2 3 0 1 2 3 0 3 1 2 0 0 1 1 3 1 0 2 0 3 2 2 2 0 1 2 2 2 1 3 3 3 1 2 3 3 3 3 3 3 3 3 1 2 2 1 2 2 3 3 3 0 3 1 1 0 2 1 0 1 2 1 2 0 0 3 0 0 3 1 2 3 0 2 0 2 1 0 0 0 2 3 0 3 2 3 0 2 2 2 2 0 0 0 2 1 0 2 2 1 1 3 0 3 1 1 2 2 1 3 2 1 1 3 3 1 0 3 3 2 1 3 2 2 2 1 3 0 3 3 3 0 2 0 2 3 1 2 1 2 3 1 3 1 1 3 2 3 0 3 3 1 0 1 3 0 3 2 3 1 3 0 1 2 0 1 3 1 1 1 3 0 0 2 3 3 1 2 1 3 1 3 0 0 0 0 3 0 0 2 2 0 1 3 3 2 0 2 1 0 0 2 3 0 3 1 1 2 0 1 2 0 0 1 1 0 1 0 1 2 2 2 0 1 0 3 3 3 2 3 1 1 2 1 3 1 1 0 2 2 0 2 3 3 3 0 3 1 0 2 2 2 3 3 3 1 3 1 1 3 2 2 3 2 0 1 2 1 3 1 3 0 1 3 2 2 2 1 2 3 2 1 3 1 0 3 0 3 1 2 2 2 2 2 3 1 0 0 1 2 2 1 0 1 0 3 0 2 2 1 2 0 2 3 1 3 0 1 0 2 0 1 0 2 3 0 1 0 1 1 0 3 0 3 0 0 2 0 1 2 3 3 1 0 2 0 1 2 1 2 2 2 1 3 2 1 0 3 3 2 0 1 1 1 0 0 2 0 3 2 0 0 1 3 1 2 1 2 1 2 2 0 1 2 2 1 1 0 2 2 2 2 3 3 0 3 1 2 3 1 0 3 2 0 2 1 3 0 0 2 2 2 0 3 2 2 1 2 1 0 0 0 0 0 0 1 3 2 2 0 3 0 2 3 0 2 1 2 1 1 3 2 0 3 0 1 1 2 0 3 3 0 1 1 0 3 0 0 3 1 3 3 3 0 0 0 3 3 1 1 2 2 2 2 2 0 0 0 3 2 1 1 2 0 2 0 2 3 0 3 1 1 1 0 1 3 2 0 0 1 2 3 2 3 2 0 2 1 0 2 2 2 0 1 3 1 0 0 2 2 1 2 0 0 3 0 1 1 0 3 0 0 2 0 2 3 1 3 1 0 0 0 3 1 2 2 0 3 2 2 1 1 1 0 0 2 2 0 3 2 3 2 2 3 0 1 0 3 0 0 1 2 3 2 3 1 1 1 1 1 0 2 1 0 0 1 3 0 0 3 2 3 0 3 0 3 1 2 2 0 0 1 3 3 1 2 1 2 0 1 3 2 3 3 3 0 0 0 0 3 2 1 0 1 0 3 3 0 0 2 2 2 1 3 1 1 1 1 2 2 0 2 3 2 2 3 0 0 1 3 0 2 2 0 1 1 0 3 0 2 2 1 0 2 1 0 0 2 0 0 0 3 2 0 0 2 1 1 3 3 0 3 3 0 3 0 3 0 0 3 3 1 2 3 3 0 0 1 0 2 2 0 1 2 3 3 1 2 2 1 2 2 3 2 0 0 2 3 1 0 0 1 1 3 0 0 2 1 3 3 3 1 0 2 3 3 3 0 2 0 0 3 3 2 2 1 3 2 3 0 1 1 2 2 0 3 3 2 2 1 3 3 2 3 0 2 0 3 1 1 3 2 3 3 2 1 2 3 0 0 0 0 3 3 1 2 1 2 2 0 2 1 0 0 2 3 3 2 0 1 2 1 2 3 1 2 2 3 1 3 0 1 1 3 1 3 3 0 1 0 2 1 0 1 0 2 1 2 2 2 2 3 0 2 1 0 2 1 0 3 0 0 3 0 0 0 1 1 3 1 2 2 3 3 1 2 0 1 2 0 2 3 0 0 0 2 1 3 2 0 2 3 0 2 3 1 2 1 1 3 3 1 2 3 2 1 0 2 1 3 3 3 2 2 1 3 3 0 0 3 2 1 2 0 2 2 0 0 3 3 1 1 2 1 0 0 1 0 3 1 0 1 3 1 0 2 0 2 2 1 1 1 2 1 1 2 3 1 1 3 1 1 3 1 2 0 3 0 0 1 0 3 1 1 1 3 2 1 2 1 3 1 0 1 0 2 2 0 2 1 0 0 2 1 0 0 1 0 2 2 2 1 0 0 2 0 0 3 3 2 0 2 3 2 3 0 2 2 1 0 1 3 1 3 1 0 0 2 0 0 0 2 0 0 3 2 2 0 1 1 3 0 0 2 2 2 3 3 3 2 2 0 2 0 2 3 1 3 3 0 2 3 3 3 0 3 1 1 2 3 0 3 1 0 2 1 0 2 1 3 2 2 2 0 2 2 3 1 0 0 0 2 1 3 1 0 1 3 2 2 0 0 1 2 1 2 3 3 0 2 1 0 3 0 2 1 3 1 2 2 2 0 3 2 3 3 1 3 3 0 2 2 1 2 3 0 1 0 1 1 1 2 1 1 0 2 3 1 2 3 1 2 1 2 0 1 0 1 2 2 0 2 0 2 2 1 3 1 1 1 1 3 1 1 1 2 3 1 2 1 2 1 2 1 2 1 1 1 2 0 1 2 0 3 2 1 0 1 1 0 1 0 3 0 0 1 0 1 0 0 2 0 2 3 0 0 2 2 0 0 2 1 0 1 2 3 1 2 2 3 0 0 1 3 0 2 2 1 2 1 2 0 3 3 0 1 2 0 2 3 0 3 1 1 2 0 0 1 1 0 1 1 2 2 1 0 3 0 0 0 0 1 2 1 0 2 2 0 0 1 3 3 1 1 3 1 3 3 1 1 2 2 3 0 1 1 2 0 1 2 3 3 0 2 3 2 0 3 1 2 1 0 3 0 2 2 2 3 0 2 3 0 2 2 2 0 2 1 3 1 3 3 1 0 3 1 0 0 2 0 3 3 0 3 1 3 2 1 2 2 3 0 0 3 2 0 1 1 2 2 0 0 2 2 1 3 1 1 0 0 3 1 3 2 3 2 1 2 2 3 1 0 2 1 3 1 0 3 3 2 2 0 1 2 1 0 0 2 1 2 2 1 1 0 0 1 1 2 1 1 0 2 2 2 3 3 2 2 1 1 1 0 3 3 1 2 3 2 3 1 0 1 2 2 1 2 3 1 2 2 0 3 2 3 0 3 1 2 3 1 2 3 2 0 3 2 0 1 3 0 2 0 2 3 3 2 1 1 3 3 3 1 2 2 2 3 1 1 0 1 2 2 2 3 1 0 2 0 0 1 1 1 3 3 2 1 3 2 1 2 2 3 1 0 2 2 0 3 1 2 3 3 3 2 1 0 2 0 1 2 0 1 3 1 3 1 0 2 0 2 3 2 3 1 3 2 1 2 0 0 1 2 3 3 0 1 3 2 3 2 3 3 3 2 0 3 1 1 2 1 0 0 3 1 0 2 1 1 1 0 2 0 2 0 2 3 3 3 3 3 0 1 2 2 1 1 0 1 0 1 1 3 2 2 3 2 1 3 1 3 0 1 2 3 3 1 1 1 0 2 3 3 0 2 0 0 0 0 3 3 2 2 3 0 3 1 1 1 3 2 3 2 1 3 0 2 0 3 0 0 3 2 0 2 1 2 0 2 0 0 0 2 0 0 1 1 1 2 1 3 0 2 3 2 2 3 3 1 3 1 2 2 1 3 0 0 2 0 0 3 2 1 1 3 2 2 2 1 3 0 3 0 0 1 2 0 2 0 0 3 1 1 2 1 3 0 2 3 2 0 2 2 1 1 2 3 3 3 0 0 3 3 0 3 3 1 3 1 2 1 2 1 0 1 0 0 0 1 2 1 2 1 0 1 1 3 0 1 0 3 3 1 0 3 3 2 2 1 2 2 0 1 3 2 1 3 1 3 3 3 2 3 0 3 1 1 0 3 0 0 1 0 2 3 2 2 1 1 3 3 3 2 0 1 2 3 3 2 3 3 3 3 3 3 2 1 2 2 0 0 0 1 2 1 0 1 2 0 1 2 2 2 3 0 2 1 2 1 2 3 1 0 3 2 1 1 3 3 3 1 1 2 3 3 0 3 0 2 2 1 1 2 1 0 0 3 1 3 0 3 1 1 3 3 0 2 1 2 0 0 2 2 3 0 0 2 2 0 1 3 1 3 2 3 1 3 1 0 2 1 0 1 3 1 1 3 3 2 3 0 0 1 3 3 2 1 3 1 1 1 1 0 1 2 2 3 2 3 1 2 1 0 3 1 3 0 1 0 2 3 1 2 2 1 2 1 3 2 3 0 3 3 1 0 1 1 1 3 1 3 1 3 2 0 2 0 1 3 0 2 3 2 2 0 0 2 1 3 0 2 1 1 3 1 1 1 2 2 2 1 2 0 1 0 2 3 2 3 2 0 1 2 0 1 3 1 3 3 2 0 3 0 2 2 1 1 0 2 3 0 3 1 0 3 0 3 0 1 3 1 3 3 0 0 2 1 0 1 1 2 2 0 0 3 1 1 2 3 2 2 2 2 3 3 0 2 0 3 3 2 1 2 1 2 3 0 0 3 1 3 3 1 1 2 0 2 2 3 0 2 3 0 0 1 0 2 1 2 2 0 1 3 0 0 0 1 3 0 1 3 0 2 2 2 1 3 1 1 3 2 0 2 0 1 3 2 0 0 0 1 1 1 0 3 3 1 3 3 2 0 2 1 3 0 3 2 1 1 1 2 2 0 1 3 3 2 0 1 3 0 2 1 2 1 2 2 1 1 2 3 1 1 3 3 3 0 3 0 0 2 2 2 0 1 0 3 1 3 3 2 0 2 0 0 1 3 1 0 3 2 1 0 2 3 1 0 1 1 0 2 2 0 2 3 3 3 3 0 0 3 3 2 2 2 1 3 3 3 3 3 3 0 2 1 2 3 0 2 2 0 3 0 3 2 1 0 2 1 0 0 2 3 1 3 3 2 3 1 2 1 2 3 0 0 2 2 3 0 1 2 3 2 3 0 0 3 1 1 1 0 2 3 2 0 2 2 2 0 2 3 0 1 0 2 1 0 3

Expected Output:

1114

Your Program Output:

1126

5 Private (Hidden) Test Cases Failed.

0 Passed 5 Failed

`

CODE:

n=int(input())
ar=list(map(int, input().split()))
dp=n*[-1]
c=0
prev, dp[0]=ar[0],ar[0]
for i in range(1,n-1):
    if ar[i]==prev:
    dp[i]=0
    prev=dp[i]
    continue
    if ar[i]==0:
    dp[i]=0
    prev=0
    continue
    if ar[i]==3 and prev==0:
    if ar[i+1]==1:
       dp[i]=2
    elif ar[i+1]==2:
       dp[i]=1
    prev=dp[i]
    continue
    if ar[i]==3 and prev==1:
    dp[i]=2
    prev=dp[i]
    elif ar[i]==3 and prev=2:
    dp[i]=1
    prev=dp[i]
    else:
    dp[i]=ar[i]
    prev=dp[i]
if prev==ar[n-1]:
    dp[n-1]=0
else:
    dp[n-1]=ar[n-1]
for i in dp:
    if i==0:
    c+=1
print(c)

sorry guys i am newbie to dynamic programming i cant figure out what went wrong.....

Answer 1

This really has nothing to do with dynamic programming. You just iterating through the array, keeping track of how many days you've skipped, and what you're allowed to eat that day. Let's use the value 1, 2, and 3 to indicate what you're allowed to eat, in the same way it's used to keep track of what what the store serves.

allowed = 3
skipped = 0
for value in array_of_store_values:
    if value == 0:
        # Nothing there.  I have to skip.  Tomorrow I'll eat anything
        skipped += 1 
        allowed = 3 
    elif value in (1, 2):  # restaurant only has one flavor
        if allowed in (value, 3): 
            # I can eat the restaurant's flavor.  Tomorrow the other
            allowed = 3 - value
        else:
            # No ice cream today
            skipped += 1
            allowed = 3
    else:
        # The restaurant has both.  If I'm allowed to eat anything, then
        # I can delay my decision on what to eat today until I found out what
        # they have tomorrow.  But if I'm only allowed to eat one flavor, 
        # eat it, and tomorrow I have to eat the other.
        if allowed != 3:
            allowed = 3 - allowed

print(skipped)