lundi 24 février 2020

DP approach to calculate maximum length of beads

I am trying to solve the USACO problem beads. In this problem, you are given a string of beads, and you have to find the maximum consecutive pair of red and blue beads.

Example: IF you were given the string wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb, the maximum length would be 11 as you would split the string at these two intervals wrwrrbwwwbb The w counts as both a red or blue bead, depending on what is favorable to you.

My solution is to have a count where I sort of split up each of the sections into different colors and then progressively add them and get the overall max.

Ex: IF we were using the string "rrbbwwrrb", my possible list of counts would be [6,5] My different sections would be rrbbww, bbwwrr, and wwrrb.

Logically this seems like the correct solution, but it is the coding part of it that is stumping me. Here is my code:

neck = "wwwbbrwrbrbrrbrbrwrwwrbwrwrrbwwwbbrwrbrbrrbrbrwrwwrbwrwrrb"
n = len(neck)
maxi = -1 #max length
c = 0 #counter 
changes = 1 #number of color swaps
curr = 0 #each part

color = None

for i in range(n):
    if neck[i] == 'w':
        c += 1
        if changes == 2:
            curr += 1
    elif neck[i] == color:
        c += 1
        if changes == 2:
            curr += 1
    else:
        if changes == 3:
            color = neck[i]
            maxi = max(c,maxi)
            #print(str(c) + str(" ") + str(i))
            c = 1
            curr = 1
            changes = 1
        else:
            color = neck[i]
            c += 1
            if changes == 2:
                curr += 1
            changes += 1
print(maxi)

The correct answer is 11, but my coded solution reports 9.

Aucun commentaire:

Enregistrer un commentaire