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 1863. Peaceful Atom

What is algo???
Posted by IgorKoval(from Pskov) 1 Nov 2011 00:06
Head-on solution have complexity O(2^40)=O(10^12). It's very slow. How do it faster?
Re: What is algo???
Posted by svr 1 Nov 2011 07:46
I used 40=30+20
First 20- memorization
second 20 as 2^20=10000000- that normaly
Re: What is algo???
Posted by IgorKoval(from Pskov) 2 Nov 2011 02:34
Could you explain your solution more in detail?
"First 20- memorization" What it mean in Russian?
I understood that what we do with second 20. But can not understood that what we do with first 20. =)
Re: What is algo???
Posted by svr 2 Nov 2011 07:01
I meant that first 20 also as 2^20 or with brute force aproach,
but result of first 20 we place in arr[1..1000000](memorization)
sort arr than in second 20 use log-bin search in arr.
Re: What is algo???
Posted by IgorKoval(from Pskov) 3 Nov 2011 02:31
Thank you very much. You is good man! I got AC. =)
Re: What is algo???
Posted by Harkonnen 16 Aug 2022 08:33
It's a bit more complicated than that because you should care about rod not getting off the rails during the process as well, so you can't just pick arbitrary memorized sequence which gives suitable end-result, it also must stay within limits while it performs memorized shiftings. Looks like segment tree algo, not just plain binary search (or tests are very weak).

P.S: Got AC with 0.5 sec and 44Mb, probably could've done better. For every 2^20 endings I track range of start values where it is suitable (i.e. fits for its entire internal history), then for every 2^20 beginnings (sorted) I track min/max of currently active segments via two heaps.

Edited by author 16.08.2022 11:51
Re: What is algo???
Posted by Harkonnen 16 Aug 2022 12:17
P.P.S: Ah, I'm dumb! Memorizing first 20 leads to much easier algo when last 20 are brute-forced (not vice versa). 0.265 sec, 7 Mb. Yet, coding that monster from previous "P.S" was fun :)