Another Thursday. Another Code Jam review because writing about anything else would have taken even more time…
Problem 1 New Elements: Part 1
Problem Statement
Muriel is on the path to discovering two new elements that she has named Codium and Jamarium. She has not been able to isolate them yet, but she wants to start investigating some important properties, like their atomic weights, by indirect means. Since Muriel is working with a single isotope of Codium and a single isotope of Jamarium, their atomic weights are strictly positive integers.
Muriel managed to create N different molecules, each of which contains one or more atoms of Codium and one or more atoms of Jamarium, and no other elements. For each molecule, she knows how many atoms of each element are present in it. The molecular weight of a molecule is the sum of the atomic weights of all the atoms it contains.
As a first step towards figuring out exact molecular weights for the molecules and atomic weights for the two elements, Muriel wants to sort the molecules by strictly increasing molecular weight. To assess the difficulty of that task, she wants to know how many orders are valid considering only the information she has right now. An ordering of the molecules is considered valid if there exist values for the atomic weights of Codium and Jamarium such that the ordering is strictly increasing in molecular weight.
To give an example, we represent each molecule by the ordered pair of the number of atoms of Codium and Jamarium it contains. If Muriel has 3 molecules represented by (1, 1), (2, 1) and (1, 2), there are two possible orderings that can be strictly increasing in molecular weight: (1, 1), (1, 2), (2, 1) and (1, 1), (2, 1), (1, 2). The first ordering is valid for any assignment of atomic weights in which Codium is the heaviest of the two elements, and the second is valid for any assignment in which Jamarium is the heaviest. The only case remaining is when both Codium and Jamarium have the same atomic weight, in which case (1, 2) and (2, 1) have the same molecular weight, so no strictly increasing ordering can be produced for that scenario.
My Solution
Unfortunately the problems are getting longer and longer…
And I think I spent at least one minute wondering why they are not simply Codium and Jamium.
Anyway, this problem is essentially asking how many proportions of relative weights for Codium and Jamarium are there for which two atoms have the same total weight. These proportions do not produce legal ordering by themselves, but they are separators of different orderings. Hence the answer is one plus this number.
Problem 2 Lottery
Problem Statement
The Pottery Palace is going to run a lottery featuring some valuable vases by the artist Cody-Jamal. The lottery works as follows:
- 100 people get to play in the lottery. Each player has a unique number between 1 and 100, and is given a single token with that number.
- There are 20 empty clay vases on a table, numbered 1 through 20. The vases have narrow openings that are large enough to accept a token, but small enough that players cannot look inside to see the contents.
- On the i-th day of the lottery, the player with token number i chooses a vase and puts their token in that vase. Since the vases are all identical (apart from their labels), every player will choose one uniformly at random and independently of all other players’ choices.
- On day 100, after player number 100 has inserted their token, the organizers shake the vases to determine how many tokens are inside each one. If there is exactly one vase that has fewer tokens than any other vase, then that one is the “winning vase”. The organizers then pour out all of the tokens in that vase, and every player whose number is written on one of those poured-out tokens wins a vase! If multiple vases have the same minimal amount of tokens, nobody wins anything.
You have been hired to test the security of the lottery, and you will participate in some trial runs. The company will always assign you the number 100 — that is, you replace player 100.
You have found some ways to tamper with the lottery at night, but security is tight, so you can only do so much! Specifically, after each of the first 99 days of the lottery, you may do exactly one of the following:
- forge a token with the player number of your choice (between 1 and 100, inclusive), and add it to a vase of your choice. You are a very good forger: if there is a winning vase, any forged tokens in that vase will cause the players with those numbers to win (with one exception; see below).
- use a special camera to see the numbers on all of the tokens in one vase of your choice
You may perform different actions on different nights, and you may choose dynamically: you do not need to decide on all of your actions in advance.
On the 100th day, it is your turn to insert your token into a vase of your choice (you do not need to choose uniformly at random). You cannot perform any other actions on that day.
You know that if there is a winning vase with more than one token for the same player, it will be obvious that cheating has occurred and nobody will win. However, it does not matter if other vases contain more than one token for the same player because the organizers never see those tokens.
Your goal is to be a winner in at least 90% of the test cases.
My Solution
This problem is, I believe, pretty revolutionary, as it requires you to provide a strategy that works good enough over a given distribution of inputs.
As I did not have many ideas for this question, I decided to start from a toy strategy and gradually improve it.
Since the goal is to ensure the vase with your vote to win, the sub-goals are to have a plan about what vase to vote, and to keep other vases from threatening that vase.
Hence, I mix the two options with a fixed pattern (which ended up in a 3:1 cycle).
For each peek attempt, we try to look at something that has greatest uncertainty (as in have not been peeked for long), as well as threat.
What is more weird is the strategy of forging votes. A intuitive strategy is to always hamper the current second placed vase (based on our best effort to predict), since this gives the current best vase a greatest edge over its alternatives. However, this strategy does not work well enough, presumably because we have absolutely no control over the other 99 voters, and they might simply ruin your plan.
A more refined strategy is to hamper the ninth placed vase first, then eighth, seventh… as the time goes by. Only for the last few rounds, we focus on the second placed vase to ensure the vase we pick is the winner.
The strategies, especially the one for the forgery operation, involves lots of hyper-parameters. Fortunately, by increasing the number of test cases, we can check whether each potential modification improves the strategy or not with pretty high level of confidence.
My first submissions at a locally measured success rate of 92% failed the official test… which I have to blame my bad luck. But further improvements brought it to 94% and nothing could prevent my code any more.
This problem also brings an interesting question: what if we approach problems like this with reinforcement learning? To be honest, I have not done much reinforcement learning so far, but this is a fascinating opportunity to try fun stuff.
Problem 3 New Elements: Part 2
Problem Statement
The problem shares the same story with the first problem, so I’ll only quote the actual different parts.
As a first step, Muriel sorted the molecules by strictly increasing molecular weight. Now she wants to find out possible integer values for the atomic weights of both Codium and Jamarium that are consistent with the ordering. Since she is aware there could be many consistent pairs of values, she wants one that minimizes the atomic weight of Codium. If there are multiple pairs in which Codium’s atomic weight is minimum, she wants the one in which Jamarium’s atomic weight is minimum.
My Solution
It is pretty easy to find a open range to represent all the feasible weight proportions between Codium and Jamarium. The problem is we need both of them to be integers. In other words, we are to find a fraction of smallest numerator that falls within a known region.
I immediately realized that this problem could be solved with a Stern–Brocot tree. Since it is a binary tree, with deeper nodes having both larger numerators and denominators, we only need a binary search to find the first node to fall in the range and output it.
Only after the competition and finding my solution accepted, I realized that the said binary search still degenerates to O(n) for extreme inputs…
Problem 4 Contransmutation
Problem Statement
Last year, we asked you to help us convert expensive metals into lead. (You do not need to know anything about the previous problem to solve this one.) But your country’s leader is still greedy for more lead!
There are M metals known in the world; lead is metal number 1 on your periodic table. Your country’s leader has asked you to use the metals in the treasury to make as much lead as possible.
For each metal (including lead), you know exactly one formula that lets you destroy one gram of that metal and create one gram each of two metals. (It is best not to think too much about the principle of mass conservation!) Note that it is possible that the formula for the i-th metal might produce the i-th metal as one of the products. The formulas do not work with partial grams. However, you can use each formula as often as you would like (or not at all), as long as you have a gram of the required ingredient.
If you make optimal choices, what is the largest number of grams of lead you can end up with, or is it unbounded? If it is not unbounded: since the output can be a really big number, we only ask you to output the remainder of dividing the result by the prime 109+7 (that is, 1000000007).
My Solution
I can’t help but wasted another minute or two wondering about the terrible pun about lead and leader.
Anyway, first find out all strongly connected components and sort them from the destinations to the sources. Then for each SCC we can calculate its “optimal lead production per gram” by discussing all the cases (which is more than I initially thought).
A trick that helps a bit is to introduce an extended number type that includes 0, all positive integers modulo 109+7 and infinity, and build various operations over this type.