UVA - 11583 - Alien DNA 

This article will explain my thought process to solve a problem called Alien DNA (PDF) from UVA Online Judge. Read the original problem statement before reading this article.

Keywords: Greedy, Bit Manipulation, Bitmask

Problem Summary 

Given:

  1. Length of a DNA Strand.

  2. DNA Strand of an Alien.

We want to:

  1. Find the minimum total cuts to form a segments.

Glossary 

  1. Greedy — A strategy to choose the locally optimal option at each step, in assumption that it will eventually lead to a globally optimal solution.

  2. Bit Manipulation — A technique of using bitwise operations to manipulate individual bits in a binary data.

  3. Bitmask — A binary representation of a data that can be manipulated using bitwise operations.

Observation 

First, we need to have a clear definition over the terms that are being used on the documents.

  1. Strand — A sequence of Base Sets (e.g. [ab], [ab, abc], [abcd, ab]).

  2. Base Set — A unique list of Base (e.g. ab, abc, a).

  3. Base — A lowercase letter (e.g. a, b, c).

  4. Segment — A contiguous sub-sequence of a strand that with shared base (e.g. [ab, ac, ad], [zxy, xya, xb]).

Next, since we only have 26 possible values of base (a to z), we could model the base set as an integer bitmask. This will enable us to find a shared base between 2 base sets in a single operation.

Last, to minimize the total cuts, use greedy strategy to form the longest possible segments from the first until the last sequence of the base sets. Use bit manipulation on the bitmask to keep track of the shared base on each iteration.

Algorithm 

To transform the base set into integer bitmask, we need to define what each bit of the bitmask represent. 0-th bit represent the existence of base a, 1-st bit represent the existence of base b, and so on. We could transform the base set into bitmask by setting the N-th bit to 1 for each base. This can be achieved using OR and bitwise shift operator.

Next, we want to form the longest possible segments while keeping track of the shared base. We could do this by doing greedy linear scan from the first until the last sequence of the base sets. Use AND operator to extract the shared base on each iteration. If the base set doesn’t share any base with its predecessor, cut the strand and start a new segment.

The time complexity of this solution is O({strand length}) or O(10^4).

Implementation 

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * 11583 - Alien DNA
 * Time limit: 1.000 seconds
 * https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2630
 */
public class Main {
    public static void main(final String... args) {
        final Scanner in = new Scanner(new BufferedInputStream(System.in));
        final PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));
        final Process process = new Process();

        final int totalTestCases = in.nextInt();
        for (int i = 0; i < totalTestCases; i++) {
            final Input input = new Input();
            input.strandLength = in.nextInt();
            input.strand = new String[input.strandLength];
            for (int j = 0; j < input.strandLength; j++) {
                final String baseSet = in.next();
                input.strand[j] = baseSet;
            }

            final Output output = process.process(input);
            out.println(output.totalCuts);
        }

        in.close();
        out.flush();
        out.close();
    }
}

class Input {
    public int strandLength;
    public String[] strand;
}

class Output {
    public int totalCuts;
}

class Process {
    private static final int ONE_BITMASK = -1;

    public Output process(final Input input) {
        final Output output = new Output();
        output.totalCuts = 0;

        final int[] strand = new int[input.strandLength];
        for (int i = 0; i < input.strandLength; i++) {
            strand[i] = toBitmask(input.strand[i]);
        }

        for (int i = 0; i < strand.length; ) {
            int segment = ONE_BITMASK;

            for (; i < strand.length; i++) {
                final int baseSet = strand[i];
                final boolean hasCommonBase = (segment & baseSet) > 0;

                if (hasCommonBase) {
                    segment &= baseSet;
                } else {
                    output.totalCuts++;
                    break;
                }
            }
        }

        return output;
    }

    private int toBitmask(final String text) {
        int bitmask = 0;
        for (char letter : text.toCharArray()) {
            final int bit = letter - 'a';
            bitmask |= (1 << bit);
        }
        return bitmask;
    }
}


Powered by Docmost