11036 - Eventually Periodic Sequence

[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?

[mf]

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

[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]

hi i got TLE ,

Code: Select all

//removed

plz let me know if you find the reason

[Martin Macko]

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]

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

[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]

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

[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]

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]

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.

[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]

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

[mf]

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]

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 .