CF 102697125 - Chord Identification

We receive three musical notes that form a major triad. The notes may be written in any order, and a note can use either sharp notation such as C or flat notation such as Df. We need to determine which of the three notes is the root.

codeforcescompetitive-programming

CF 102697125 - Chord Identification

Rating: -
Tags: -
Solve time: 47s
Verified: yes

Solution

Problem Understanding

We receive three musical notes that form a major triad. The notes may be written in any order, and a note can use either sharp notation such as C# or flat notation such as Df. We need to determine which of the three notes is the root.

The twelve pitch classes in one octave can be assigned the integer values 0 through 11:

C, C#, D, D#, E, F, F#, G, G#, A, A#, B.

Two notes one half step apart have consecutive values, with the octave wrapping from B back to C. A major chord whose root has value r contains the three pitch classes r, r + 4, and r + 7, with all arithmetic taken modulo 12. The input can contain those three notes in any permutation.

The notation creates one implementation detail that is easy to miss. C# and Df represent the same pitch class, as do D# and Ef, F# and Gf, G# and Af, and A# and Bf. We must convert both spellings to the same numerical value for comparison, but when we output the root, we should print the original spelling that appeared in the input.

There are only three notes and only twelve possible pitch classes. The constraints are consequently tiny, so there is no risk of a conventional linear or quadratic algorithm being too slow. Even an exhaustive search over every possible root performs only a constant number of operations. The useful goal here is not asymptotic optimization, but reducing the problem to a clean interval check that is difficult to get wrong.

A first edge case is a chord whose root is not the first input note. For example,

E G C

has values 4, 7, 0. The correct output is C. An implementation that assumes the first note is the root would incorrectly print E.

A second edge case is a flat spelling of a pitch class. For example,

Bf Ef G

represents the values 10, 3, 7, which are the notes of an E-flat major chord. The correct output is Ef. If Bf and Ef are treated as unrelated strings instead of converting flats to their pitch classes, the interval test cannot work correctly.

A third edge case occurs across the octave boundary. For example,

B D# F#

represents values 11, 3, 6. The root is B, because 11 + 4 = 15, which is 3 modulo 12, and 11 + 7 = 18, which is 6 modulo 12. A careless implementation using ordinary integer differences without modulo arithmetic could reject this valid chord.

A fourth edge case is another inversion where the fifth appears first:

G C E

The correct output is C. Sorting the notes numerically and assuming the smallest pitch is the root would also fail in other inversions, because the root is a musical pitch class rather than necessarily the first or smallest input value.

Approaches

The most direct brute-force solution is to try every one of the twelve pitch classes as a possible root. For a candidate root r, the corresponding major chord must contain exactly r, (r + 4) mod 12, and (r + 7) mod 12. We compare those three values with the three input notes. Since there are twelve candidates and three notes, the worst case performs at most 36 basic membership comparisons, plus the small amount of arithmetic needed to construct each candidate chord. This is already constant time and is easily fast enough.

The brute-force method is correct because the problem guarantees that the input is a major chord and that its root is one of the three supplied notes. Exactly one candidate root therefore describes the given set of pitch classes.

We can make the search smaller by using that final guarantee. Instead of trying all twelve pitch classes, only the three input notes can be roots. For each of those three candidates, we check whether the other two notes are exactly four and seven half steps above it. The candidate root r is valid precisely when the input pitch-class set equals {r, r + 4, r + 7} modulo 12.

The observation that a major triad has a fixed interval pattern is the key simplification. We do not need to reason about the order in which the notes were supplied, and we do not need to distinguish between different inversions. Once every spelling has been mapped to a pitch class, the chord is just a three-element set with a known pattern.

Approach Time Complexity Space Complexity Verdict
Brute Force over all 12 roots O(1) O(1) Accepted
Test the 3 supplied notes as roots O(1) O(1) Accepted

The second approach is preferable because it directly uses the structure promised by the input and makes the correctness argument straightforward.

Algorithm Walkthrough

  1. Create a mapping from every possible input spelling to its pitch-class number from 0 to 11. For example, C maps to 0, C# and Df both map to 1, and B maps to 11.
  2. Read the three note strings and convert each one to its numerical pitch class. Keep the original strings as well, because the required output should use the spelling supplied for the root.
  3. Put the three numerical values into a set. The input describes three distinct notes of a major chord, so this set represents the complete collection of pitch classes in the chord.
  4. Try each of the three input notes as a possible root. For a candidate value r, construct the expected major triad {r, (r + 4) % 12, (r + 7) % 12}.
  5. Compare the expected triad with the input set. If they are equal, the candidate is the root, so output its original input spelling.
  6. Since the input is guaranteed to be a valid major chord, one of the three candidates must succeed. No fallback case is needed for valid judge data.

