程序设计在线评测(Online Judge)


问题 1061. -- 2010欧洲西南分区赛:Palindromic DNA

1061: 2010欧洲西南分区赛:Palindromic DNA

时间限制: 1 Sec  内存限制: 128 MB
提交: 0  解决: 0
[提交][状态][讨论版]

题目描述

A DNA sequence is composed of a series of four possible nucleobases, namely Adenine, Guanine, Thymine
and Cytosine; we will refer to each of these bases by their initial. For our purposes, nucleobases have
an associated cyclic \order": A is followed by G, which in turn is followed by T, which is followed by C,
which is followed by A again. State-of-the-art research in genomics has revealed the startling fact that many
diseases are caused by certain subsequences of bases not forming a palindromic sequence! Your mission as
a leading researcher at ICPC laboratories is to take a DNA string S and a series of subsets P1; : : : ; Pt of
indices to characters (nucleobases) in S, and transform S so that each of the restrictions of the resulting
string to P1; : : : ; Pt are palindromic. (The restriction of S to a subset P = fi1; i2; : : : ; ikg of indices, where
0 <= i1 < i2 < : : : < ik < jSj, is the string Si1Si2 : : : Sik ). It is possible to inspect any base of S at will, but
only three transformations can be applied to a base:
1. Leave it unaltered.
2. Increase it by 1 in the cyclic order of nucleobases (e.g. turn C into A).
3. Decrease it by 1 (e.g. turn T into G).
Moreover, owing to limitations of current technology, it is impossible to modify two bases in consecutive
positions of the sequence. Is our goal achievable?
By way of example, consider DNA sequence AGTAT. Number positions starting from 0, and suppose we
have the three subsets P1 = f1; 4g, P2 = f0; 1g and P3 = f0; 2; 4g. One solution is to increase the rst
character and decrease the last, yielding S0 = GGTAG. The restrictions of S0 to P1, P2 and P3 are GG, GG and
GTG, respectively; all of them are palindromic.
One case where no solution is possible is when the string is CATGC, and we require the subsequences
determined by positions f0; 3g and f3; 4g be palindromic. Here, characters 3, 0 and 4 would

输入

The rst line of each test case has two integers N and T (1 <= N <= 10 000; 1 <= T <= 6 000), the sequence
length and number of subsets to consider. The next line contains the DNA sequence of length N, all of
whose characters are in ACGT. The subsets are described by the following T lines. Each line starts by \L:",
where L (0 <= L <= N) is the number of positions in the subset, and is followed by T distinct integers between
0 and N

输出

In a single line per test case, print YES if the task is solvable and NO otherwise.

样例输入

5 3
AGTAT
2: 1 4
2: 0 1
3: 0 2 4

5 3
CATGC
0:
2: 0 3
2: 3 4

0 0

样例输出

YES
NO

提示

来源

[提交][状态][讨论版]