Tuesday, April 15, 2008 Match summary
This match attracted 1280 competitors, 721 Div2 (78 newcomers) and 559 Div1. Div2 problem set turned out to be the easier one for Div2 coders. They faced easier Hard problem that was worth 900 points. Many of them (even 88 competitiors) solved correctly all three tasks. Div1 coders faced very easy 250 points problem and almost all of them solved it correctly, however, due to minor bugs some red coders (extarget) like gawry and ahyangyi failed on this problem, but thanks to their excellent coding skills their rating increased. Many coders showed that they are familiar with Div1 Medium kind of problems. Some of them took it as easier and had to resubmit their solution to avoid Failed system tests. Many coders trapped with Div1 Hard and lot of early submited solutions failed. In Div1 wywcgs first submitted Hard problem, but it came out as incorrect. After solving Medium problem ardiankp, tomekkulczynski and PaulJefferys took lead. Match is going on and submissions of Hard problem change things  PaulJefferys, nigulh, Vasyl[alphacom] (become almost a target) and Rizvanov_de_xXx took lead, but one of them had 1K problem incorrect solution. PaulJefferys showed great performance and thanks to 4 successful challenges won the match with over 200 points margin and became target. nigulh took second place, followed by Petr who resubmited 1K problem, but earned 125 points in challenge phase and took third place. Even with third place, Petr's rating decreased  amazing, isn't? Because the problems in Div2 weren't hard, we've got very fast solutions for each of them. Thanks to 2 successful challenges dlwjdans won the match. Although newcomer ILoveWangYeMore finished challenge phase with 50 points, he won second place, followed by gpascale who was on third place. The ProblemsMinDifferenceUsed as: Division Two  Level One:
Although this is very simple problem, it can be solved in several ways. First approach Simple checking for the minimum over all pairs will work in Second approach SinceO(n^2) solution could be "very slow" on some platforms, it would be very nice if we can come up
with faster one.
Lets look at the element A[i] and divide other elements into two groups:
A[i] . Similarly, over all elements from the seconds group the minimal one will produce
the minimal difference with A[i] . Actually, instead of comparing A[i] to all elements
from the list, we should compare it to only two elements. After this conclusion, it is obvious that sorting
the list A is key to the solution. In sorted list, each element should be compared with its
left and right neighbour. Implementation in Java of this approach:
Time complexity of this algorithm is Third approach Let's go on and find even faster solution, the one that depends onM and for
the maximal n and M is faster than Second approach.
Note that if each element (except
A[0] = A0 ) of the list is calculated by modulo M then it must fail
between 0 and M1 , inclusive.
So, we have at most M+1 different numbers that are in the
range 0 .. Max(M1, A0) . According
to the constraints, any number is between 0 and 10000, inclusive. Let's make an array flag of 10001
booleans (0 .. 10000) and mark flag[i] = true if i appears in the list.
If flag[i] was already set on true return 0. Else, go through the array flag
and calculate difference between two neighbour elements that are set on true and return the minimal
difference. Time complexity of the algorithm is O(Max(M, A0) + n) .
Implementation in Java of this approach:
Exercise
Used as: Division Two  Level Two: Used as: Division One  Level One:
This task is pretty straighforward. It doesn't involve any special knowledge. Almost each bruteforce solution
would pass. One way to solve the task is first to generate all possible positions for
For a short and fast iterative solution take a look at vlad89's
solution here.
Exercise
Used as: Division Two  Level Three:
This task was a greedy one. The key to the solutions was to check all possible positions of
You can take a look at delicato's solution
here.Time complexity of described algorithm is O(maxlen^2*n) , where n is number
of puzzle words. With simple precalculating time complexity can be reduced to O(maxlen*n) .
Let c be i th letter of matchString . For each position j ,
0<=j<matchWords[i].length() , calc the last occurence of the letter c
in the first j letters of matchWords[i] . With this information, instead
to each time calculate where is the last occurence of some letter, you can get the answer
in constant time. As reference you can take a look at my solution in the practice room.
Exercise
Used as: Division One  Level Two:
This is modification of wellknown dynamic programming problem. Let special field
It seems that some memoization solutions for this problem was too slow, so be careful. Also, solution will probably timeout if at each step for some field you check whether it is special field or not. It is better to cacl that information once and store somewhere. This algorithm gives time and space complexity n^4 .
For clean and fast solution you can take a look at ainu7's solution
here.
Exercise
Used as: Division One  Level Three:
This problem can be divided into four parts. First two parts contain proofs that number of friends for each kid
(used as array
Let's sum all J_i
This is part where we check if return could be "IMPOSSIBLE"  SSF must be
divisible by n2 . Let's go on and transform J_i :J_i: S  sumFriends[i] = f[i] + f[(i+k)%n]  let C[i] be S  sumFriends[i] We know S and we know sumFriends[i] , so we know f[i]+f[(i+k)%n] .
Now we should check that f[i]+f[(i+k)%n] >= 0 holds for every i .Second part Suppose that (i+p*k)%n=(i+q*k)%n and 0<=p<=q<n/GCD(n, k) .
Lets transform that into (q*kp*k)%n=((qp)*k)%n=0 . We have two options 1. q  p = 0 => q = p 2. (q  p)*k = r*LCM(n, k) = r*k*n / GCD(n, k) => (qp) = r*n / GCD(n, k) , but
0 <= p < q < n/GCD(n, k) , so this option is impossible.We proved that in case above p = q  call it Proof 1.Define Seq_i as list: i, (i+k)%n, (i+2*k)%n, ..., (i+m*k)%n ; where (i+m*k)%n is
first index that already exists in Seq_i for some (i+r*k)%n , r < m . Such
r must exists because Seq_i is finite. It is also true that
m <= n/GCD(n, k) .
Let's proove that m = n/GCD(n, k) .m = n/GCD(n, k) is the highest value of m , because i=(i+k*n/GCD(n, k))%n .Suppose m<n/GCD(n, k) and there exists some p such that
(i+p*k)%n=(i+m*k)%n, 0<=p<m , but according to the Proof 1 it is impossible, so
m=n/GCD(n, k) => (i+m*k)%n=i .That means indexes of each Seq_i form a cycle and all Seq have the same length 
the length n/GCD(n, k) . For each Seq_i and Seq_j we should proove that
either Seq_i is same as Seq_j or they don't have common elements. Although it
is very obvious, let's make short proof.Suppose that Seq_i: i, (i+k)%n, (i+2*k)%n, ..., (i+c1*k)%n,..., (i+m*k)%n Seq_j: j, (j+k)%n, (j+2*k)%n, ..., (j+c2*k)%n,..., (j+m*k)%n and (j+c2*k)%n = (i+c1*k)%n . But that means ((ji)+(c2c1)*k)%n = 0 . Because
Seq_j is cyclic we can always choose such j that c1 = c2 and then we
have (ji)%n=0, 0<=i,j<(n1) => i=j .We can conclude that number of different lists Seq is equal to
n/(n/GCD(n, k))=GCD(n, k) and each list has odd number of elements (n is an odd number, so
n/GCD(n, k) is an odd number, too).Third part In order to make it easier for reading and understanding, let gr=n/GCD(n, k)1 .Consider particular list Seq_i that actually represents independent system of equations.
From the first part we can write:
Sum left and right sides:J_((i+k*gr)%n)  J_i + J_((i+k)%n)  J_((i+2*k)%n) + J_((i+3*k)%n)  ... + J_(i+k*(gr1)) = Now we can calculate f[(i+k*gr)%n] , then f[(i+k*(gr1))%n] , ..., and finally
f[i] . If we do this for all Seq s, we will get all f[i] .We can take this way of suming in order to get f[i] because number of equations in the system is odd. In case
it is even the sum will be 0.At each part you are dividing something, check whether it is possible to divide and get integer without reminder as the result. Also check whether number of friends of some kid is nonnegative number and less than number of all kids. If these conditions are not satisfied, return "IMPOSSIBLE". NOTE: All three parts could be replaced by Gaussian elimination. However, in this case we should guess that the solution is unique. Forth part When we get f[i] , each kid can be represented as vertex and there will be edge between two kids
iff those kids are friends. So, the question becomes: "If you are given degrees of all vertices in the graph,
return whether such graph exists."To give the answer, we can use HavelHakimi algorithm. Here is short description of the algorithm:
You can take a look at fero's solution
here which seems very clear.
Exercise