Why it works

For every candidate r, the algorithm accepts it exactly when the three input pitch classes are {r, r + 4, r + 7} modulo 12. That is precisely the definition of a major triad with root r. The actual root is guaranteed to be among the three input notes, so the algorithm eventually tests it and accepts it. A non-root input note cannot pass the same test because shifting that note by four and seven half steps would produce a different major-triad pattern. Thus the returned candidate is the root, and the original spelling attached to that candidate is the required output.

Python Solution

import sys
input = sys.stdin.readline

NOTE_VALUE = {
    "C": 0,
    "C#": 1,
    "Df": 1,
    "D": 2,
    "D#": 3,
    "Ef": 3,
    "E": 4,
    "F": 5,
    "F#": 6,
    "Gf": 6,
    "G": 7,
    "G#": 8,
    "Af": 8,
    "A": 9,
    "A#": 10,
    "Bf": 10,
    "B": 11,
}

def solve():
    notes = input().split()
    values = [NOTE_VALUE[note] for note in notes]
    chord = set(values)

    for i, root in enumerate(values):
        expected = {
            root,
            (root + 4) % 12,
            (root + 7) % 12,
        }

        if expected == chord:
            print(notes[i])
            return

if __name__ == "__main__":
    solve()

The NOTE_VALUE dictionary handles both sharp and flat spellings. Multiple strings can map to the same integer because enharmonic notes have the same pitch class for this problem.

The original notes list is preserved separately from values. This is necessary because if the input contains Ef, the required answer is Ef, not some canonical spelling such as D#.

The set chord removes ordering from the input. For a candidate root, the expected major chord is also represented as a set, so the comparison does not depend on whether the input was given in root position, first inversion, or second inversion.

The additions by 4 and 7 are performed modulo 12. This handles chords crossing from B back to C, such as the B major chord B D# F#.

There are no integer-overflow concerns because every value is between 0 and 11, and Python integers also handle arbitrary precision. The loop has exactly three iterations, so no additional optimization is necessary.

Worked Examples

For the first sample,

E G C

the converted values are 4, 7, 0.

Candidate index Input note Root value Expected major triad Matches input?
0 E 4 {4, 8, 11} No
1 G 7 {7, 11, 2} No
2 C 0 {0, 4, 7} Yes

The third candidate produces exactly the input pitch classes, so the algorithm prints the original spelling C. This demonstrates why input order cannot be used to identify the root.

For the second sample,

Bf Ef G

the converted values are 10, 3, 7.

Candidate index Input note Root value Expected major triad Matches input?
0 Bf 10 {10, 2, 5} No
1 Ef 3 {3, 7, 10} Yes

The second candidate succeeds. Its original spelling is Ef, so the output is Ef. The trace also demonstrates why the conversion of flat notation must happen before interval comparisons.

For the boundary case,

B D# F#

the values are 11, 3, 6.

Candidate index Input note Root value Expected major triad Matches input?
0 B 11 {11, 3, 6} Yes

Here (11 + 4) % 12 becomes 3, showing why modular arithmetic is necessary when a chord crosses the end of the twelve-note octave.

Complexity Analysis

Measure Complexity Explanation
Time O(1) Only three notes are converted and at most three candidate roots are checked.
Space O(1) The algorithm stores three notes and a set containing at most three pitch classes.

The input itself has a fixed size of three notes, and the musical alphabet has only twelve pitch classes. The solution therefore stays constant in both time and memory, comfortably within the one-second and 256 MB limits of the problem.

Test Cases

import sys
import io

NOTE_VALUE = {
    "C": 0,
    "C#": 1,
    "Df": 1,
    "D": 2,
    "D#": 3,
    "Ef": 3,
    "E": 4,
    "F": 5,
    "F#": 6,
    "Gf": 6,
    "G": 7,
    "G#": 8,
    "Af": 8,
    "A": 9,
    "A#": 10,
    "Bf": 10,
    "B": 11,
}

def solve():
    notes = input().split()
    values = [NOTE_VALUE[x] for x in notes]
    chord = set(values)

    for i, root in enumerate(values):
        expected = {
            root,
            (root + 4) % 12,
            (root + 7) % 12,
        }
        if expected == chord:
            print(notes[i])
            return

