11512 - GATTACA

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

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

11512 - GATTACA

Post by 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.....
Last edited by mmonish on Tue Oct 07, 2008 7:56 pm, edited 1 time in total.

azk84
New poster
Posts: 14
Joined: Sat Sep 13, 2008 7:50 pm
Location: Tehran
Contact:

Re: 11512 - GATTACA

Post by 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

:wink:

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Re: 11512 - GATTACA

Post by 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
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Re: 11512 - GATTACA

Post by 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.]
If only I had as much free time as I did in college...

azk84
New poster
Posts: 14
Joined: Sat Sep 13, 2008 7:50 pm
Location: Tehran
Contact:

Re: 11512 - GATTACA

Post by azk84 »

My solution gives

Code: Select all

AA 2
:wink:

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

GATTACA --- Getting TLE !!

Post by 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
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Re: 11512 - GATTACA

Post by 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
New poster
Posts: 2
Joined: Thu Jan 15, 2009 2:46 pm

helpme

Post by 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
New poster
Posts: 9
Joined: Mon Feb 13, 2006 12:40 am
Location: Mexico

Re: 11512 - GATTACA

Post by el cheeto »

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11512 - GATTACA

Post by Jan »

I used a trie and got accepted.
Ami ekhono shopno dekhi...
HomePage

roticv
Learning poster
Posts: 63
Joined: Sat Dec 11, 2004 9:28 am

Re: 11512 - GATTACA

Post by roticv »

or use suffix array

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11512 - GATTACA

Post by 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
New poster
Posts: 28
Joined: Mon Nov 15, 2004 5:00 pm

Re: 11512 - GATTACA

Post by 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!
Attachments
11512.zip
(3.86 KiB) Downloaded 272 times

MRH
Learning poster
Posts: 51
Joined: Mon Aug 11, 2008 9:09 pm

Re: 11512 - GATTACA

Post by MRH »

remove................
Last edited by MRH on Wed Sep 09, 2009 5:28 am, edited 1 time in total.

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Re: 11512 - GATTACA

Post by sohel »

Use code tags, when posting your source code!

Post Reply

Return to “Volume 115 (11500-11599)”