701 - The Archeologists' Dilemma

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

Moderator: Board moderators

User avatar
emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

Post by emotional blind » Sat Mar 05, 2005 1:32 pm

> > = [0, 2, 3, 9, 2, 2, ... ] in continuous
..../\....
....||....
how it comes


WHO WILL HELP ME?

eyhk
New poster
Posts: 1
Joined: Tue Mar 22, 2005 7:21 am

Post by eyhk » Tue Mar 22, 2005 7:25 am

For sedafcho's input, I got a different output, the last two.
I'm not able to find 2^31 though.

Code: Select all

7
8
15
12
20
31
28748
24559
4813
325147
325148
11036
37937
6432163
146964308
146964307

SiburNY
New poster
Posts: 4
Joined: Mon Apr 11, 2005 9:47 pm

Post by SiburNY » Mon Apr 11, 2005 10:04 pm

2 Sedefcho

I got the same results. How long does it take to get them ? On my AMD 2200 it took like 10 minutes or more.

2 All

What is the maximum E ? I used LOG method. It's fairly fast, but this ludge gives just 10 sec for execution. So if there is number that definately does not have answer, it'll take my script a lot of time till it figures that out :(

Any ideas ?

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Mon Apr 11, 2005 10:29 pm

Hi SiburNY,

I have a machine with 512 MB RAM and
with a 1.6 GHz processor. My program is in C++.

For the input/output I have given above my C++ terminates
for about 3 mins.
So my algorithm is not efficient ( for the limits of
this problem as stated in the problem statement ).

But the Online Judge says my program terminates
( for Judge's input ) in 0.2 secs. So the Judge's input is not
so "hard" as mine ( see above ).

Apparently your algorithm could be made even more efficient.

I don't remember any details about the algorithm I've used.
I just ran my program once again.

Let me know if you need some hints. I can check my code
to see what algorithm I use.

But for sure the Judge's Input is not hard which means it contains
no numbers like 100 000 000 let's say.

One more thing - I am pretty sure
there's no limit for E.

SiburNY
New poster
Posts: 4
Joined: Mon Apr 11, 2005 9:47 pm

Post by SiburNY » Mon Apr 11, 2005 10:44 pm

I doubt that input is not hard. When you have chance, can you creat not hard input set and feed it to your script so then I can compare to my output. Thanks a lot.

Just thought: for previous input I have the same output. So my program works right. And because Judge gives TLE to me, that means it has at least one "no power of 2" case.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Apr 12, 2005 12:55 am

How fast is your computer ( memory/processor ) ?
If we could say it is as fast as mine
than your algorithm is about 3 times slower.
But still this does not explain the TLE you get.
You should get into these 10 secs which the
Judge gives us even if your algorithm is 3 times slower.

You can easily create some "not hard" test cases.
Simply use values which are below 100 000 or below
1000 000 let's say ( second could be better ).

Make a lot ( 20-30 ) such cases and then we will compare them with
my output for the same values. Just post your I/O here.

If then the two outputs are the same there's a great chance
then that there exists some special case in which your program
goes into an endless loop ( or least in a loop which takes too much
to complete )
. This could explain the TLE. Of course I am
just guessing ( logically guessing, at least trying to ... ) .

Are you using C/C++ or Java ?
That also shouldn't make any great difference but ...
Still, who knows.

That is my opinion.

SiburNY
New poster
Posts: 4
Joined: Mon Apr 11, 2005 9:47 pm

Post by SiburNY » Tue Apr 12, 2005 1:37 am

Thanks for trying to help me. I use C. I have Athlon XP 2200 768Mb computer. This time I tweaked my code a little. It took 11-12 seconds to finish the following numbers:

Input:

Code: Select all

1
2
3
4
5
111
222
333
444
555
66666
77777
88888
99999
111111
111222
333444
555666
999900
123456
654321
100000
200000
300000
400000
500000
Output:

Code: Select all

7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146
Thank you.

User avatar
Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

Post by Sedefcho » Tue Apr 12, 2005 10:47 am

Hi again SiburNY,

for your input I get the following output

Code: Select all

7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146

Seems the same , right ?

With my program it takes about 1 sec to get this
output on a machine with 2GB RAM and
with a 2.66 GHz processor.

I will test it on the other machine too ( the one having
512 MB RAM and a 1.6 GHz processor ). And I will tell you
how much time my program needs to
complete on that machine for the input from your last post.

Why don't you e-mail me your code ? Or just send it to
me via a private message.
Last edited by Sedefcho on Sat Jun 11, 2005 9:00 pm, edited 1 time in total.

SiburNY
New poster
Posts: 4
Joined: Mon Apr 11, 2005 9:47 pm

Post by SiburNY » Wed Apr 13, 2005 7:31 am

Yes, it's the same :). So my program works fine. I guess Judge has now more hard test input.

I just sent you my source code. Thank you.

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 03, 2005 7:55 pm

I don't believe Ivan Golubev's method works. This is the fastest way I can think of implementing it, and it times out. Is there some tweak that can make it faster?

Code: Select all

works now.
Thanks.
Last edited by Abednego on Tue May 03, 2005 8:03 pm, edited 1 time in total.
If only I had as much free time as I did in college...

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Tue May 03, 2005 8:02 pm

Ok. Nevermind. I switched _everything_ to long double, and it got accepted in 0.123 seconds. Strange problem....
If only I had as much free time as I did in college...

Alec
New poster
Posts: 8
Joined: Sun Mar 28, 2004 9:00 pm

Your answer of the last two is wrong

Post by Alec » Sun Aug 07, 2005 7:43 am

eyhk wrote:For sedafcho's input, I got a different output, the last two.
I'm not able to find 2^31 though.

Code: Select all

7
8
15
12
20
31
28748
24559
4813
325147
325148
11036
37937
6432163
146964308
146964307
I had calculated the 2^146964308 with big number.
the first 20 digits is 99999999281501361389...

Alec
New poster
Posts: 8
Joined: Sun Mar 28, 2004 9:00 pm

Post by Alec » Sun Aug 07, 2005 7:58 am

My computer is P-M 1.6G with 512MB. it is about 2sec to finished
but my code got WA or TL on the judge......
my output

Code: Select all

7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146

real    0m1.819s
user    0m1.650s
sys     0m0.038s
SiburNY wrote:Thanks for trying to help me. I use C. I have Athlon XP 2200 768Mb computer. This time I tweaked my code a little. It took 11-12 seconds to finish the following numbers:

Input:

Code: Select all

1
2
3
4
5
111
222
333
444
555
66666
77777
88888
99999
111111
111222
333444
555666
999900
123456
654321
100000
200000
300000
400000
500000
Output:

Code: Select all

7
8
15
12
9
143
629
314
1600
1597
224296
26399
123446
254370
194220
94220
2250226
225093
5766432
63293
78171
70777
325148
3606692
325149
325146
Thank you.

Moussa
New poster
Posts: 6
Joined: Fri Jun 24, 2005 1:29 am

701

Post by Moussa » Tue Aug 30, 2005 7:01 pm

it took me much time in problem 701 but give me run time error
and also i want to know an effecient way to solve this problem cuz i think my way will lead to Time limit exceed
i appreciate the effort of the one who is gonna help

Code: Select all

#include<iostream>
#include<string>
#include<stdio.h>
#include<cmath>
using namespace std;
string mult(string,int);
bool check(string,char*);
int main()
{
	float x,k;
	int div=1;
	string str = "1";
	int n=1;
	char ch[10];
	while(cin>>x)
	{
		div = 1;
		str = "1";
		n=1;
		sprintf(ch,"%d",(int)x);
		while(!check(str,ch))
		{
			
			k = log10(x)/log10((double)2) + (strlen(ch)+n)*1/log10((double)2);
			for(int i=div;i<=ceil(k);i++)
			{
				str=mult(str,2);
			}
			div = ceil(k)+1;
			n++;
			
		}
		cout<<div-1<<endl;

	}
return 0;

}
string mult(string s,int n)
{
	int carry=0;
	int k;
	string result = "";
	for(int i=s.length()-1;i>=0;i--)
	{
		k=(s[i]-'0')*n;
		result.insert(0,(char)((k%10)+48+carry));
		if(k>=10)
		{
			carry = k/10;
		}
		else
			carry = 0;
	}
	if(carry!=0)
	{
		result.insert(0,(char)(carry+48));
	}
	return result;
}
bool check(string s1,char* s2)
{
	int n;
	n = s1.length();
	if(s1.length()%2!=0)
		n++;
	if(n/2<=strlen(s2))
		return false;
	for(int i=0;i<strlen(s2);i++)
	{
		if(s1[i] != s2[i])
			return false;
	}
	return true;
}

lantimilan
New poster
Posts: 11
Joined: Sat Mar 19, 2005 11:12 am
Location: HKU
Contact:

p701, solved but run in 2.531s

Post by lantimilan » Tue Sep 20, 2005 9:46 am

Since there a a number of peope get less than 0.010s to finish, there must be some better algorithm than bruth force on search exponent by
2n+1, 2n+2, ...

Will anyone please give a hint?

thanks
-- This is Unix, any explanatory error message is seen as a sign of weakness

Post Reply

Return to “Volume 7 (700-799)”