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!