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
Post
by mmonish » Tue Oct 07, 2008 12:43 pm
I checked a lot of small cases but couldn't find any wrong.Anyone please give me some tricky case..
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:
Post
by azk84 » Tue Oct 07, 2008 6:50 pm
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
Experienced poster
Posts: 109 Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
Post
by mmonish » Tue Oct 07, 2008 7:56 pm
>>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:
Post
by Abednego » Wed Oct 29, 2008 5:44 pm
What is the answer for the following input?
My code prints
but the problem statement could be interpreted to mean
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:
Post
by azk84 » Wed Oct 29, 2008 6:26 pm
My solution gives
kangroo
New poster
Posts: 13 Joined: Fri Sep 12, 2008 9:12 am
Post
by kangroo » Thu Dec 11, 2008 7:52 pm
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
Post
by Sedefcho » Fri Jan 16, 2009 11:58 pm
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
Post
by krnara » Tue Feb 10, 2009 5:56 am
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
Post
by el cheeto » Thu Apr 16, 2009 11:11 pm
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:
Post
by Jan » Tue May 05, 2009 1:54 am
I used a trie and got accepted.
roticv
Learning poster
Posts: 63 Joined: Sat Dec 11, 2004 9:28 am
Post
by roticv » Thu May 07, 2009 5:49 am
or use suffix array
MRH
Learning poster
Posts: 51 Joined: Mon Aug 11, 2008 9:09 pm
Post
by MRH » Sat Aug 08, 2009 11:30 am
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
Post
by SePulTribe » Sun Sep 06, 2009 2:01 pm
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 277 times
MRH
Learning poster
Posts: 51 Joined: Mon Aug 11, 2008 9:09 pm
Post
by MRH » Mon Sep 07, 2009 7:15 pm
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
Post
by sohel » Tue Sep 08, 2009 8:18 am
Use code tags, when posting your source code!