A week with 42

On Saturday morning, TopCoder Open 2015 Round 2D gave everybody the last chance to get into the top 40 and advance to Round 3 (problems, results, top 5 on the left, parallel round results). Of course, getting into top 1 is still better than getting into top 40, so congratulations to tomerun on winning this round!

Here are the statistics on Round 3 advancers by country:

Russian Federation - 42: Kankuro, kuniavski, pashka, Endagorion, qwerty787788, 2rf, niyaznigmatul, VArtem, darnley, yeputons, eatmore, SergeiFedorov, Egor, Baz93, Petr, hmich, meshanya,LoRd_TaPaKaH, andrewzta, Belonogov, Jedi_Knight, Burunduk1, ilyakor, mikhailOK, RiaDWaW, homo_sapiens, knightL, Michael_Levin, Um_nik, KalininN, Dlougach, Merkurev, Akhi_Anton,HellKitsune, Zlobober, Enot, UdH-WiNGeR, malcolm734, Shapo, _aid, Nikita.Podguzov, Gassa
Japan - 24: uwi, ir5, hogloid, chokudai, Komaki, anta, snuke, stqn, __math, zerokugi, sky58, kawatea, semiexp, asi1024, Lepton_s, ynasu, j_gui0121, tomerun, tozangezan, LayCurse, sugim48, kusano,DEGwer, wo[]
China - 22: Blue.Mary, xhm1994, Sevenkplus, jiry_2, xyz111, ACRush, cgy4ever, zhj1997, zyxwvu164, nhzp339, liympanda, sky_love_high, OIerRobbin, wenhanhuang, jiangyouno1, Meriones,UESTC_elfness, panjf1987, matthew99a, justever86, Shizhouxing, Hillboy
Ukraine - 10: RAVEman, Vasyl[alphacom], dzhulgakov, K.A.D.R, maksay, Gluk, vlad89, LeBron, sdya, Deretin
United States - 10: pieguy, theycallhimtom, lg5293, iridescent, scott_wu, aceofdiamonds, xiaowuc1, SourSpinach, Gaytrodex, ecnerwal
South Korea - 6: Kriii, ainu7, RRx, kcm1700, sukh1222, xhae
Belarus - 5: tourist, ivan_metelsky, forest, Arterm, subscriber
Poland - 5: Eryx, Psyho, pparys, Marcin_smu, mnbvmar
Croatia - 4: lovro, IvL, Zuza, ikatanic
Taiwan - 3: dreamoon, ShikXD, tmt514
South Africa - 2: bmerry, HiltonLange
United Kingdom - 2: al13n, PaulJefferys
Netherlands - 2: krijgertje, davidv1992
Czech Republic - 2: fhlasek, cibulka
Bulgaria - 3: espr1t, danch0, anrieff
Slovakia - 2: baklazan4247, Xellos0
Latvia - 2: eduardische, Alex_2oo8
Brazil - 2: ffao, rafaelhirama
Hungary - 1: ecsirke
Australia - 1: John Dethridge
Georgia - 1: nika
Finland - 1: Sisu
Switzerland - 1: W4yneb0t
Romania - 1: klamathix
Sweden - 1: Gullesnuffs
Bangladesh - 1: shakilaust
Indonesia - 1: handojo1
Mexico - 1: macs
Norway - 1: Im2Good
Iran - 1: EbTech
Canada - 1: zxqfl
Singapore - 1: eugenesh

Codeforces Round 317 ("AimFund Thanks-Round") took place on Saturday evening (problems, results, top 5 on the left). Subscriber has continued his excellent recent form with another victory - great job!

Problem C was a very nice exercise that involved careful reduction to a graph problem, and the observation that the graph problem in question is actually not difficult at all :) The problem statement was: you're given a boolean expression as an AND of several OR-clauses, where each OR-clause is an OR of several terms, and each term is either a variable, or a negation of a variable, and you need to check if the expression evaluates to true for some variable values. Sounds familiar? Well, the familiar problem is NP-complete, whereas this one had one additional restriction: each variable appears at most twice in the formula (including appearances in negated form).

In order for the formula to evaluate to true, each OR-clause has to evaluate to true, meaning that at least one term in each OR-clause has to evaluate to true. If a variable has just one appearance, or if both its appearances are the same (both negated or both not negated), then we can just set its value to make all OR-clauses containing this variable evaluate to true, and forget about those OR-clauses. In case one of the variables has only one appearance in the remaining OR-clauses, we can also set its value, and so on. After this process ends, we're left with some OR-clauses and variables that appear exactly twice in them, once in normal form, and once in negated form.

Here's where graphs come into play: let's make the OR-clauses the vertices of an undirected graph, and connect two OR-clauses with an edge if they share a variable. The problem now asks: is there a way to pick a direction for each edge in this graph in such a way that every vertex has at least one incoming edge?

Had the original problem been formulated in graph terms, the number of solutions would probably be much higher. The remaining graph problem is not difficult, can you see its solution?

In last week's summary, I've promised to explain the solution to Merlin QA, so let me recall the problem statement first. You are given 100 8-dimensional vectors, and you're adding them in one of 100! possible orders, but with a small twist: every time one of the coordinates of the sum is negative, it becomes zero. Here's a 2-dimensional 2-vector example: if you have vectors (5, -2) and (-3, 1), then adding them in the given order yields (0, 0) -> (5, -2) -> (5, 0) -> (2, 1), while adding them in the reverse order yields (0, 0) -> (-3, 1) -> (0, 1) -> (5, -1) -> (5, 0). Your goal is to pick the order of addition that maximizes the sum of coordinates of the resulting vector.

The key idea is: let's consider a slightly different problem! Instead of making each coordinate equal to zero whenever it becomes negative, let's say that we can change any coordinate to zero at any time.

But is this problem really that much different? It's not hard to see that the answers to those problems will always be the same. On one side, setting coordinates to zero whenever they become negative is included in setting them to zero at any desired time, so the answer to the first problem is less than or equal to the answer to the second problem. On the other hand, if we ever reset a positive coordinate to zero or skip resetting a negative coordinate to zero, the answer will not increase, and thus the answer to the second problem is exactly equal to the answer to the first problem!

The newly formulated equivalent problem is much easier to solve, because there's nothing "conditional" happening. For each vector, its contribution to the answer is equal to the sum of its coordinates that will not be reset to 0 after this vector is added. If we consider the last time each coordinate is reset to 0, and reorder the coordinates in decreasing order of that time, then each vector will always contribute a sum of its first k coordinates for some k. Of course, we should now pick k greedily to maximize the contribution. Since we don't know the last time each coordinate is reset to 0, we should consider all 8! possible permutations of coordinates, and apply the above greedy solution to each of them.

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