11036 - Eventually Periodic Sequence
Moderator: Board moderators
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
11036 - Eventually Periodic Sequence
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
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
hi i got TLE ,
plz let me know if you find the reason
Code: Select all
//removed
Last edited by arsalan_mousavian on Wed May 31, 2006 7:28 am, edited 1 time in total.
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
This part can be done much more efficient... Try to remember the numbers already generated in a more efficient way....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 ) ; } ...
Hint: Instead of quadratic time comlexity, you can easily get O(n log n) time comlexity or even better.
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
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:
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)
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 %
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)
-
- Experienced poster
- Posts: 111
- Joined: Mon Jan 09, 2006 6:19 pm
- Location: Tehran, Iran
- Contact:
There is R.Floyd's cycle finding algorithm, which needs O(1) memory.
http://en.wikipedia.org/wiki/Floyd's_cy ... _algorithm
http://en.wikipedia.org/wiki/Floyd's_cy ... _algorithm
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
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)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)
-
- Experienced poster
- Posts: 161
- Joined: Tue Oct 25, 2005 8:38 pm
- Location: buet, dhaka, bangladesh
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
----------------
the world is nothing but a good program, and we are all some instances of the program
-
- New poster
- Posts: 44
- Joined: Sun Apr 27, 2003 3:17 am
- Location: Rio Grande do Norte - Brazil
- Contact:
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...
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
UFRN HDD-1
Brasil
-
- A great helper
- Posts: 481
- Joined: Sun Jun 19, 2005 1:18 am
- Location: European Union (Slovak Republic)
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.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.
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
