11251 - Fractions

All about problems in Volume 112. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

11251 - Fractions

Post by sclo »

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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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 :(
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo »

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.

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey »

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?
The biggest problem with most problems is not how to solve the problem, but how to not solve what is not the problem.

Johan
New poster
Posts: 7
Joined: Wed Dec 21, 2005 5:27 pm

Post by Johan »

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

Post Reply

Return to “Volume 112 (11200-11299)”