tag:blogger.com,1999:blog-29632375.post1201321125320031588..comments2024-06-25T13:05:10.432-07:00Comments on vexorian's blog: SRM 526: The killing wait for resultsUnknownnoreply@blogger.comBlogger3125tag:blogger.com,1999:blog-29632375.post-82531955629521779852013-05-15T21:10:37.966-07:002013-05-15T21:10:37.966-07:00Hi Vexorian in DuckAlignment , (After solving for ...Hi Vexorian in DuckAlignment , (After solving for rows,i solve for columns) <br />I demonstrate that reduce to find a median .<br />If we define X[i] = position of the duck.<br />then we have find a position k (the begin of the queue) that minimize this expresion min( Sum( | X[i] - (k+i) | ) ) . If we take Y[i] = X[i] - i , then the expresion convert in min( Sum( | Y[i] - k | ) ) therefore this k = median of Y.<br />After all this aprouch is more eficient.Luis Vasquezhttp://www.facebook.com/luis.vasquez.507noreply@blogger.comtag:blogger.com,1999:blog-29632375.post-47873551138150468972011-12-11T15:59:46.086-08:002011-12-11T15:59:46.086-08:00You know, I was not very sure about that solution....You know, I was not very sure about that solution. It passed system tests, but without a more formal proof it could be just that the tests were weak.<br /><br />I guess that your idea is based around the idea that you can first select the center of the line. Ok, in that case the row cost (or column cost) will be constant regardless so we end up with the same subproblem of moving ducks from various positions in a row to consecutive positions in that row. So, in theory the middle of the row will coincide with the point with the minimum sum of distances. If that is true, it probably depends on the assumption that there will be at most one duck per row/column.<br /><br />Do you happen to have found a more formal proof?vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-84898858954312906412011-12-06T20:49:57.306-08:002011-12-06T20:49:57.306-08:00In fact, DuckAlignment can be done much simpler. I...In fact, DuckAlignment can be done much simpler. I can't prove my solution mathematically, but I kinda proved it to myself during the contest and my submission passed system tests.<br /><br />Solution. First, find a point with minimal sum of distances to every duck (this can be an empty point). Save this minimal sum of distances - min_d. <br /><br />Then subtract from this min_d one for second and third duck, 2 for 4th and 5th, 3 for 6th and 7th and so on. That's the answer.Sergey Dymchenkohttps://www.blogger.com/profile/09624925799451791143noreply@blogger.com