Discussion @ 1032. Find a Multiple @ Timus Online Judge

ile AC; after little bit tweaking the code I got TL#4 [4] // Problem 1032. Find a Multiple 26 Mar 2010 01:55

This is ridiculous!!
My AC solution (ACed twice) works in 0.950 seconds. Which is actually O(n^2). The code is long and nasty... After some "improvements" - ie changing ArrayList to LinkedList/getting rid off BitSet/etc - the running time should decrease drastically!! but it gives me TL... WTF?
I was sure, that my "better" code works FASTER, since there is much less operations to perform...
Can anyone help me with it? I can send the code to get feedback.
Thanks!

dAFTc0d3r [Yaroslavl SU] 0,015s [3] // Problem 1032. Find a Multiple 26 Mar 2010 10:49

And I'm interesting how to solve this in 0,015s.

ile Re: 0,015s [2] // Problem 1032. Find a Multiple 27 Mar 2010 00:26

well...
There's good idea in neighbor thread, which proves that solution always exist. It can help you solve it in O(n).
Or... you can think up your own ideas based on remainders... There's up to N remainders only... so I used BFS without considering duplicates... it works fast enough in Java.

dAFTc0d3r [Yaroslavl SU] Re: 0,015s [1] // Problem 1032. Find a Multiple 27 Mar 2010 01:42

Yeah, there is a nice idea. =)

Petrenuk (NNSTU) Re: 0,015s // Problem 1032. Find a Multiple 6 Feb 2011 00:20

0.14 seconds on JAVA, O(nlogn + n) solution

Discussion of Problem 1032. Find a Multiple