All about problems in Volume 113. If there is a thread about your problem, please use it. If not, create one with its number in the subject.
Moderator: Board moderators
Ron
Learning poster
Posts: 55 Joined: Mon Jul 23, 2007 5:01 pm
Location: INDIA
Post
by Ron » Sun Dec 30, 2007 8:25 pm
why im getting TLE....
My Code :
Code: Select all
#include<iostream>
#include<string>
using namespace std;
int main(){
int t,n,i;
string v[10000];
int size[10000];
cin>>t;
while(t--){
cin>>n;
string s;
bool flag=1;
cin>>v[0];
size[0]=v[0].length();
n--;
i=1;
int j;
while(n--){
cin>>v[i];
if(flag){
size[i]=v[i].length();
for(j=0;j<i;j++){
if(flag){
if(size[i]>size[j]){
if(v[i].substr(0,size[j])==v[j]){
flag=0;
break;
}
}
else{
if(v[j].substr(0,size[i])==v[i]){
flag=0;
break;
}
}
}
}
}
i++;
}
if(flag) cout<<"YES\n";
else cout<<"NO\n";
}
return 0;
}
please check my code...........................
what should i do ????
EDIT : Thnx sohel !! Now i got accepted ....
Title edited by moderator
Last edited by
Ron on Sun Dec 30, 2007 11:00 pm, edited 1 time in total.
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Post
by sohel » Sun Dec 30, 2007 10:08 pm
An O(n^2) algorithm for this problem will get TLE.
Think of how you can reduce the runtime to O(n log n)?
Chirag Chheda
Learning poster
Posts: 74 Joined: Sat Jun 21, 2008 12:24 pm
Location: India
Post
by Chirag Chheda » Wed Jul 02, 2008 8:24 am
Even i m getting TLE.
can neone who has got ACC jus tell me whether i should sort the numbers on the basis of their length and then start searching..
Thnx in advance.
Waiting for a reply..
kbr_iut
Experienced poster
Posts: 103 Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:
Post
by kbr_iut » Mon Aug 18, 2008 4:18 am
yes,u r right. u have to sort those numbers and then just check one number and between next number.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
kbr_iut
Experienced poster
Posts: 103 Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:
Post
by kbr_iut » Tue Aug 19, 2008 3:51 pm
dont post ambiguous topic.
here all posts r about volume 113.
if u want to post something interesting or like that there is appropriate position for it,,,general chit-chat
http://online-judge.uva.es/board/viewforum.php?f=24
dont do this again.
It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................
bleedingeyes
New poster
Posts: 9 Joined: Thu Aug 21, 2008 3:08 am
Location: IUT
Post
by bleedingeyes » Thu Oct 09, 2008 12:46 am
why i am getting TLE
please help
Code: Select all
#include<stdio.h>
#include<algorithm>
using namespace std;
struct tag
{
char data[15];
int len;
}num[10050];
bool cmp(const tag &p,const tag &q)
{
return p.len<q.len;
}
int main()
{
int a,b,i,j,k,flag;
// freopen("in.txt","r",stdin);
while(scanf("%d",&a)==1)
{
for(k=0;k<a;k++)
{
scanf("%d",&b);
flag=0;
for(i=0;i<b;i++)
{
scanf("%s",&num[i].data);
num[i].len=strlen(num[i].data);
}
sort(num,num+b,cmp);
for(i=0;i<b-1;i++)
{
if(flag) break;
for(j=i+1;j<b;j++)
{
if(num[i].len>num[j].len) break;
else if(i==j) continue;
else
{
const char* p = search(num[j].data, num[j].data + num[i].len, num[i].data, num[i].data + num[i].len);
if((p-num[j].data)==0)
{
flag=1;
break;
}
}
}
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
}
return 0;
}
wanna be notorious....
Obaida
A great helper
Posts: 380 Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.
Post
by Obaida » Thu Nov 13, 2008 6:59 am
1'st sort the values in an efficient way. Then do it.
try_try_try_try_&&&
_try@try.com
This may be the address of success.
setu
New poster
Posts: 4 Joined: Fri Mar 06, 2009 11:33 pm
Post
by setu » Wed Apr 22, 2009 1:13 pm
bleedingeyes wrote: why i am getting TLE
please help
First find out the sorted form of strings in O(nlgn) time . U can sort it by qsort too.
Then scan previous and next string to find if the previous string is a substring of next string.
Hope it will help...
##############################################
I have expressed my thought from my little knowledge.
Jehad Uddin
Learning poster
Posts: 74 Joined: Fri May 08, 2009 5:16 pm
Post
by Jehad Uddin » Sun Aug 30, 2009 5:49 pm
thank u setu vai for ur post,it really helps to get accepted
Mahabub Khan
New poster
Posts: 5 Joined: Sun Apr 08, 2012 5:36 pm
Post
by Mahabub Khan » Tue Oct 30, 2012 7:15 pm
why we sort
the array?
if we sort this
3
911
97625999
91125426
then it becomes
119
25679999
11224569
answer should be "Yes"
please anyone describe this.
Thanks in advance
sohel
Guru
Posts: 856 Joined: Thu Jan 30, 2003 5:50 am
Location: New York
Post
by sohel » Tue Oct 30, 2012 8:26 pm
Who said we are sorting each number?
triplemzim
New poster
Posts: 48 Joined: Sat Apr 06, 2013 6:02 pm
Post
by triplemzim » Sun Aug 18, 2013 10:34 pm
Why getting TLE please help???
here is my code...
Code: Select all
#include<iostream>
#include<cstdio>
#include<math.h>
#include<string.h>
using namespace std;
int min(int a,int b)
{
if(a<b) return a;
else return b;
}
int main()
{
char ch[10009][11];
int cases,n;
scanf("%d",&cases);
while(cases--)
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%s",ch[i]);
}
int flag=1;
for(int i=0;i<n-1;i++)
{
int ilen=strlen(ch[i]);
for(int j=i+1;j<n;j++){
int len=min(ilen,strlen(ch[j]));
flag=1;
for(int k=0;k<len;k++)
{
if(ch[i][k]!=ch[j][k])
{
flag=0;
break;
}
}
if(flag) break;
}
if(flag) break;
}
if(flag) printf("NO\n");
else printf("YES\n");
}
return 0;
}
triplemzim
New poster
Posts: 48 Joined: Sat Apr 06, 2013 6:02 pm
Post
by triplemzim » Sun Aug 18, 2013 10:37 pm
setu wrote: bleedingeyes wrote: why i am getting TLE
please help
First find out the sorted form of strings in O(nlgn) time . U can sort it by qsort too.
Then scan previous and next string to find if the previous string is a substring of next string.
Hope it will help...
##############################################
I have expressed my thought from my little knowledge.
I didn't understand your logic... if we sort this input ( 911,9101,911234) then how can we find if it is consistent by checking just with the previous one???
brianfry713
Guru
Posts: 5947 Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA
Post
by brianfry713 » Mon Aug 19, 2013 10:23 pm
Sort as strings not as integers.
Check input and AC output for thousands of problems on
uDebug !
triplemzim
New poster
Posts: 48 Joined: Sat Apr 06, 2013 6:02 pm
Post
by triplemzim » Tue Aug 27, 2013 2:01 am
yup got it!!!! it's called lexicographical sorting