2015 Feb Bronze Problem 2 COW

Official Problem Statement

COW

Problem

The task is to find all subsequences of the word "COW" in a given string.

The given string consists only of the characters 'C', 'O', and 'W'.

Subsequences do not have to be contiguous; for example, in the string "COWOC", there are two subsequences of "COW" - the characters at positions 1, 2, 3 and the characters at positions 1, 4, 5.

The length of the string is at most 1000.

Solution

A simple solution is to iterate over the string from left to right, keeping track of the number of 'C's, 'CO's, and 'COW's seen so far.

For each character:

• If it is a 'C', increment the number of 'C's.
• If it is an 'O', increment the number of 'CO's by the number of 'C's.
• If it is a 'W', increment the number of 'COW's by the number of 'CO's.

In this way, the number of 'COW's at the end will be the total number of subsequences "COW" in the string. This algorithm works because it counts all the ways to choose a 'C' and an 'O' for every 'W'.

This solution works in O(n) time where n is the length of the string.

Code

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    freopen("cow.in", "r", stdin);
    freopen("cow.out", "w", stdout);

    int length;
    string sequence;
    cin >> length >> sequence;

    long long countC = 0;
    long long countCO = 0;
    long long countCOW = 0;

    for (int i = 0; i < length; i++) {
        if (sequence[i] == 'C') {
            countC++;
        } else if (sequence[i] == 'O') {
            countCO += countC;
        } else if (sequence[i] == 'W') {
            countCOW += countCO;
        }
    }

    cout << countCOW << endl;
    return 0;
}

Java

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new FileReader("cow.in"));
        BufferedWriter bw = new BufferedWriter(new FileWriter("cow.out"));

        int length = Integer.parseInt(br.readLine());
        String sequence = br.readLine();

        long countC = 0;
        long countCO = 0;
        long countCOW = 0;

        for (int i = 0; i < length; i++) {
            if (sequence.charAt(i) == 'C') {
                countC++;
            } else if (sequence.charAt(i) == 'O') {
                countCO += countC;
            } else if (sequence.charAt(i) == 'W') {
                countCOW += countCO;
            }
        }

        bw.write(Long.toString(countCOW));
        bw.newLine();

        br.close();
        bw.close();
    }
}

Python

with open('cow.in', 'r') as fin:
    length = int(fin.readline().strip())
    sequence = fin.readline().strip()

count_C = 0
count_CO = 0
count_COW = 0

for i in range(length):
    if sequence[i] == 'C':
        count_C += 1
    elif sequence[i] == 'O':
        count_CO += count_C
    elif sequence[i] == 'W':
        count_COW += count_CO

with open('cow.out', 'w') as fout:
    fout.write(str(count_COW) + '\n')