시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 (추가 시간 없음) 1024 MB197736.842%

문제

Being a renowned Bacteria and Protein Collector, you are leading research into the spread of bacteria and virus proteins. As part of this research, public locations spread over the entire world have been swabbed for DNA samples.

The sequenced DNA samples have just come back from the lab, and you would now like to prove your hypothesis that even though the samples have been taken in different continents, they are still related.  However, as it turns out, they are not related. In fact, the samples are independent uniformly random DNA sequences containing characters in "ACGT".  This means that each character in each sequence has a probability of exactly $25\%$ of being each of 'A', 'C', 'G', or 'T'.

Nevertheless, you would still like to convince your colleagues that the samples are related. You decided that two pieces of DNA are related when they share at least half of their code: if the sequences both have length $n$ they are related when they share a common subsequence1 of length at least $\frac 12 n$.

Given two independent uniformly random DNA sequences $A$ and $B$, your task is to find a common subsequence to prove that they are related. You already did some analysis, and confirmed that the probability of failure is in fact less than $10^{-1000}$ per instance when $n=10^6$.

1A sequence $S$ is a subsequence of a sequence $A$ when $S$ can be obtained from $A$ by deleting some or none of the elements of $A$ while preserving the order of the remaining elements.

입력

The input consists of:

  • One line with an integer $n$, the length of the DNA sequences.
  • One line with a string $A$ consisting of $n$ independent uniformly random characters in "ACGT".
  • One line with a string $B$ consisting of $n$ independent uniformly random characters in "ACGT".

Your submission will be run on exactly $100$ test cases, all of which will have $n=10^6$. The samples are smaller and for illustration only.

Each of your submissions will be run on new random test cases.

A testing tool is provided to run your submission on large random inputs. It does not verify the correctness of your answer.

출력

Output a common subsequence of length at least $\frac 12 n$.

If there are multiple valid solutions, you may output any one of them.

예제 입력 1

20
TCCGATCGCTCTAGAACTAG
CTCACTAGCTCTTCGCCGAC

예제 출력 1

TCATGCTCTGCG

예제 입력 2

20
AGGCTTGAACGATAGACAAC
AGCTAAAGCTAGCTAGACTT

예제 출력 2

AGCTAACATAGAC

출처

ICPC > Regionals > Europe > Northwestern European Regional Contest > Benelux Algorithm Programming Contest > BAPC 2021 E번

  • 문제를 만든 사람: Ragnar Groot Koerkamp

채점 및 기타 정보

  • 예제는 채점하지 않는다.