## 11583 - Alien DNA

Moderator: Board moderators

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### 11583 - Alien DNA

What need to do in this problem???

cathy
New poster
Posts: 2
Joined: Sat Mar 28, 2009 11:47 pm

### Re: 11583 - Alien DNA

How is it possible to solve this problem if you get TLE just reading the input??? This program gives me TLE:

#include <iostream>
using namespace std;
#include <string>

int main()
{
long long i, n, x, nc, cuts=0;
string s;
cin >> nc;
for (x = 0; x < nc; x++) {
cin >> n;
for (i = 0; i < n; i++) {
cin >> s;
}
cout << cuts << endl;
}
return 0;
}

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11583 - Alien DNA

Don't use cin here, it is too slow....

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11583 - Alien DNA

I am unable to understand this problem. Can someone please explain it to me??

setu
New poster
Posts: 4
Joined: Fri Mar 06, 2009 11:33 pm

### Re: 11583 - Alien DNA

Chirag Chheda wrote:I am unable to understand this problem. Can someone please explain it to me??
Its not so hard as u thinking. Just take strings one after another and find out the common bases. Take only common bases and compare it with next string untill the common bases string is not NULL. If NULL then cut and start next string otherwise continue finding common bases among the upcoming strings.
INPUT:
asd
sdf
cd
gh

OUTPUT:
1
Becoz the only common base among the first three string is d and as we have to take least minimum cuts so we should be greedy in choosing d avoiding s in above two strings.
Am i clear to understand u?

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11583 - Alien DNA

Thanx a lot 4 u reply. It was very helpful for me. I finally managed to solve it.