tag:blogger.com,1999:blog-31847281.post9005100106787292592..comments2018-05-17T01:18:38.572-07:00Comments on Entropy always increases: IOI 2012 Day 2 analysisBruce Merrynoreply@blogger.comBlogger2125tag:blogger.com,1999:blog-31847281.post-71151463250096613122012-09-28T04:48:08.964-07:002012-09-28T04:48:08.964-07:00Is the following observation correct for "Jou...Is the following observation correct for "Jousting tournament":<br />As long as some candidate is above the late knight, we don't care what his actual rank is. So we can replace everyone's rank as 0 (knights lower than the late knight), 1 (late knight) or 2(knights higher).<br />So the range maximum query reduces to finding whether a range is completely filled with 0, which is simpler.Nadeem Moiduhttps://www.blogger.com/profile/13795897650911483828noreply@blogger.comtag:blogger.com,1999:blog-31847281.post-35492697642811247072012-09-27T22:43:42.195-07:002012-09-27T22:43:42.195-07:00I may be wrong, but isn't the fact that the gr...I may be wrong, but isn't the fact that the graph is a tree a proof of your original conjecture? As, on a tree, any two vertices have a unique path between them, any vertical movement that doesn't take you from one strip to the next strip on that path will eventually have to be undone, that is, it could never be present on an optimal route. Do the same thing to a graph of the vertical strips to prove it for the x-distance.ffaohttps://www.blogger.com/profile/05368412467671894977noreply@blogger.com