OJ Board

Please remove your code if it can get AC after clean the queue ^_^.

Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^.

O(n log n) preprocessing -> O(log n) query answering? If you use binary trees, I think the preprocessing part is O(n) not ...

898989 wrote:Hi
Can any one describe efficient algorithm for the problem that will pass the system tests.

Think about Range Maximum Query(RMQ), then you can answer each query in O(lg N) operation after O(N lg N) for build the tree. You must transform the problem to RMQ first ^_^.

Thanks for DP and Darko .

I only know the value of A and N, how to solve this equation:

(A^X) % N == 1

I must compute the value of X.
(2<=A,N<=1000000000).

Thanks

Timo

Thanks for help me
I have got AC...

Timotius Sakti

sorry I have post wrong title
I am asking for 11138 - Nuts and Bolts

Please forgive me moderator

I have stuck to solve this problem .
Can anybody tell me how to solve this problem ?

Thanks

Timotius Sakti

Planeyang wrote:sorry about my careless.
Thank you misof and Timo

The Program of Timo is really cool!
That's a very good idea.

the idea was come from misof

I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC

I used Rabin Karp method for hashing but it gave me a WA
what is your method?

sorry for late reply...

I used my own method to solve this problem ^ ^ (that's secret), but if you have used Rabin Karp ...

freq = 0

while read number
if freq == 0 then answer = number
else
if number == answer then freq=freq+1
else freq=freq-1
end while

output answer

Can anybody give me hint to solve this problem.

http://acm.zju.edu.cn/show_problem.php?pid=2667

Thanks

Timotius Sakti

I am very very agree with Jan.
I am sure that the judge's output is wrong.

Darko wrote:I used java.util.Hashtable, I don't have my own.

So, that's the only way to solve it? I guess I'll have to reinvent yet another wheel

don't store the substring in the hashtable, just store the value....

26^10 < 10^18

I hope you understand....

Darko wrote: Oh, I did try using Hashtable, but it gives me MLE - it is just too expensive to use (on UVa, at least).

I think your implementation of Hashtable is wrong.
I have use Hashtable too.. and it give me AC