Monday, July 27, 2015

A week before IOI

Codeforces Round 313 has set the tone for an active week after a few very calm ones (problems, results, top 5 on the left). Only TooSimple and qwerty787788 have managed to solve all problems, but the former has picked much better problem solving sequence, and thus won convincingly - great job, and great preparation for the upcoming IOI in Kazakhstan!

TopCoder SRM 663 took place 25 hours later (problems, results, top 5 on the left, my screencast). Subscriber has found two crucial challenges and claimed the victory - great job! Of course, the challenge phase would have much less importance had myself or anybody else managed to solve the hardest problem: we have n binary variables a1,a2,...,an, each initialized randomly, independently and uniformly to 0 or 1. Then, we repeatedly pick two random indices i and j such that i < j, and set overwrite aj with the value of ai. This process will stabilize as soon as all variables have the same value. Before that happens, what's the expected number of times the given sequence of variable values (n numbers, 0 or 1 each, corresponding to the n variables in order) appears?

I've spent an awful lot of time digging in various wrong directions, and with just about 10 minutes to go in the coding phase a good idea came to my mind: simulate the probability of getting each sequence of 0s and 1s for a small value of n after each step. This simulation revealed a very unexpected observation (which can be proved by induction): the probability of seeing any given sequence at any given step depends only on the number of 0s/1s in the sequence, and not on the positions of those 0s and 1s!

Can you figure out the rest? It is relatively easy, but I needed quite some time to finish the implementation after the round - it took me maybe 20 more minutes to get working.

VK Cup 2015 Finals have also happened today, but the results or problems are not available online yet - we can just look at Daria' twitter so far.

Thanks for reading, and check back next week!

Saturday, July 25, 2015

A week when easy is enough

Last week TopCoder Open 2015 Round 2C presented three tricky, if a tiny bit standard, problems (results, top 5 on the left, my screencast, parallel round results). As a result, a fast solution for the easy problem was enough to qualify for the next round, just like in old days :) Of course, a successful challenge together with a not-so-fast solution was also enough. Congratulations to everybody who qualified!

The medium problem has tripped the most competitors, with just 2 correct solutions out of 54 submitted. It went like this: you're placing 8 segments of given lengths into a longer segment of given length one by one in the given order. The smaller segments must lie inside the longer segment, and must not intersect. You can pick any position for a small segment that does not contradict the above rule. When there's no such position, the small segment is not placed into the large segment at all (but if there's at least one possible position, you have to pick one). For each small segment you need to return one of three outcomes:
  • it will definitely be placed into the longer segment irrespective of how previous segments are placed, or
  • it will definitely not be placed into the longer segment, or
  • both situations can occur depending on placement of previous segments.
At first sight, the problem seems straightforward: we probably need to compare some sums of lengths of small segments with the length of the large segment. However, after some more thinking pretty tricky cases come to light: for example, even if some subset of previous segments can fill the large segment completely and thus leave no space for the current segment, it might happen that it's impossible for exactly this subset to appear inside the large segment since we can't skip a segment - we must place it if there's space.

At this point, a solution from the other end of the spectrum comes to mind: what if we try all possibilities of how the small segments are placed, and carefully write down all constraints that appear - i.e., if a segment was not placed, then all gaps currently have strictly smaller length; if a small segment is placed into a gap that is bounded in length, we get two gaps such that their total length is bounded, and so on.

This solution has quite a few different cases to consider, and thus brings a temptation to look for a simpler solution, maybe some invariant that holds or some simple inequalities that we should check.
But it turns out that all (to the best of my knowledge) such simplifications fail, and one simply has to take their time and carefully track the facts about the remaining gaps as we place the segments.

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

Sunday, July 12, 2015

An associative week

TopCoder SRM 662 took place this week (problems, results, top 5 on the left). With just under 600 competitors, this was the lowest attendance for a TopCoder SRM since SRM 307 which happened more than nine years ago. Of course, the starting time at 3am in Europe and 4am in Russia wasn't exactly helpful.

Nevertheless, the problemsetter cgy4ever and the admins have once again prepared very nice problems for everybody to solve. The hardest problem was not solved by anybody: you want to define an associative (but not necessarily commutative or inversible) binary operation on N elements, and have already decided what should be the results of applying the operation when the first argument is some fixed element X and the second argument is any of the N elements. Is there a way to define the rest of the operation to make it associative?

I haven't solved this problem myself yet, so I will try to at least share my approach. Given a formal set of constraints, we should try to see what can we derive from those constraints. Since we know the result of X*Y for all Y, and know that the operation is associative, we can look at (X*X)*Y=X*(X*Y) and learn the result of (X*X)*Y for all Y. In the same manner, we know the result of the operation if the first argument is X*X*...*X. If the data filled so far already leads to a contradiction, or to a non-associativity, then there's no solution. But can you see what should we do if there's no contradiction?

If I were solving this problem myself during the round, I would probably try to add some heuristic to define the remaining elements of the multiplication matrix, then implement a random testcase generator and see where the solution fails, hoping to obtain some more intuition about the problem.

Thanks for reading, and check back next week!

Just a summer week

There were no big international algorithmic competitions last week (the one that ended on 5th of July), so the time seems right for some boring history digging :)

