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 1005. Stone Pile

What is "mid in the middle" algorithm for solving this problem?
Posted by Squire [Lviv NU] 30 Sep 2011 22:45
Re: What is "mid in the middle" algorithm for solving this problem?
Posted by Tigran92[RAU] 17 Oct 2011 20:49
Meet-in-the-middle is algorithm which allows us to solve O(2^n) complexity problems for O(2^n/2) time. In this problem you can use meet-in-the-middle: divide the peal into two peals b = {a1 a2 a3 . . . an/2}, c = {an/2 + 1, a2, . . . an}. Then calculate all subvalues of b and store it in s1, same for c and store in s2.Then sort s1 and s2. Now you must calculate Min(pealsum - 2 * (s1j + s2k)).This algo takes O((2^(n /2))^2) time instead of O(2^n), but   O((2^(n /2))^2) = O(2^n). Notice that s2 is sorted then we can use binray_search then we have O(2^(n/2)log(2^n/2))=O(2^(n/2) *(n/2)).

Edited by author 17.10.2011 20:50
Re: What is "mid in the middle" algorithm for solving this problem?
Posted by eddycael 17 Feb 2014 05:41
Hello, i am learning about meet in the meedle, please explain why Min(pealsum - 2 * (s1j + s2k)) thanks (Sorry for my poor english)
Re: What is "mid in the middle" algorithm for solving this problem?
Posted by VK 28 Aug 2014 04:53
I also haven't understood  Min(pealsum - 2 * (s1j + s2k)). I'd appreciate if someone explain it. But, you can calculate s1 and s2 as sum of all possible combinations: +/-a1 +/-a2... ++/-an and +/-b1 +/-b2... ++/-bn. Then find min(s1j + s2k). Here `meet in the middle' to reduce complexity, sort s2 and use binary search for lookup. Does it make sense?