← CSES Better

COW

USACO · 2015 · February · bronze-2

Open official problem ↗
Ask AI

Open a hint-first prompt in a new AI chat. Grok may ask you to confirm before sending.

Open Claude Desktop

strings · subsequence-counting

The organizer’s problem statement is available at the official source link.

sample trace

COW: count ordered subsequences

Maintain counts for C, CO, and COW while scanning COOWWW. Each new character extends every matching partial subsequence seen before it.

sample

COOWWW

states

  • prefix
    C
    C
    1
    CO
    0
    COW
    0
  • prefix
    CO
    C
    1
    CO
    1
    COW
    0
  • prefix
    COO
    C
    1
    CO
    2
    COW
    0
  • prefix
    COOW
    C
    1
    CO
    2
    COW
    2
  • prefix
    COOWW
    C
    1
    CO
    2
    COW
    4
  • prefix
    COOWWW
    C
    1
    CO
    2
    COW
    6

answer

6
  1. 1

    Count C

    Each C starts one subsequence; the sample begins with one C.
  2. 2

    Extend to CO

    Each O extends all earlier C subsequences. The two Os leave 2 ways to form CO.
  3. 3

    Extend to COW

    Each W extends every earlier CO. Three Ws add 2 each, giving 6 COW subsequences.
Tools
1
2
3
4
5
6
7
8
9
10
11
12
Draft saved locally
|12 lines, 156 chars

Run output

Run your code to see output.