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

Discussion of Problem 1148. Building Towers

Java MLE
Posted by DWED 13 Aug 2008 16:36
Is it possible to solve this problem in Java without MLE?

If we use HashMap<Integer,Long> as "cache" we get 287k entries in worst case. Even if ww think about raw data (no objects, no overlap) - it is 3.4Mb

Still thinking how to avoid "full-sized" caching (h X m+h X n).
Re: Java MLE
Posted by DWED 15 Aug 2008 03:07
Finally I solved this problem in Java =)
To reduce cache size I used fact that for any N >= Nmax we get f(N,M,H)=const. As analys of cache has shown - it is about 85% of entries. So I built 3 tables - Nmin, Nmax and F.

After that i has maximum 56k entries. But that was also too much for system (huh, i tested on my machine - it got used slightly less than 4Mb...)

I read discussions about this problem and used one hint - we can cache, for example, only even levels. As for performance - it is just 2 times slower... but it gets 2 times less memory... Exactly what we need =)

Good luck.