usaco-1-1-prob4-dp

Posted on In Disqus:

Here is a very beautiful solution using dynamic programming with $O(n)$ time complexity.

Prob 4. Broken Necklace

I get a very elegant solution using dynamic programming idea. Just with a $O(n)$ time complexity.

  • Create a new variable type as NODE, storing the left hand side and right hand side beads with red and blue color.

  • We cut the necklace into a linear string, then find another one to link it.

    • Why we do this?

      Because we want to find the correct count of left/right hand side beads.

    • What will happen if there is just one necklace not two?

      Then think about the bead count on the left or right side.

      Left side end cannot count left hand side beads, although it should be a rounded necklace rather than a linear string.

      It is the same for the right hand side beads.

  • From left to right, count the left hand side beads with dp transform function:

    1
    2
    3
    4
    5
    6
    if beads[i - 1] == 'r'
        neck[i].left_hand_side_blue_num = 0
        and neck[i].left_hand_side_red_num = neck[i - 1].left_hand_side_red_num
    if beads[i - 1] == 'b'
        neck[i].left_hand_side_red_num = 0
        and neck[i].left_hand_side_blue_num = neck[i - 1].left_hand_side_blue_num

  • From right to left, count the right hand side beads with dp transform function. (you can think about it, read the code, or see the dp transform function I wrote for left to right direction)

  • Finally, let’s count!

    Remember that there only need to read beads_num - 1 times, since we only need to count one end for one direction, so we omitted the other end.

    So left hand side count need only considering the left side of the string, from bead_num + 1 to 2 * bead_num - 1.

    So right hand side count only consider the right side of string, from 0 to beads_num - 1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
/*
ID:
LANG: C
PROG: beads
*/

#include <stdio.h>
#include <stdlib.h>

#define max(a, b) (((a) > (b)) ? (a) : (b))

typedef struct node {
    int lhs_rnum;
    int lhs_bnum;
    int rhs_rnum;
    int rhs_bnum;
} NODE;

int main() {
    FILE *fin = fopen("beads.in", "r");
    FILE *fout = fopen("beads.out", "w");
    int bead_num;
    char beads[800];
    fscanf(fin, "%d", &bead_num);
    fscanf(fin, "%s", beads);
    for (int i = 0; i < bead_num; i++)
        beads[bead_num + i] = beads[i];
    int max_len = 0;
    NODE necklace[800];
    necklace[0].lhs_bnum = 0, necklace[0].lhs_rnum = 0;
    for (int i = 1; i < 2 * bead_num; i++) {
        if (beads[i - 1] == 'r')
            necklace[i].lhs_bnum = 0,
				necklace[i].lhs_rnum = 1 + necklace[i - 1].lhs_rnum;
        else if (beads[i - 1] == 'b')
            necklace[i].lhs_bnum = necklace[i - 1].lhs_bnum + 1,
				necklace[i].lhs_rnum = 0;
        else if (beads[i - 1] == 'w')
            necklace[i].lhs_bnum = necklace[i - 1].lhs_bnum + 1,
				necklace[i].lhs_rnum = necklace[i - 1].lhs_rnum + 1;
    }
    necklace[2 * bead_num - 1].rhs_rnum = 0, necklace[2 * bead_num - 1].rhs_bnum = 0;
    for (int i = 2 * bead_num - 2; i >= 0; i--) {
        if (beads[i + 1] == 'r')
            necklace[i].rhs_rnum = 1 + necklace[i + 1].rhs_rnum,
				necklace[i].rhs_bnum = 0;
        else if (beads[i + 1] == 'b')
            necklace[i].rhs_rnum = 0,
				necklace[i].rhs_bnum = necklace[i + 1].rhs_bnum + 1;
        else if (beads[i + 1] == 'w')
            necklace[i].rhs_rnum = necklace[i + 1].rhs_rnum + 1,
				necklace[i].rhs_bnum = necklace[i + 1].rhs_bnum + 1;
    }
    for (int i = 0; i < bead_num - 1; i++)
        max_len = max(max_len,
                      max(necklace[bead_num + i + 1].lhs_rnum,
                          necklace[1 + bead_num + i].lhs_bnum)
                      + max(necklace[i].rhs_rnum, necklace[i].rhs_bnum));
    if (max_len < bead_num)
        fprintf(fout, "%d\n", max_len);
    else
        fprintf(fout, "%d\n", bead_num);
    exit(0);
}