Between my own archives and the data available on the Internet, my earliest programming contest submission available that scored at least some points seems to be the one to problem 1 of the 1997 Russian Olympiad in Informatics.

The problem was: you're given at most 50 "bad" words of length at most 6, consisting of 3 letters each ("I", "N", and "W" - maybe somebody who was judging that olympiad can shed the light about why those three were chosen?), and each bad word has an associated integer penalty. You need to build a word of the given length (at most 100) consisting of the same three letters, so that the total penalty obtained by summing the penalties for all bad words appearing in it as substrings, is minimized. If a bad word appears multiple times, the penalty is counted multiple times, too.

These days, the problem doesn't seem that difficult, although at that time just 4 contestants have managed to solve it in full, the most famous of which is probably Nikolay Durov. His code uses the dynamic programming approach that seems quite obvious now, although for some reason he uses base-4 representation for the last 5 letters instead of base-3 - maybe to avoid dealing with the first few letters separately.

My own solution did an exhaustive search over all possible output strings, and thus scored just 4 points out of 40. Here it is (note the John Dethridge-style indentation :)

const
inpname='input.txt';
outname='output.txt';
MaxM=50;
MaxL=6;
MaxP=100;
MaxN=100;
type
strin=string[MaxL];
wrd=array[1..MaxM]of strin;
pla=array[1..MaxM]of byte;
var
Next:array[char]of char;
z:wrd;p:pla;
t,r:string;
min,m,n:word;
procedure load;
var f:text;i:byte;s,w:string;cnt:integer;
begin
assign(f,inpname);
reset(f);
readln(f,n);
readln(f,m);
for i:=1 to M do begin
readln(f,s);
z[i]:=copy(s,1,pos(' ',s)-1);
delete(s,1,pos(' ',s));
val(s,p[i],cnt);
end;
close(f);
end;
function getpl(gs:string):word;
var i,j,n:byte;pl:word;
begin
pl:=0;
for i:=1 to M do begin
  n:=0;
  for j:=1 to M-length(z[i])+1 do
    if copy(gs,j,length(z[i]))=z[i] then inc(n);
  inc(pl,n*p[i]);
end;
getpl:=pl;
end;
procedure work;
var mm:word;ps:byte;
begin
min:=65535;
fillchar(t[1],M,'I');
t[0]:=chr(m);
repeat
mm:=getpl(t);
if mm<min then begin min:=mm;r:=t; end;
ps:=M+1;
repeat
dec(ps);
if ps=0 then begin t:='';break; end;
t[ps]:=next[t[ps]];
until t[ps]<>'I';
if t='' then break;
until false;
end;
procedure save;
var f:text;
begin
assign(f,outname);
rewrite(f);
writeln(f,min);
writeln(f,r);
close(f);
end;
begin
next['I']:='N';
next['N']:='W';
next['W']:='I';
load;
work;
save;
end.

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

