912 - Live From Mars

[breech]

Can someone tell me what their ACC code gives for the following input?

Code: Select all

3
1
2
3
4
5
6

3
A
1
2
1
2
3

3
A
2
2
1
D
1

Thanks

[Jan]

My accepted code returns..

Output:

Code: Select all

YES

YES
1 A
2 A
3 A

NO

[breech]

Thanks. My code gives the same answers, but I'm still getting WA.

Anyone got any tricky inputs for this problem they want to share?

[dongle_xxzp]

Hello to all,

I have been stuck for over 1 week in this problem and is starting to get frustrating).

I have some questions on the problem.
Does the mutant dna elements be a positive integer ranging from 1 to 200 and always starting from 1?


Could someone please explain why the output for this test case:

Code: Select all

6
4
5
A
4
5
B
6
7
4
5
6
7

is (generated from uvatoolkit.com)

Code: Select all

YES
4 A
5 B
6 B
7 B

Shouldn't it be

Code: Select all

NO

since A->4 means 5 also becomes A
and B->7 means 5 also becomes B
thus there is a collision and hence it both sequences cannot mutate into a common sequence?

[Leonid]

My AC solution prints "NO" for the case above. uvatoolkit solution may be doing some assumptions about the input which aren't satisfied in the test case, or it could be just a bug anywhere in the solution.

[brianfry713]

Input:

Code: Select all

7
3
D
4
C
B
6
9
C
4
4
A
D
D
C

5
7
5
B
4
D
2
A
5
B
3

6
C
A
C
C
6
D
3
5
5
B
B
8

4
B
7
3
1
D
1
1
8

9
B
C
B
A
9
B
A
5
D
D
4
2
6
D
A
A
B
5

7
A
B
C
B
1
2
2
A
3
A
7
C
8
B

7
D
3
1
3
3
5
2
6
D
C
6
7
C
4

10
A
9
9
B
A
6
5
2
5
9
C
B
5
A
7
C
4
C
5
2

7
7
C
8
1
C
B
D
B
7
6
3
B
B
D

6
6
A
B
6
3
8
D
C
D
9
D
B

3
6
C
B
8
7
2

1
A
7

1
1
C

2
5
2
4
6

6
1
C
1
B
4
B
D
A
B
2
2
D

1
4
B

8
3
2
B
5
2
B
A
2
9
9
C
5
C
C
A
A

10
1
B
1
C
A
7
9
D
B
1
2
C
2
6
A
D
7
1
7
3

2
9
D
C
B

6
B
2
C
2
7
B
D
1
C
C
2
3

1
6
D

8
3
8
7
5
C
A
A
7
7
3
C
A
7
4
2
A

10
A
D
7
9
A
9
4
9
C
D
B
5
A
A
8
B
8
6
A
B

8
B
B
B
6
C
A
7
1
8
9
9
2
9
9
B
2

9
B
3
5
2
C
3
6
2
C
B
4
A
5
C
5
6
C
B

9
D
5
A
1
2
3
9
7
A
8
A
4
A
7
B
1
1
B

9
A
2
A
6
9
B
D
9
D
8
C
4
2
9
B
5
5
B

9
4
6
D
A
5
D
C
D
9
C
5
B
C
D
1
C
5
4

2
1
D
1
7

5
3
D
4
D
C
2
1
D
5
C

3
C
C
B
C
D
7

10
B
3
1
C
3
3
4
9
C
B
D
A
B
A
A
A
A
B
A
5

10
5
B
7
7
6
A
4
B
3
4
B
D
1
7
C
B
6
5
8
A

7
A
4
C
D
5
7
B
C
D
D
2
7
D
B

9
B
A
1
A
A
6
9
D
B
B
6
B
9
3
B
5
D
B

2
4
9
B
B

7
D
8
8
8
B
3
5
A
1
5
B
9
3
B

3
B
C
D
4
6
D

8
B
C
2
1
D
B
D
5
5
C
5
B
D
D
C
9

1
A
5

3
2
D
C
D
2
C

2
B
D
C
7

4
A
B
2
D
D
A
1
7

8
B
6
2
4
B
2
D
1
D
4
1
5
4
2
B
A

9
B
D
C
8
5
9
1
C
5
6
C
C
6
D
1
3
3
D

2
2
5
C
3

8
2
9
C
B
2
5
3
8
C
A
B
7
A
D
A
8

3
7
9
B
2
D
C

6
D
B
6
4
D
C
2
9
D
5
B
A

8
5
B
3
3
5
D
C
2
A
4
1
9
C
3
8
A

3
9
4
B
D
A
2

3
A
4
A
5
8
6

6
3
6
D
D
5
1
B
A
3
A
A
D

3
B
D
5
D
D
5

1
A
8

