Is there any good ways of doing this problem without bruteforce?
My program takes a very very long time to check if a case is impossible, but if it is possible, then generates the solution rather quickly. For some input values, it is easy to prove mathematically that they are impossible.
11251 - Fractions
Moderator: Board moderators
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
I noticed that you now have a solution that runs in 0.004 seconds. May I assume that you've found the trick? Or is it a printf solution? If the former, could you shed some light?
My 'brute-forcer' finishes just in time, but I had to 'wax it up' by adding printfs for the slowest two inputs
My 'brute-forcer' finishes just in time, but I had to 'wax it up' by adding printfs for the slowest two inputs
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
It's just printf's. If I tried to generate all of them it also tle. It also just finishes in time if I printf the slowest cases, like the ones with base > 25.
Also I have to also figure out which ones are impossible, so I don't generate them. It seems that if it can't find a solution in 1 sec, then that case is impossible.
Also I have to also figure out which ones are impossible, so I don't generate them. It seems that if it can't find a solution in 1 sec, then that case is impossible.
-
little joey
- Guru
- Posts: 1080
- Joined: Thu Dec 19, 2002 7:37 pm
I see 
About the impossible cases: they will not appear in the input, so once your solution is fast enough for the possible cases, you're done.
Anyone else wants to comment on a fast solution?
About the impossible cases: they will not appear in the input, so once your solution is fast enough for the possible cases, you're done.
Anyone else wants to comment on a fast solution?
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.
My system is about twice as fast as the UvA judge.
In my program where I pick the next digit I tried to both iterate both forward and backward. When I iterate forward it takes me 1654 seconds to compute the answers for all valid inputs.
When I iterate backward I can do everything except (B=27,N=24) and (B=26,N=13) in a total time of 5.3 seconds. Those two included it takes me 37.1 seconds. I'm not sure why this makes such a big difference, apparently solutions are more likely to have larger digits at the back of the numerator, but why?
I decided to precalculate everything, but I wonder if there is another trick.
Johan de Ruiter
In my program where I pick the next digit I tried to both iterate both forward and backward. When I iterate forward it takes me 1654 seconds to compute the answers for all valid inputs.
When I iterate backward I can do everything except (B=27,N=24) and (B=26,N=13) in a total time of 5.3 seconds. Those two included it takes me 37.1 seconds. I'm not sure why this makes such a big difference, apparently solutions are more likely to have larger digits at the back of the numerator, but why?
I decided to precalculate everything, but I wonder if there is another trick.
Johan de Ruiter