Problem 2: first 30 numbers are $$$2^0$$$ to $$$2^{29}$$$, then 70 random trash numbers (I used $$$10^6$$$ to $$$10^6 + 69$$$ and added all those as the 70th number.)

When the judge gives you the B array, you try to minimize the difference between the two subsets that add to B (i.e. ignoring A) You do this by maintaining the difference of the two subset sums, and if the first sum is larger then insert the current element to the second; else insert into first. You can keep the difference under $$$\operatorname{max}(B_i)$$$.

Then you just use the $$$2^0$$$ to $$$2^{29}$$$ to make up for the difference (grade school math). Finally output the smaller-sum subset with the adjustments, and also output the sum of the first 69 trash numbers (i.e. the 70th trash). You're done!

Who else spent 1 hour on B and then realized $$$N$$$ is constant?

And why wouldn't they emphasize such a thing since the sample contains $$$N= 3$$$ !!!

Problem C is range DP. Let $$$dp_{ij}$$$ be the answer to the given problem if we only considered exercises $$$i$$$ through $$$j$$$. Then, $$$dp_{ii}$$$ is simply twice the number of weights needed for exercise $$$i$$$. We can compute $$$dp_{ij}$$$ for $$$i < j$$$ by first placing all weights that are included in all exercises $$$i$$$ through $$$j$$$ (let there be $$$N$$$ such weights), and then iterating over the next exercise $$$k$$$ after which only these $$$N$$$ weights remain (it can be shown that such a $$$k$$$ does exist, satisfying $$$i \leq k < j$$$: try to prove it!). Then, we have $$$dp_{ij} = \min_k dp_{ik} + dp_{(k+1)j} - 2N$$$, subtracting $$$2N$$$ because we do not need to remove these $$$N$$$ weights after exercise $$$k$$$ or add them before exercise $$$k+1$$$. Our answer is then $$$dp_{1E}.$$$

We can precompute the values of $$$N$$$ for each interval in $$$O(E^2 W)$$$ time, and we can then handle our DP in $$$O(E^3)$$$ time, giving an $$$O(E^2(E+W))$$$ solution, sufficient to pass easily.

A screencast of my third-place finish will be uploaded to my YouTube channel tomorrow.

For problem 3 I managed to pass test 1 using BFS, the node is a state composed of the current exercise I want to do and a string representing the current weights on the machine.

Edges go out like this:

• With the current set of weights do as many exercises as you can (1 edge)

• Remove the topmost weight if the string isn't empty (1 edge)

• Add a new weight (at most 3 edges)

I wonder if anyone solved a problem using Punched Card Python...

Although I get a perfect score in the end, I am still astonished by the speed of the top contestants. How did they finish the contest in just 20 minutes? 20 minutes is just enough for me to finish first problem.

Also, I struggle for the third problem for almost 2 hours. I tried greedy at first, failed and failed again, struggle for an hour, then I found I need divide and conquer with memorization. I can imagine that if first two problems have more difficulty, I will not able to finish third problem. I am wondering if I can pass round 2.

My suggestion for Code jam is that, if you are under 2100, never try the large test set directly except for the very easy problem. Try to brute force and pass small test set first, then you can use your brute force code to get the correct answer for arbitrary small input, and this can help you examine your formal code to avoid unnecessary punishment.

Another suggestion is, learn how to use the test tools to test your code quickly in interactive problems, it is really helpful and can save you a lot of time in the contest. Download both local testing tools and interactive runner, and read the comments of interactive runner carefully, you will now how to test your code.

In problem 2, I reached the observation of powers of 2 quickly. But my main goal was to use the binary representation of the difference and use powers of 2 accordingly, but was stuck at the unused powers (they cannot be known in advance). I eventually found a bit complicated way to accommodate for this but unfortunately ran out of time.

Later, I knew from the editorial how this can be simplified using the observation that any odd number can be constructed using all powers of 2 (by putting some powers with positive signs and others with negative signs), e.g., 0 0 0 0 1 0 0 1 is equivalent to +1 -1 -1 -1 -1 +1 -1 -1.

Orz mon0pole :)

Solved B using Fibonacci numbers instead of powers of 2 ¯\_(ツ)_/¯