This problem turned out to be harder than we expected. We rated it a C\/D, yet only 2 teams managed to solve it, the first coming about three and a half hours into the contest. It’s really not a difficult algorithm, but it’s off the beaten path, and requires some thinking and some care.<\/p>\n
Check out the Judge Input<\/a>, the Judge Output<\/a>, the main Solving Program<\/a>, another java solution<\/a>, and one in C++<\/a>. <\/p>\n Look in the spoiler for a description of a solution. The only way the Greedy algorithm can fail is if stretching an early gap limits your options of stretching a later gap. I’m not going to go through a convoluted argument, but it’s true. It’s left as an exercise to the reader to confirm! This problem turned out to be harder than we expected. We rated it a C\/D, yet only 2 teams managed to solve it, the first coming about three and a half hours into the contest. It’s really not a difficult algorithm, but it’s off the beaten path, and requires some thinking and some care. Check […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[6],"tags":[],"class_list":["post-213","post","type-post","status-publish","format-standard","hentry","category-6"],"_links":{"self":[{"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/posts\/213","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=213"}],"version-history":[{"count":2,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/posts\/213\/revisions"}],"predecessor-version":[{"id":217,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=\/wp\/v2\/posts\/213\/revisions\/217"}],"wp:attachment":[{"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=213"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=213"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/serjudging.vanb.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=213"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\n[spoiler]
\nUse a Greedy algorithm. First, assume that the trees are laid out right next to each other, as tightly as possible. Then, find the positions of the smallest and largest trees – let’s say s and t – and then try to stretch the gap between s and s+1 as far as possible, then the gap between s+1 and s+2, then s+2 and s+3, all the way up to t-1 and t. Look at all pairs of trees that are adjacent height-wise (that the Ninjas would jump between) that span each of those gaps, to see how far the gaps can be stretched.<\/p>\n
\n[\/spoiler]<\/p>\n","protected":false},"excerpt":{"rendered":"