11036 - Eventually Periodic Sequence

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

Moderator: Board moderators

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

11036 - Eventually Periodic Sequence

Post by ayon »

hi, i got wrong answer, i used long long data type. Is that, before % N operation, the result may be long enough not to fit in "long long"? can you give me some tricky inputs?
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

The result may be far bigger than 2^64, of course.
Do every arithmetic operation modulo N.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

According to what is allowed by the problem description to be on the input, the actual judge input is probably too weak... There is probably no test case with a really big period (like 10M, or so).

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

hi i got TLE ,

Code: Select all

//removed
plz let me know if you find the reason
Last edited by arsalan_mousavian on Wed May 31, 2006 7:28 am, edited 1 time in total.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

arsalan_mousavian wrote:hi i got TLE ,

Code: Select all

		...
		while ( 1 ) 
		{
			x = Eval ( root ) ;
			for ( long long i=0 ; i<V.size () ; i++ )
				if ( x == V[i] ) 
				{
					result =V.size () - i ;
					goto Final ;
				}
			V.push_back ( x ) ;

		}
		...
This part can be done much more efficient... Try to remember the numbers already generated in a more efficient way....

Hint: Instead of quadratic time comlexity, you can easily get O(n log n) time comlexity or even better.

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

thanks Martin Macko , i got accepted but in 9.0 seconds do u have any idea to optimize my code ?

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

I solved this in Java, but it's very ugly.

I realized I should've built a tree and whatnot, but I still wanted to avoid implementing things that are part of "regular" Java. I guess I won't be able to do that indefinitely.

Now, I have no idea how to deal with this case:

Code: Select all

11000000 0 x 1 + N %
Any suggestions?
Or maybe that was a typo and they meant 1,000,000 instead of 11,000,000? If they raised the memory limit to 64MB, it becomes easy, so I don't know... (not sure what the limit was during the contest)

arsalan_mousavian
Experienced poster
Posts: 111
Joined: Mon Jan 09, 2006 6:19 pm
Location: Tehran, Iran
Contact:

Post by arsalan_mousavian »

i don't think these kinds of input exists among the input data of OJ

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

There is R.Floyd's cycle finding algorithm, which needs O(1) memory.
http://en.wikipedia.org/wiki/Floyd's_cy ... _algorithm

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

Darko wrote:Or maybe that was a typo and they meant 1,000,000 instead of 11,000,000? If they raised the memory limit to 64MB, it becomes easy, so I don't know... (not sure what the limit was during the contest)
You can easily fit 11M of chars into the memory limit. (You don't have to remember the actual sequence, it's sufficient to remember only if a number was already generated)

ayon
Experienced poster
Posts: 161
Joined: Tue Oct 25, 2005 8:38 pm
Location: buet, dhaka, bangladesh

Post by ayon »

i used tree for searching(10-ary tree, might be called trie), that took not more than 1MB for the OJ, that was also fast enough to run in 0.6xx sec. implementing tree is not that hard.
ishtiak zaman
----------------
the world is nothing but a good program, and we are all some instances of the program

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko »

Heh, Martin, I actually started with booleans (single bytes) and then, for some reason, I decided that I couldn't solve it that way. You are right, it is easy any way you look at it.

That Floyd's algorithm looks interesting, I'll have to check it out.

danielrocha
New poster
Posts: 44
Joined: Sun Apr 27, 2003 3:17 am
Location: Rio Grande do Norte - Brazil
Contact:

Post by danielrocha »

A couple of observations about this problem:

1. There's no such case as (x+1)%N with N=11*10^6 in the judge test cases... I don't really understand why, since I didn't even submitted my code during the contest because it was to slow (4 seconds) to solve this case.

2. Floyd's Cycle detection algorithm is indeed very interesting, but (as far as I can tell) it's not the only way to solve this problem: you can use a bool array (size N) and solve it in time O(seq + c + c), where 'seq' is the size of the sequence without the cycle and 'c' is the cycle size.

Hope this helps someone...
Daniel
UFRN HDD-1
Brasil

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf »

danielrocha wrote:you can use a bool array (size N) and solve it in time O(seq + c + c)
Um, not quite. You have to spend additionally O(N) time to initialize this bool array.

Floyd's algorithm runs in time O(<size of cycle> + <size of precycle>), assuming that computing f(n) takes O(1) time.

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

mf wrote: Um, not quite. You have to spend additionally O(N) time to initialize this bool array.

Floyd's algorithm runs in time O(<size of cycle> + <size of precycle>), assuming that computing f(n) takes O(1) time.
Fortunatelly it is enough to initialize the bool array just once. After every test case you know which elements of the array have changed. Thus, you need to reinitialze only them.

The Floyd's algorithm uses at least 3(p+c) calls to the f(n) function, while for the other method needs only 2(p+c) calls, where p is the size of the precycle and c the size of the cycle. However, if we wouldn't have enough memory the Folyd's algorithm would've been much better :wink:.

Post Reply

Return to “Volume 110 (11000-11099)”