6
5
5
D
C
3
B
6
D
D
4
3
C

8
B
A
6
5
1
B
B
C
9
7
A
7
6
2
4
7

6
A
9
2
A
5
B
D
6
9
A
B
6

9
D
2
A
3
4
B
6
1
3
D
C
C
D
6
C
C
B
A

4
D
C
9
5
C
A
B
2

3
1
4
3
B
9
D

8
1
8
D
C
3
7
3
A
2
D
B
2
5
B
6
7

8
3
B
3
9
A
8
B
C
9
2
B
9
2
C
C
9

8
D
A
D
B
B
3
4
2
7
9
2
D
1
2
5
D

5
6
D
4
6
7
3
D
D
7
B

5
8
9
A
5
A
4
6
A
A
C

1
6
3

8
7
D
B
4
8
5
D
2
6
7
D
A
6
4
4
C

5
1
A
A
7
4
A
8
5
3
8

7
6
3
A
B
7
D
5
8
A
B
D
9
B
C

6
D
C
D
1
6
9
5
3
7
D
D
8

4
3
9
7
5
2
B
B
A

8
C
A
8
C
C
D
C
B
7
B
B
A
2
D
B
4

9
4
7
8
D
C
5
4
B
8
1
D
B
5
C
A
2
C
B

8
1
4
3
4
D
6
3
B
B
B
1
6
D
A
4
A

6
D
D
B
B
B
C
7
B
D
B
B
2

5
4
D
5
B
A
2
D
A
1
C

10
3
8
A
D
A
6
B
7
7
5
2
2
6
9
3
5
4
1
5
B

5
A
A
6
C
9
6
2
2
C
A

7
5
A
6
6
A
9
C
D
B
7
B
3
D
9

6
2
B
B
D
1
5
5
7
1
9
D
D

6
2
D
3
B
A
1
B
4
B
A
A
A

7
C
A
D
B
5
3
D
C
D
D
5
4
5
9

7
5
C
4
D
4
A
B
8
2
D
C
A
A
A

9
A
C
D
7
B
A
4
D
B
D
9
D
3
1
4
A
6
5

10
2
1
9
A
C
A
D
D
3
B
4
8
A
2
2
5
8
D
C
B

7
4
B
1
C
5
5
C
D
2
B
8
5
9
A

9
5
2
A
2
C
A
B
D
2
6
D
C
A
1
A
4
4
B

4
D
6
6
4
2
2
5
5

5
D
5
C
8
A
C
9
B
3
D

8
C
A
B
D
B
1
C
B
8
C
5
4
B
A
C
C

9
C
A
D
C
B
8
D
A
3
A
5
C
8
B
8
D
4
9

3
C
B
5
8
1
4

4
3
D
B
7
3
A
9
A

4
D
C
7
C
1
C
9
6

4
A
D
2
3
A
A
1
D

10
3
4
7
D
C
8
D
C
8
4
A
D
6
C
C
5
1
B
C
2

5
7
3
6
6
7
7
6
A
9
B

8
D
9
7
7
2
B
B
1
5
C
2
9
C
5
3
5

3
4
A
C
9
A
B

AC output:

Code: Select all

NO

NO

NO

NO

NO

NO

YES
1 C
3 D
5 C
6 D
7 D

NO

NO

NO

YES
2 B
7 C

YES
7 A

YES
1 C

YES

NO

YES
4 B

NO

NO

NO

NO

YES
6 D

NO

NO

NO

NO

NO

NO

NO

YES
7 D

YES
1 D
4 D
5 D

NO

NO

NO

NO

NO

YES
4 B
9 B

NO

YES
4 B
6 C

NO

YES
5 A

YES
2 D

NO

NO

NO

NO

YES
2 C

NO

NO

NO

NO

YES
2 B
4 A
9 D

YES
5 A
6 A

NO

NO

YES
8 A

NO

NO

NO

NO

NO

YES
1 B
3 D

NO

NO

NO

YES
3 B
4 D
6 B
7 B

NO

YES

NO

YES
1 A
4 A
5 A
8 A

NO

YES
1 D
3 C
5 D
6 D
7 D

YES
5 A
7 B
9 B

NO

NO

NO

NO

NO

NO

YES
2 A
6 A
9 A

NO

NO

NO

NO

NO

NO

NO

NO

NO

YES
2 D
4 D
5 D
6 D

NO

NO

NO

YES
1 B
8 C

NO

YES
1 D
6 C

NO

NO

YES
3 A
6 A
7 B
9 A

NO

NO

[Drathus]

Hey guys, I'm having a lot of trouble with this problem. I have tested my code against brianfry's big data set, and have gotten them all correct. But I still am getting WA. I think it has to do with newlines. Any ideas? Please help.

Code: Select all

