497 - Strategic Defense Initiative

All about problems in Volume 4. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Post by roticv » Tue Aug 30, 2005 9:13 am

The code looks okay to me, but is your SIZE big enough? I used 15000.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

497-TLE pls help!

Post by sunny » Sun Sep 18, 2005 10:29 pm

pls help me why TLE :

/*
REMOVED
*/
Last edited by sunny on Thu Oct 26, 2006 11:03 pm, edited 1 time in total.

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

Post by Jan » Wed Nov 09, 2005 11:24 pm

Code: Select all

scanf("%ld%c%*c",&c,&h);
Why you are using variable 'h'? There is no need to use it. Use..

Code: Select all

scanf("%ld",&c);
Hope it helps. :)
Ami ekhono shopno dekhi...
HomePage

shalinmangar
New poster
Posts: 6
Joined: Sun Nov 27, 2005 8:24 am
Location: India

Post by shalinmangar » Sun Jan 29, 2006 10:30 am

Your code is wrong. Consider the following testcase:

100
45
46
47
48
49
11
1

Your code gives the answer as:
Max hits: 1
1

But actually we can have:
Max hits: 5
45
46
47
48
49

taskin
New poster
Posts: 22
Joined: Sun Jan 01, 2006 1:43 pm
Location: Bangladesh

497 WA

Post by taskin » Fri May 26, 2006 2:29 pm

can anyone tell me why its wa.

deleted after ac

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

497 WHY WA!!! IF YOU KNOW TELL ME THANKS.

Post by Staryin » Thu Jun 01, 2006 10:48 am

removed :lol:
Last edited by Staryin on Fri Jun 02, 2006 4:46 am, edited 1 time in total.

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu Jun 01, 2006 12:37 pm

Two things that might cause you problems:

char c,snum[5];
5 might be too low. Try changing it to 10 (you want to be able to read numbers that would fit into a 32-bit int).

Also, you print an extra blank line after the last case, which might cause a presentation error.

Staryin
New poster
Posts: 12
Joined: Fri Dec 16, 2005 4:22 pm
Location: shanghai/china
Contact:

Post by Staryin » Thu Jun 01, 2006 12:53 pm

THANKS! AC!

User avatar
dumb dan
Learning poster
Posts: 67
Joined: Tue Aug 05, 2003 1:02 am

Post by dumb dan » Thu Jun 01, 2006 6:22 pm

No problem.

You should probably remove your code now (it's custom to remove ones code after getting AC).

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Wed Jul 19, 2006 6:38 pm

Larray wrote: Well, I couldn't get it to accept until I fixed the zero case... maybe it was just me..
Hehehe! its not only you larry! I also had the same problem, and it costed me three consecutive WAs before getting that zero case idea!

Thanks a lot to everyone!
fahim
#include <smile.h>

User avatar
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

in nlog(n) time

Post by Tanu » Thu Jul 20, 2006 9:08 am

I'm trying to solve it in nlog(n) time ...
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;
}
There is another question what is the real array size should be declared...
Thanx in advance..
..Tanu

IRA
Learning poster
Posts: 82
Joined: Sat Jan 07, 2006 6:52 am

Post by IRA » Thu Jul 20, 2006 10:52 am

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....

User avatar
Tanu
Learning poster
Posts: 70
Joined: Sun May 29, 2005 12:46 pm
Location: Mars

I know the n^2 algorithm

Post by Tanu » Thu Jul 20, 2006 3:40 pm

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

User avatar
smilitude
Experienced poster
Posts: 137
Joined: Fri Jul 01, 2005 12:21 am

Post by smilitude » Mon Jul 24, 2006 7:42 am

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]
fahim
#include <smile.h>

User avatar
algoJo
New poster
Posts: 37
Joined: Sun Dec 17, 2006 9:02 am

critical I/O set

Post by algoJo » Sun Apr 29, 2007 6:47 am

Hi, can someone check this I/O set:

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
OUTPUT

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

can someone post more I/O set..
Thanks :D [/quote]

Post Reply

Return to “Volume 4 (400-499)”