11512 - GATTACA

[mmonish]

I checked a lot of small cases but couldn't find any wrong.Anyone please give me some tricky case..

Code: Select all

AC.....

[azk84]

I tested your program with 100 random generated strings and your program gave wrong answer for this test cases:

Code: Select all

9
AAGAAAGCACAC
ACAACGCTAGAGCGAAAGCATGGCGCCCGC
TGCTCCTATGAATCT
ATGCACCGCCAGAGC
CCGAAC
TGAATCCGGCTTAAGTCTTGGGGCCA
ATTATCGGGGCCGGATTTCCCCTAA
ATAGTCGGAACACCAGGCAGAGCATTACGT
GGTCTATACGATGATAATATC

Correct answers should be:

Code: Select all

AAG 2
AGC 2
AT 2
AG 2
A 2
CTT 2
ATT 2
CAG 2
ATA 3

But your program gives:

Code: Select all

CAC 2
CGC 3
CT 3
GC 3
A 3
GGC 2
CCC 2
GCA 2
TAT 2

[mmonish]

>>azk84
thx for ur reply.silly mistake in my lexiographic compare function.My AC time is 2.110 sec but some people solve this
prob in less than 0.1sec. I want to know the better approach for this prob.anyone help me please....

[Abednego]

What is the answer for the following input?

Code: Select all

1
AAA

My code prints

Code: Select all

AA 2

but the problem statement could be interpreted to mean

Code: Select all

A 3

Thanks.

[I'm getting WA after passing all of azk84's test cases.]

[azk84]

My solution gives

Code: Select all

AA 2

[kangroo]

hello,

I m getting TLE for GATTACA problem...
below is my code...anyone pls help me !!

Code: Select all

int main ()
{
 int t = GI;
 while ( t -- )
 {
  char c[1002] = {'\0'};
  scanf ( "%s" , c );
  string s = c;
  mSI mp;

  FORZ (i , s.sz)
  {
   FORZ (j , s.sz - i)
   {
    string x = s.substr(i , j + 1);
    mp [x] ++;
   }
  }


  string ans = "";
  int occ = 0;

  for ( mSI :: iterator it = mp.begin() ; it != mp.end() ; it ++ )
  {
   string x = it -> first;
   int len = it -> second;
   if ( len <= 1 ) continue;
   if ( x.sz > ans.sz )
   {
    ans = x;
    occ = len;
   }
  
  }

  if ( ans.empty() ) printf ( "No repetitions found!\n");
  else printf ( "%s %d\n" , ans.c_str() , occ );

 }
 return 0;
}

thanks in advance..!!
waiting for help !!

[Sedefcho]

I solved this one using two separate programs which implement different algorithms.

Program #1 uses Trie-like structure - some simpler version of Suffix Tree
but I believe I have some performance flaw in this one
(language C with some simple C++ features, no STL usage)
Runs (Accepted) in about : 4.970 secs

Program #2 uses Heap and also Suffix Array
(language C++, uses STL)
Runs (Accepted) in about 0.670 secs

I was really amazed of the speed difference of the two programs.
Apparently my first program can be optimized much further.

[krnara]

my code passed all testcase.....

but TLE.........

somebody helpme plz........

Code: Select all

#include <iostream>
#include <string>
#include <map>
#include <algorithm>

using namespace std;


int main()
{

	int cnt;

	string input;
	
	cin>>cnt;
	

	while(cnt)
	{
		map<string,int> pattern;
		int MAX_LEN = -1;
		int MAX_CNT = -1;
		int a = 0;
		
		int i,j;
		i = 0;

	
		cin>>input;

		
		for(i = 0 ; i< input.size(); i++)
		{	
			string temp = "";
			temp += input[i]; 
			
			a++;
		
			
			for(j = i + 1; j<= input.size() ; j++)
			{
				int input_size = input.size();
				if(input_size - i < MAX_LEN)
				{
				
					break;
				}
					a++;
				
			
			
				pattern[temp]++;

				
				int temp_size = temp.size();
				int frequency = pattern[temp];
				
				
				if(temp_size > MAX_LEN && frequency >= 2 )
				{
					
					
			
					MAX_LEN = temp_size;
					MAX_CNT = frequency;
				}
				temp += input[j];
				

				
				
			}
		}
		

		
		cout<<a<<endl;
		map<string,int>::iterator it = pattern.begin();
		
		int MAX_LENGTH = -1;
		bool flag = false;
		

		for(it ; it != pattern.end() ; it++)
		{
		
			
			if(it->second <= 1)
			{
			
			
				continue;
			}
				

			
			
			else
			{
			
				int temps = it->first.size();
				
				if(temps > MAX_LENGTH)
				{
					MAX_LENGTH = temps;
					flag = true;
				}

			}
			
		}

		
		if(flag)
		{

			for(it = pattern.begin() ; it != pattern.end() ;it++)
			{
				if(it->first.size() == MAX_LENGTH && it ->second > 1)
				{
					cout<< it->first<<" "<<it ->second<<endl;
					break;
				}
			}
		}

		
		else
		{
			cout<<"No repetitions found!"<<endl;
		}

	
		cnt--;
	}


	return 0;
}

[el cheeto]

Can anyone give me some hint to solve this problem? I tried to use map, but got TLE. Thanks in advance.

[Jan]

I used a trie and got accepted.

[roticv]

or use suffix array

[MRH]

hello "Sedefcho" && " Jan" i use trie and get TLE can anyone explain me why trie get TLE??
my Program #
void init(trie *x)
{
int i ;

for(i = 0 ; i < 4 ; i++)
{
x->next[i] = NULL ;
x->pre[i] =0;
}
}
here add string and take longest prefix
void add(trie *vertex , string word)
{
word.erase(0 , 1) ;
add(vertex->next[k] , word) ;
}

int main()
{
while( s!="" )
{
ss="";
add(head , s) ;
s.erase(0,1);
}
}

[SePulTribe]

Here are some killer test cases. The .in file is the input file and the .out file is for you to compare against. Good luck!

[MRH]

remove................

[sohel]

Use code tags, when posting your source code!