Monday, June 29, 2015

A week with randomized travel

Quite unusually, this week had two Codeforces rounds. The first one, Codeforces Round 309, took place on Wednesday (problems, results, top 5 on the left). Congratulations to ecnerwal for his second Codeforces victory! The scoreboard is a bit unusual, too, as all successful submissions for the top 5 happened within the first hour, highlighting the huge gap in difficulty between problem E and the rest. I haven't solved it myself yet, but the problem statement looks interesting: you're given a graph with 50 vertices and 100 edges, where each edge has a cost and a travel time associated with it, and the travel time is actually a random value: you're given the probabilities that it's equal to 1, 2, .., t (t <= 20000). You need to get from vertex A to vertex B, and if you spend more than t time doing that, you pay an additional constant penalty. How do you minimize the expected payment for getting from A to B?

Codeforces Round 310 happened on Saturday (problems, results, top 5 on the left). The problems were more tractable this time, and the order of solving them played the key role - congratulations to Borys on getting that right and claiming the first place!

Challenge24 finals in Budapest covered both Saturday and Sunday (results, top 5 on the left). There is little information available right now, but the final scoreboard is, and team HoChockiGon is the winner, overtaking the last year's champions PrecisionScrewdrivers in Sunday's morning hours - nice push!

Last week I mentioned the nice problem H2 from the IPSC: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices.

The key idea is: it turns out that the problem is equivalent to finding a subset of vertices with total degree as close to half of the total degree of all vertices as possible! Having made this observation, the rest is very straightforward dynamic programming.

Thanks for reading, and check back next week!

Monday, June 22, 2015

A week with H2

IPSC 2015 was the main event of the week (problems, results, top 5 on the left, analysis). The scoreboard looks suprisingly similar to last year: R+T+J on the top with 35 points (great job!), then HoChockiGon. The Polish team is now closer to the first place, with a 3 point gap instead of 6 points a year ago.

Among the problems my team didn't solve, I'm particularly disappointed not to solve problem H2 which was a very nice "classical" problem: you're given an undirected graph, and need to color its vertices into red and blue in such a way that the total number of edges between the red vertices is as close as possible to the total number of edges between the blue vertices. The solution is very simple and elegant, and after seeing it you don't understand how you could've missed it in the first place :)

TopCoder Open 2015 Round 2B was the other contest this week, with another 40 advancing to the final online selection stage (problems, results, top 5 on the left, parallel round results). One could compete onsite in San Francisco or online, and most fittingly the top 5 are all based in California (how many were actually onsite?). Congratulations to ACRush on continuing the 100% record in TopCoder in 2015, both in algorithm and in marathon!

Finally, let me come back to a problem I mentioned last week: you are given a row of n devices, each consuming some subset of k<=8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on is at least z.

When the left boundary l is fixed, we can use the following dynamic programming: start moving the right boundary r to the right, and maintain the highest possible energy we can obtain from each possible subset of resources in a 2k-element array, spending O(2k) operations on updating the dynamic programming array with a new device, As soon as the highest possible energy for the "all resources" exceeds z, we're done.

Now suppose we've ran this algorithm for some l, and now need to switch to l+1. First, it's easy to see that r will not decrease, so we should be able to just continue our dynamic programming from where we left off, and thus process all data in O(n*2k) time. But we've missed an important step: we also need to somehow "remove" the l-th device from our dynamic programming array, and it's not clear how to do that.

