Problem E looked tedious at first, but coming up with the right idea helped make the implementation really easy. You are given two trees on the same set of vertices, one blue and one red. You want to convert the blue tree into the red one, step-by-step. At each step, you must take any path consisting of blue edges, add a red edge connecting its endpoints, but remove one of the edges of the path. After n-1 steps all blue edges will be removed, and n-1 red edges will be added, and you want those edges to form the required red tree.
Die 1: = < > != <= >=
Die 2: 4 + - ( ( )
Die 3: 0 / / / 8 +
Die 4: 2 3 4 5 - )
Die 5: + - * / 1 9
Die 6: 6 7 + - ( )
You need to pick a die, then roll it (by interacting with the judge program), and record the symbol that appears. Then you can do it again, using either the same or a different die, and so on, doing at most 1000 rolls. At some point you need to stop rolling, and form a correct mathematical expression (equality or inequality) by concatenating all recorded symbols in some order. No need to optimize anything - just build any correct expression after at most 1000 rolls.
There must be a ton of different approaches in this problem, as any valid expression suffices. The first idea lies on the surface: since the first die always gives us a comparison, and there must be exactly one comparison in each expression, we can start by rolling the first die once. This will give us the type of comparison we're building. In the remainder of the explanation I will assume we get "=", as that is the most tricky case - the rest can be handled in the same manner.
But then, things get not so easy. First, we should get enough symbols to form any syntactically valid expression: we should get the same amount of opening and closing parentheses, and the amount of operations we get should be two less (one for each side) than the amount of numbers we have (after the contest I've noticed that the numbers can be joined together to form multiple-digit numbers, but I did not notice this in the heat of the moment). Then, of course, we need to form not just syntactically valid expression but a correct equality.
The next idea is: the "correct" part is actually much easier than "syntactically valid" part. Assuming we have only digits and +/- signs, then we just need to split the digits into two groups with the same sum, and with enough different digits this is always possible.
Now, we need to find a way to get the right left-right parenthesis balance, and the right operation-digit balance. The two key dice that help accomplish that are, for example, die 3 and die 2. Let's assume we already rolled some dice, and we have more closing parentheses than opening parentheses. Then we can repeatedly roll die 2 until we get the right parentheses balance. After that, let's assume we have more digits than operations. Then we can repeatedly roll die 3 until we get the right balance (and this won't affect the parentheses).
So now we only need to prepare the ground for rolling dies 2 and 3 - we need to roll some dice in such a way that we have more closing than opening parentheses, and much more digits than operations (so that even rolling die 2 a few times does not cancel that), and enough different digits and +/- operations to build our equality in the end. Die 3 also gives us "/" operations, but to avoid complications we'll just divide 0 by some numbers to get rid of those.
It's easy to see now that die 4 is exactly what we need. Let's roll it a few (say, 100) times. We will have a few (~16) closing parentheses, and a lot more digits than operations, and those digits will be from a wide variety, so we're guaranteed to get two equal sums. Now we also need a 0 to handle the divisions, so let's roll die 3 until we get it. After this we can switch to "die 2, then die 3" strategy described above to get the right balances, and finally form our equation.
How did your team solve this problem? Maybe there's a simpler approach?
No comments:
Post a Comment