def run(inp: str) -> str:
    global input
    old_stdin = sys.stdin
    old_input = input

    sys.stdin = io.StringIO(inp)
    input = sys.stdin.readline

    try:
        solve()
        return sys.stdout.getvalue() if False else ""
    finally:
        sys.stdin = old_stdin
        input = old_input

def run(inp: str) -> str:
    old_stdin = sys.stdin
    old_stdout = sys.stdout

    sys.stdin = io.StringIO(inp)
    sys.stdout = io.StringIO()

    try:
        solve()
        return sys.stdout.getvalue()
    finally:
        sys.stdin = old_stdin
        sys.stdout = old_stdout

# Provided samples
assert run("E G C\n") == "C\n", "sample 1"
assert run("Bf Ef G\n") == "Ef\n", "sample 2"
assert run("C F A\n") == "F\n", "sample 3"
assert run("C# F Af\n") == "C#\n", "sample 4"

# Custom cases
assert run("C E G\n") == "C\n", "root appears first"
assert run("G C E\n") == "C\n", "root appears in the middle"
assert run("B D# F#\n") == "B\n", "octave boundary"
assert run("Df F Af\n") == "Df\n", "flat spelling"

def run_all_tests():
    tests = [
        ("E G C\n", "C\n"),
        ("Bf Ef G\n", "Ef\n"),
        ("C F A\n", "F\n"),
        ("C# F Af\n", "C#\n"),
        ("C E G\n", "C\n"),
        ("G C E\n", "C\n"),
        ("B D# F#\n", "B\n"),
        ("Df F Af\n", "Df\n"),
    ]

    for inp, expected in tests:
        assert run(inp) == expected

run_all_tests()

The first custom case checks the ordinary root-position chord. The second checks an inversion where the root is not the first input note. The third checks modular arithmetic at the B to C boundary. The fourth checks flat notation and verifies that the original spelling is returned rather than a different enharmonic spelling.

The test harness intentionally keeps the solver logic identical to the submitted solution. In an actual contest submission, only the solve function, mapping, and standard input setup are needed.

Test input Expected output What it validates
C E G C Root in the first position
G C E C Root in the middle of an inversion
B D# F# B Modulo 12 at the octave boundary
Df F Af Df Flat spelling and original-output preservation

An all-equal input such as C C C is not a valid test under the problem's guarantee, because three identical notes cannot form a major triad. The same applies to any malformed input that does not contain the three distinct pitch classes of a major chord. A correct contest solution can rely on the guarantee instead of inventing behavior for invalid data.

Edge Cases

The first edge case is an inversion. With

E G C

the values are 4, 7, 0. The algorithm first tests E, expecting {4, 8, 11}, which does not match. It then tests G, expecting {7, 11, 2}, which also fails. Finally it tests C, expecting {0, 4, 7}, exactly the input set. It outputs C. The crucial property is that the algorithm treats the three notes as a set, so their input order has no effect.

The second edge case is enharmonic spelling. With

Bf Ef G

the dictionary converts Bf to 10, Ef to 3, and G to 7. Testing Ef gives (3 + 4) % 12 = 7 and (3 + 7) % 12 = 10, producing {3, 7, 10}. That equals the input set, so the algorithm outputs the original string Ef. Converting the notes to numbers while retaining their original strings handles both comparison and output correctly.

The third edge case crosses the end of the octave. With

B D# F#

the root candidate B has value 11. Its third is (11 + 4) % 12 = 3, which is D#, and its fifth is (11 + 7) % 12 = 6, which is F#. The expected set is {11, 3, 6}, exactly the input. Without modulo arithmetic, the third and fifth would incorrectly appear to lie outside the octave.

The fourth edge case concerns a root that is neither the first nor the smallest numerical note. With

G C E

the values are 7, 0, 4. The candidate G fails because its expected major triad is {7, 11, 2}. The candidate C succeeds with {0, 4, 7}, so the answer is C. This is why sorting the values and assuming the first sorted value is the root would be an invalid shortcut.

The algorithm also naturally handles the case where the root is already first, such as

C E G

Here the first candidate immediately produces {0, 4, 7}, so C is returned. The same invariant is used regardless of the input ordering: a candidate is accepted only when its four-half-step and seven-half-step intervals generate exactly the three supplied pitch classes.