However, if we had to remove the r-th device from the dynamic programming array instead of l-th device, it would be easy: we can just remember the state of the dynamic programming array before we added r-th device, and revert to that. In other words, we know how to work with a stack, but need to work with a queue. And of course, the computer science has the answer: one can emulate a queue using two stacks! Ever wondered if this textbook construction is practical? Well, now you know.

Having two stacks instead of one queue makes checking if we can produce at least z units of power slightly more difficult, but it still takes only O(2k) operations since we need to iterate over all ways to split the set with k elements into two, and the total running time of this solution is thus O(n*2k).

Thanks for reading, and check back next week for the Challenge24 results (a picture from last year from the official website is on the left)!

Monday, June 15, 2015

A 25+25+50+10 week

TopCoder SRM 661 took place very early on Friday after a mostly calm week (problems, results, top 5 on the left, discussion). One of the highlights of the round is the screencast by subscriber where he has also thought aloud and recorded his voice - check it out if you understand Russian! When solving a problem, it's always helpful to discuss it with somebody, and in many cases simply explaining yourself in words helps understand the solution better and improve it - so it might be that intentionally telling the thoughts loudly actually leads to better results! Definitely need to try this out myself.

Yandex.Algorithm 2015 Round 2.2 gave contestants the final chance to get into the top 25 in overall selection results (problems, results, top 5 on the left, overall selection results, discussion). Unlike the previous round, where the best result with at least two blind submissions was 20th place, this one was not so brutal and Jacob Dlougach has appropriately used the time bonus to claim fourth place. Still, places 1-3 and 5-16 have at most one blind submission each, suggesting that this problemset, authored by GlebsHP, also had a lot of tricks. I wonder if the problemsetter for the final round will be revealed in advance - it seems that this can significantly affect the strategy choices.

Google Code Jam 2015 Round 3 has chosen another top 25, this time to fly to Seattle (problems, results, top 5 on the left, discussion). The intersection between this top 25 and the Yandex one is just 7 people: tourist, iwi, vepifanov, dzhulgakov, AngryBacon, ishraq and qwerty787788 - hope I didn't forget anybody - the intersection is small probably due to the difference in competition formats, the task types, and just to the natural randomness.

The problems presented quite different types of challenges, but here's a particularly nice one. You are standing on a line in point 0 and can run at speed v, and there are n quail running away from you, i-th quail at point pi (can be positive or negative) running away at speed vi. What's the smallest time required to catch all quail? n is up to 500.

The two approaches that come to mind for such problems are greedy algorithms and dynamic programming. But it's not clear where would the greedy optimality property come from, and the number of possible states for DP seems exponential - we need to remember which quail we've already caught. Can you see which one of those ideas actually works?

Russian Code Cup 2015 Elimination Round was a bit more generous and chose the top 50 using the 3-hour ACM format (problems in Russian, results, top 5 on the left, discussion in Russian). rng_58 quite succesfully continued working towards his goal of learning Russian by claiming third place in a contest with Russian problem statements only, although most probably translation software has played a part.

The hardest problem was probably the most beautiful, too. You are given a row of n devices, each consuming some subset of 8 different resources when turned on, and producing some amount of energy when turned on. For each l from 1 to n you need to find the smallest r such that it's possible to turn on some devices from the segment [l;r] such that no two devices turned on consume the same resource, and that the total energy of the devices turned on it at least z. Solving this problem for each particular value of l is a relatively straightforward dynamic programming question, but given that n is up to 100000, we can't affort to solve each l separately.

And finally, Google Distributed Code Jam 2015 Online Round brought an entirely new competition format to the best competitors in the world (problems, results, top 5 on the left, discussion). Of course, it might turn out that the best competitors for this new format will be completely different ones - that's why it's so exciting to see how it pans out.

So far, it looks like the competition went well, and there are only two competitors who have qualified both for the regular and for distributed Code Jam: simonlindholm and bmerry, definitely suggesting that the distributed part tests quite different skills. People who participated: do you share this feeling? Was solving these problems similar to more usual contests?

Thanks for reading, and see you next week!