497  Strategic Defense Initiative
Moderator: Board moderators
497TLE pls help!
pls help me why TLE :
/*
REMOVED
*/
/*
REMOVED
*/
Last edited by sunny on Thu Oct 26, 2006 11:03 pm, edited 1 time in total.
Code: Select all
scanf("%ld%c%*c",&c,&h);
Code: Select all
scanf("%ld",&c);
Ami ekhono shopno dekhi...
HomePage
HomePage

 New poster
 Posts: 6
 Joined: Sun Nov 27, 2005 8:24 am
 Location: India
497 WHY WA!!! IF YOU KNOW TELL ME THANKS.
removed
Last edited by Staryin on Fri Jun 02, 2006 4:46 am, edited 1 time in total.
in nlog(n) time
I'm trying to solve it in nlog(n) time ...
here is my code...
Plz help...
There is another question what is the real array size should be declared...
Thanx in advance..
..Tanu
here is my code...
Plz help...
Code: Select all
#include<stdio.h>
#include<string.h>
#define inf 4294967295
#define MAX 1000000
unsigned long res[MAX],in[MAX];
long top;
long binarySearch(unsigned long key )
{
long low = 0;
long high = top 1; //zero based array
long middle;
while( low <= high )
{
middle = ( low + high ) / 2;
if( key == res[ middle ] ) //match
return middle;
else if( key < res[ middle ] )
high = middle  1; //search low end of array
else
low = middle + 1; //search high end of array
}
return middle;
}
main()
{
long test = 0,testcase;
long i,t;
long pos,k;
char ss[100];
//freopen("c:\\in.txt","r",stdin);
scanf("%ld",&testcase);
getchar();
gets(ss);
while(1)
{
if(test == testcase)
break;
while(gets(ss))
{
if(strcmp(ss,"")==0)
break;
res[top] = inf;
sscanf(ss,"%lu",&in[top++]);
}
res[top] = inf;
k = 0;
for(t = 0; t < top ;t++)
{
pos = binarySearch(in[t]);
if(res[pos] > in[t])
res[pos] = in[t];
else
res[pos+1] = in[t];
}
for(t = 0; t < top ;t++)
if(res[t] == inf)
break;
printf("Max hits: %ld\n",t);
for(i = 0; i < t ;i++)
printf("%lu\n",res[i]);
test++;
top = 0;
}
return 0;
}
Thanx in advance..
..Tanu
to Tanu:
I try your program....
I find this case

1
10
9
2
3
8
1

your output:
Max hits:3
1
3
8

This is not correct.
This problem can solve in O(n^2) use LCS method to find LIS.
I search many web.Can't find O(nlogn) method how to find the correct subsequence.But,it can find correct length.
Q481 need use O(nlogn) method.The problem I have not solve....
I try your program....
I find this case

1
10
9
2
3
8
1

your output:
Max hits:3
1
3
8

This is not correct.
This problem can solve in O(n^2) use LCS method to find LIS.
I search many web.Can't find O(nlogn) method how to find the correct subsequence.But,it can find correct length.
Q481 need use O(nlogn) method.The problem I have not solve....
I know the n^2 algorithm
I know the N^2 algorithm...
I'm trying to do it in nlog(n) time...
I learn it from my friend but my code is so useful to make it implemented...
help anyone to solve this problem in better...
Is there any post about it...
Referrence is needed...
Thanx dear IRA...
...Tanu
I'm trying to do it in nlog(n) time...
I learn it from my friend but my code is so useful to make it implemented...
help anyone to solve this problem in better...
Is there any post about it...
Referrence is needed...
Thanx dear IRA...
...Tanu
Your algorithm is quite right tanu, though it could be more simpler if you used lower_bound of stl. But you have to have a recursive function call to print the LIS. The problem with this nlogk algo is, it always tracks the last element, but not the perfect array it saves.. for that input your code is showing
1
3
8
that is supposed to be
2
3
8
your one is just right... just have another array, that will save which one was on before that  i mean each one will have one parent. Then you have to do a recursive call from the end to print the LIS. [/code]
1
3
8
that is supposed to be
2
3
8
your one is just right... just have another array, that will save which one was on before that  i mean each one will have one parent. Then you have to do a recursive call from the end to print the LIS. [/code]
fahim
#include <smile.h>
#include <smile.h>
critical I/O set
Hi, can someone check this I/O set:
INPUT
OUTPUT
can someone post more I/O set..
Thanks [/quote]
INPUT
Code: Select all
11
1
2
3
4
5
5
4
3
2
1
1
1
3
4
2
5
6
100
45
46
47
48
49
11
1
1
6
2
3
5
3
2
10
1
3
4
2
5
6
Code: Select all
Max hits: 5
1
2
3
4
5
Max hits: 1
1
Max hits: 1
1
Max hits: 0
Max hits: 0
Max hits: 5
1
3
4
5
6
Max hits: 5
45
46
47
48
49
Max hits: 4
1
2
3
5
Max hits: 1
2
Max hits: 1
10
Max hits: 5
1
3
4
5
6
Thanks [/quote]