#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <memory.h>
#include <utility>
#include <stack>
#include <queue>
#include <vector>
#include <ctime>
#include <algorithm>
#include <map>
#define REP(i, a, b) \
for(int i = int(a); i <= int(b); i++)
using namespace std;
typedef long long ll;

//Modified Halim's
vector<int> pset(1000);
void initSet(int _size) {pset.resize(_size); REP(i, 0, _size - 1) pset[i] = i; }
int findSet(int i) { return pset[i] == i ? i : (pset[i] = findSet(pset[i])); } //Gets representative for node i, and performs path compression
void unionSet(int i, int j) { pset[findSet(i)] = findSet(j); }
bool isSameSet(int i, int j) { return findSet(i) == findSet(j); }
int numberOfSets() { int n = 0; REP(i, 0, pset.size() - 1) n += (findSet(i) == i); return n; }
int sizeOfSet(int i) { int s = 0; REP(j, 0, pset.size() - 1) s += (findSet(i) == findSet(j)); return s; }

map<int, char> mut;
map<char, int> invMut;

int main(){
     //FILE * fout = fopen("data.out", "w");
     int n, cnum = 0, mN = 10;
     char c, s[50];
     while(gets(s) && strcmp(s, "") != 0){
          if(cnum++) printf("\n\n");
          sscanf(s, "%d", &n);
          string s1 = "", s2 = "";
          for(int i = 0; i < 2 * n; i++){
               scanf("%c", &c);
               if(i < n) s1 += c;
               else s2 += c;
               gets(s);
          }
          for(int i = 0; i < mN; i++){
               mut[i] = '-';
               invMut['A' + i] = -1;
          }
          initSet(mN);
          bool flag = false, c1, c2;
          for(int i = 0; i < n; i++){
               //cout << endl << i << " " << s1[i] << " " << s2[i] << endl;
               if(s1[i] == s2[i]) continue;
               c1 = s1[i] >= 'A' && s1[i] <= 'Z';
               c2 = s2[i] >= 'A' && s2[i] <= 'Z';
               int v1 = -1, v2 = -1;
               if(!c1) v1 = s1[i] - '1';
               if(!c2) v2 = s2[i] - '1';
               //cout << c1 << " " << c2 << endl << v1 << " " << v2 << endl;;
               if(c1 && c2){
                    if(s1[i] != s2[i]){
                         flag = 1;
                         break;
                    }
               }
               if(!c1 && !c2){
                    if(findSet(v1) == findSet(v2)) continue;
                    else if(mut[findSet(v1)] == '-'){
                         unionSet(v1, v2);
                    }
                    else if(mut[findSet(v2)] == '-'){
                         unionSet(v2, v1);
                    }
                    else if(mut[findSet(v1)] != mut[findSet(v2)]){
                         flag = 1;
                         break;
                    }
               }
               else if(c1){
                    if(mut[findSet(v2)] != '-' && mut[findSet(v2)] != s1[i]){
                         flag = 1;
                         break;
                    }
                    else{
                         int mergeTo = invMut[s1[i]];
                         if(mergeTo != -1){
                              unionSet(v2, mergeTo);
                              invMut[s1[i]] = findSet(v2);
                         }
                         else{
                              mut[findSet(v2)] = s1[i];
                              invMut[s1[i]] = findSet(v2);
                         }
                    }
               }
               else {
                    if(mut[findSet(v1)] != '-' && mut[findSet(v1)] != s1[i]){
                         flag = 1;
                         break;
                    }
                    else{
                         int mergeTo = invMut[s2[i]];
                         if(mergeTo != -1){
                              unionSet(v1, mergeTo);
                              invMut[s2[i]] = findSet(v1);
                         }
                         else{
                              mut[findSet(v1)] = s2[i];
                              invMut[s2[i]] = findSet(v1);
                         }
                    }
               }
               /*for(int j = 0; j < 8; j++){
                    //if(mut[findSet(j)] != '-')
                         printf("%d %d %c\n", (j + 1), findSet(j) + 1, mut[findSet(j)]);
               }*/

          }
          if(flag){
               printf("NO");
          }
          else{
               printf("YES");
               for(int j = 0; j < mN; j++){
                    if(mut[findSet(j)] != '-'){
                         printf("\n");
                         printf("%d %c", (j + 1), mut[findSet(j)]);
                    }
               }
          }
          if(!gets(s)) return 0;
     }
}

[brianfry713]

Input:

Code: Select all

3
5
6
6
B
A
A

AC output:

Code: Select all

YES
5 B
6 A

[Drathus]

Removed after AC

[brianfry713]

Always print a newline char at the end of the last line.

[brianfry713]

It looks like the judge's input doesn't follow the problem statement and you can't read line by line in this problem. Try reading the input as tokens or strings.