## COCI '18 Contest 5 #3 Ispit

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

After 26 years of studying, little Mirko took his potentially last exam. He confidently took his seat, sharpened his pencil and waited calmly for the professor's permission to start writing – after all, that was his favorite subject, Data Structures and Algorithms. But, as in any good story, this one also has that but… Namely, when he got his exam, Mirko could not even comprehend what was written in it.

He only saw a meaningless matrix of letters with rows and columns.

Since the professor forbids leaving the classroom during the exam, Mirko decided to spend hours coming up with his own task. Mirko was wondering if it is possible to select consecutive columns of the matrix so that, after arbitrarily shuffling letters in the selected columns' rows, there are two equal rows in the matrix (note that the entire rows must be equal, not just their letters in the selected columns). Shuffling is allowed only inside of the same row within selected columns and it is possible that a row remains unchanged after such operation.

#### Input

In the first line of the input there are two integer numbers and .

The following rows contain lowercase letters of the English alphabet describing the matrix of the letters Mirko saw in the exam.

#### Output

Print DA (Croatian for yes) if it is possible to select the consecutive columns that meet the conditions of the task. Otherwise print NE (Croatian for no).

#### Scoring

In the test samples totally worth 30% of the points, it will hold .

In the test samples totally worth additional 40% of the points, it will hold .

#### Sample Input 1

4 2
abcd
acbd
enaa
moze

#### Sample Output 1

DA

#### Explanation for Sample Output 1

E.g. we can choose columns and and change the matrix so that it looks like this (we can choose not to change the first row and swap and letters in other rows):

abcd
abcd
eana
mzoe

It is clear that the first and the second row are the same, thus satisfying the task condition.

#### Sample Input 2

2 2
aa
aa

#### Sample Output 2

DA

#### Sample Input 3

3 2
nec
uuc
iti

#### Sample Output 3

NE