The Basic Idea

The basic approach here is to generate all the possible ways to split the rock, then check each combination to see if it works. You can use a recursive algorithm to generate all the possible splits, and it's a good idea to only generate the pieces in ascending order because for this problem, 1 1 3 is the same combination as 1 3 1.

For the example of a ~12~ kg rock split into ~4~ pieces, the possible splits are:

1 1 1 9   1 1 2 8   1 1 3 7
1 1 4 6   1 1 5 5   1 2 2 7
1 2 3 6   1 2 4 5   1 3 3 5
1 3 4 4   2 2 2 6   2 2 3 5
2 2 4 4   2 3 3 4   3 3 3 3

Checking each combination for whether it works is where things get a bit tricky.

An Inefficient Solution

You could use a recursive backtracker to test all the possible ways to place the pieces on the balance. Each piece could be on the left, on the right, or not on the balance at all. For each combination, the difference between the two sides of the balance is the amount of corn you can weigh. In the example above, there are ~81~ possible combinations for each set of ~4~ pieces. You keep track of which amounts of corn are covered as you generate the possible combinations and a split is good if it covers all the numbers from ~1~ to ~R~.

This approach works, but the problem is that the number of combinations you might have to check grows exponentially (~3^P~). Depending on your code, you will probably only solve some of the test cases within 30 seconds if you use this method.

An Observation

If you start generating and testing splits for any large problem (e.g. ~10~ rocks and ~100~ kg) you might start to see a pattern emerge. The first thing you might notice is that you always need a rock of size ~1~. Without this rock, you could never weigh the quantity ~R-1~ (where ~R~ is the size of the original rock). So every split you generate should always start with ~1~, and this makes things faster.

But the bigger pattern that emerges is that the ~n^\text{th}~ piece never seems to get larger than ~3^{n-1}~. So a split that starts ~1, 3, 9, 27, \dots~ could work, but a split that starts ~1, 3, 10, 29, \dots~ could never work. You can use this fact to limit the splits that you try and this might help you get one more test case before your time is up.

An Efficient Solution

But if you think more deeply about the structure of the possible splits, it could lead you to an even more efficient solution that would be easily fast enough to complete all of the test data within 30 seconds. Can you figure it out? Or do you have a completely different approach that works? Post your ideas to the appropriate forum at compsci.ca!

It has already been pointed out that there is a ~3^{n-1}~ upper limit on the size of the ~n^\text{th}~ piece. But in fact, there is a tighter upper bound on the size of any piece: ~2T+1~, where ~T~ is the total of all the previous pieces in sorted order. For example, if you have already generated pieces of size ~1~, ~2~ and ~5~, the next piece can be as big as ~2 \times 8 + 1 = 17~, but no bigger. The reason is that the previous pieces can handle all quantities from ~1~ to ~8~ and you can subtract these quantities from a larger number but ~17-8 = 9~. If the next piece was ~18~ or bigger, you wouldn't be able to weigh a ~9~ kg sack of corn.

This leads to a much more efficient check on your splits. Instead of using a backtracker to check all the combinations, just make sure that the first piece is of size ~1~, that the pieces all add up to ~R~, and that the upper limit of ~2T+1~ is respected for every piece. That leads to a solution that finishes very quickly for all test cases.

Other Solutions?

It seems to me that dynamic programming should be possible when checking splits, though it is unlikely to be as efficient as the approach described above. It also seems to us that there might be a mathematical formula to compute the answer directly given ~P~ and ~R~, which would be superefficient. But at the time of writing, the contest team hadn't found either solution. Let us know if you figure it out, by posting to the compsci.ca discussion forum.