Virus Evolution (APCS 2020-07 Expert)

Points 100 0.5s 256M

Scientists have discovered \(n\) viruses numbered from \(1\) to \(n\). Each virus is represented by an RNA sequence: a string of length \(m\) containing only A, U, C, G, and @. The character @ marks an unobserved position and may be replaced by any one of A, U, C, or G.

The evolutionary relationships of the viruses are also known. Except for one original virus, every virus evolved from another virus, so these relationships form a rooted tree.

Virus family tree

The distance between two RNA sequences is their Hamming distance: the number of positions at which their characters differ. More precisely, for two sequences \(a\) and \(b\) of length \(m\), the distance is the number of positions \(i\) satisfying \(a_i\ne b_i\).

Replace every @ in every RNA sequence independently with one of A, U, C, or G. Minimize the sum of the distances between every virus and the virus from which it evolved, and output this minimum value.

Input Format

The first line contains two positive integers \(n\) and \(m\).

Each of the next \(n\) lines contains two integers \(i\) and \(j\), followed by a string \(s\). Virus \(i\) evolved from virus \(j\), and the RNA sequence of virus \(i\) is \(s\).

For the original virus, \(j=i\). Exactly one such virus exists, every virus number appears exactly once, and the evolutionary relationships form a tree.

Output Format

Output one integer: the minimum possible sum of distances between every virus and its evolutionary source. The original virus contributes no distance.

Constraints

  • \(1\le n\le1000\)
  • \(1\le m\le80\)
  • Every sequence has length exactly \(m\) and contains only A, U, C, G, and @
  • The memory limit is 256 MB
  • The time limit is 0.5 seconds per test case
Subtasks
Subtask Points Additional constraints
1 20 No RNA sequence contains @, and every non-root virus satisfies \(j<i\)
2 40 Every non-root virus satisfies \(j<i\)
3 40 No additional constraints

The official evaluation contains 20 scored test cases, each worth 5 points.

Sample Input 1

2 3
1 1 AAC
2 1 A@@

Sample Output 1

0

Sample Input 2

6 1
1 1 @
2 1 @
3 1 C
4 1 C
5 2 A
6 2 A

Sample Output 2

1

Source

APCS July 2020 Programming Problem 4, "Virus Evolution," also available as ZeroJudge f582.

Problem page help

Keyboard shortcuts

Main features

  • Sample tests — Runs the sample cases bundled with the problem and auto-compares against the expected output.
  • Custom test — Run your code with your own stdin. Optionally tick the "Compare with expected (diff)" box to verify against expected output line-by-line.
  • Template — Paste the default code template you set on your profile page.
  • Collab — Edit this problem together with classmates in real time.
  • Auto-draft — Editor contents auto-save to your browser every 1.5 seconds (per account / problem / language).
  • Submit — Send your code to the judge for grading; returns AC / WA / TLE etc.

Limits

  • Source code: at most 65,536 characters
  • Custom test stdin and expected output: at most 1 MB each (≈1 million characters)
  • Custom test and sample test share the sandbox; about 1 request per 3 s per user (sample test: 1 per 1 s)
  • Custom test and sample test both have a 15 second wall-clock cap (the official judge still uses the problem time limit)
  • Interactive problems do not offer custom test (cannot simulate interaction with the judge).
  • Submitting has no rate limit, but rapid repeated submissions on the same problem are treated as score farming.