912 - Live From Mars

All about problems in Volume 9. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
breech
New poster
Posts: 2
Joined: Wed Aug 22, 2007 12:37 am

912 - Live from Mars

Post by breech » Wed Aug 22, 2007 12:41 am

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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Aug 22, 2007 3:52 pm

My accepted code returns..

Output:

Code: Select all

YES

YES
1 A
2 A
3 A

NO
Ami ekhono shopno dekhi...
HomePage

breech
New poster
Posts: 2
Joined: Wed Aug 22, 2007 12:37 am

Post by breech » Wed Aug 22, 2007 11:20 pm

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
New poster
Posts: 1
Joined: Thu Mar 19, 2009 6:49 pm

Re: 912 - Live from Mars

Post by dongle_xxzp » Thu Mar 19, 2009 6:58 pm

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
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 912 - Live from Mars

Post by Leonid » Tue Aug 24, 2010 11:44 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 912 - Live from Mars

Post by brianfry713 » Tue Dec 03, 2013 2:42 am

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
Last edited by brianfry713 on Wed May 14, 2014 8:06 pm, edited 1 time in total.
Reason: Fixed I/O
Check input and AC output for thousands of problems on uDebug!

Drathus
New poster
Posts: 3
Joined: Wed Apr 09, 2014 5:13 am

912 - Live From Mars

Post by Drathus » Wed May 14, 2014 4:37 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 912 - Live From Mars

Post by brianfry713 » Wed May 14, 2014 8:20 pm

Input:

Code: Select all

3
5
6
6
B
A
A
AC output:

Code: Select all

YES
5 B
6 A
Check input and AC output for thousands of problems on uDebug!

Drathus
New poster
Posts: 3
Joined: Wed Apr 09, 2014 5:13 am

Re: 912 - Live From Mars

Post by Drathus » Thu May 15, 2014 12:45 am

Removed after AC
Last edited by Drathus on Thu May 15, 2014 4:15 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 912 - Live From Mars

Post by brianfry713 » Thu May 15, 2014 1:06 am

Always print a newline char at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 912 - Live From Mars

Post by brianfry713 » Thu May 15, 2014 1:46 am

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.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 9 (900-999)”