ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
back to board

Discussion of Problem 1032. Find a Multiple

AC; after little bit tweaking the code I got TL#4
Posted by ile 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.
Posted by dAFTc0d3r [Yaroslavl SU] 26 Mar 2010 10:49
And I'm interesting how to solve this in 0,015s.
Re: 0,015s
Posted by ile 27 Mar 2010 00:26
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.
Re: 0,015s
Posted by dAFTc0d3r [Yaroslavl SU] 27 Mar 2010 01:42
Yeah, there is a nice idea. =)
Re: 0,015s
Posted by Petrenuk (NNSTU) 6 Feb 2011 00:20
0.14 seconds on JAVA, O(nlogn + n) solution