11036 - Eventually Periodic Sequence

[little joey]

Hmm, if you use an array of (unsigned) chars instead of an array of 'booleans', you only need to initialise once in every 256 cases; not that it will save you much time, I think.

I agree with the previous posts that avoiding the extreme cases in the actual input for this problem, makes it misleading. The problem would be better off with a lower, but 'do-able in worst cases' limit. Unless, of course, there is an algo that needs less than O(N) function evaluations.

[fernando]

I used map<int,int> for this problem and get AC in 0.6 sec , i keep record of the time i was on a particular number, so when i found a number which was inserted in the map i found a cycle, so the length of the cycle is current_time - time_recorded_in_map

[Solaris]

Hi,

Thanks to mf for mentioning the Floyd's Algorithm. It was really a nice algo and I have just got AC .. but the timing came really bad (about 4 sec). I had a few questions:

1. Well .. according to wiki .. I made two iterations and calculated the GCD to get the actual period. Is there any better way of doing it??

2. I used a stack (of integers) to evaluate the function. But is there any faster way???

Thnx in advance

[sclo]

I believe that floyd's algorithm is slower on this problem compared to the other algorithm.

[Ecou]

Getting WA on this code:

Code: Select all

// AC

Can't figure out where it's wrong, and example runs fine,
plus all i can think of, so looking for failed test-case.

[Martin Macko]

Can't figure out where it's wrong, and example runs fine,
plus all i can think of, so looking for failed test-case.

Try the following input:

Code: Select all

11000000 10999998 x x x x * * * N %
0 0 0 N %

The correct output is:

Code: Select all

1250

[Ecou]

Thanks, fixed. I forgot to modulo after each operation.

PS: If you read this for testcases, the above is not like promised because of n > N.

[Martin Macko]

Thanks, fixed. I forgot to modulo after each operation.

PS: If you read this for testcases, the above is not like promised because of n > N.

Ups, sorry I'll fix it.

And btw, please, remove your code after having accepted.