A week when easy is enough

Last week TopCoder Open 2015 Round 2C presented three tricky, if a tiny bit standard, problems (results, top 5 on the left, my screencast, parallel round results). As a result, a fast solution for the easy problem was enough to qualify for the next round, just like in old days :) Of course, a successful challenge together with a not-so-fast solution was also enough. Congratulations to everybody who qualified!

The medium problem has tripped the most competitors, with just 2 correct solutions out of 54 submitted. It went like this: you're placing 8 segments of given lengths into a longer segment of given length one by one in the given order. The smaller segments must lie inside the longer segment, and must not intersect. You can pick any position for a small segment that does not contradict the above rule. When there's no such position, the small segment is not placed into the large segment at all (but if there's at least one possible position, you have to pick one). For each small segment you need to return one of three outcomes:

• it will definitely be placed into the longer segment irrespective of how previous segments are placed, or
• it will definitely not be placed into the longer segment, or
• both situations can occur depending on placement of previous segments.

At first sight, the problem seems straightforward: we probably need to compare some sums of lengths of small segments with the length of the large segment. However, after some more thinking pretty tricky cases come to light: for example, even if some subset of previous segments can fill the large segment completely and thus leave no space for the current segment, it might happen that it's impossible for exactly this subset to appear inside the large segment since we can't skip a segment - we must place it if there's space.

At this point, a solution from the other end of the spectrum comes to mind: what if we try all possibilities of how the small segments are placed, and carefully write down all constraints that appear - i.e., if a segment was not placed, then all gaps currently have strictly smaller length; if a small segment is placed into a gap that is bounded in length, we get two gaps such that their total length is bounded, and so on.

This solution has quite a few different cases to consider, and thus brings a temptation to look for a simpler solution, maybe some invariant that holds or some simple inequalities that we should check.

But it turns out that all (to the best of my knowledge) such simplifications fail, and one simply has to take their time and carefully track the facts about the remaining gaps as we place the segments.

Thanks for reading, and check back tomorrow for this week's summary!

Tweet