11583 - Alien DNA

All about problems in Volume 115. 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
Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

11583 - Alien DNA

Post by Igor9669 » Sat Mar 28, 2009 4:10 pm

What need to do in this problem???
Please... :D

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

Re: 11583 - Alien DNA

Post by cathy » Sat Mar 28, 2009 11:50 pm

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

Post by Igor9669 » Sun Mar 29, 2009 8:12 am

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

Post by Chirag Chheda » Sat Apr 04, 2009 11:30 am

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

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

Re: 11583 - Alien DNA

Post by setu » Sat Apr 04, 2009 10:26 pm

Chirag Chheda wrote:I am unable to understand this problem. Can someone please explain it to me??
Than in advance
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

Post by Chirag Chheda » Sun Apr 05, 2009 4:53 am

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

Post Reply

Return to “Volume 115 (11500-11599)”