HMMT 二月 2017 · 冲刺赛 · 第 17 题
HMMT February 2017 — Guts Round — Problem 17
题目详情
英文原题
- [ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . Asubstring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has
10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinctsubstrings of the string Sean is looking at?
解析
英文解析
- [ 10 ] Sean is a biologist, and is looking at a string of length 66 composed of the letters A, T, C, G . Asubstring of a string is a contiguous sequence of letters in the string. For example, the string AGT C has
10 substrings: A, G, T, C, AG, GT, T C, AGT, GT C, AGT C. What is the maximum number of distinctsubstrings of the string Sean is looking at?
Proposed by: Yang Liu
Answer: 2100
Let’s consider the number of distinct substrings of length. On one hand, there are obviously at most
4 distinct substrings. On the other hand, there are 67 − ` substrings of length ` in a length 66 string.
Therefore, the number of distinct substrings is at most
∑66
min(4 , 67 −) = 2100 .
` =1
To show that this bound is achievable, one can do a construction using de brujin sequences that wewon’t elaborate on here.