Codeforces Round #238 DIV 2

This round consisted of 5 problems. First and second were rather straightforward. Third one was a little tricky one (feeling happy I could crack this one). I got 96th ranking (I think my best one on CF, this was my 8th contest here) and a jump of +158 in my rating (current 1692)

Let's discuss each of the problems.

1. Gravity Flip

Question is when the gravity direction changes towards right, what are the number of squares in each column. Input is the no of squares in each column when gravity direction is vertical.

This is pretty straightforward problem.You can notice from the figure that the final configuration is the sorted one of the original configuration (sorting based on no  of squares in a column)

So (3,2,1,2) becomes (1,2,2,3) (Refer figure above)

.

If you want a justification, we can see that the last column in final configuration will have maximum squares. After that second maximum will follow and so on. (code)

2. Domino Effect

Given n dominoes and the direction of some of the dominoes in which they are being pushed, calculate the number of dominoes still standing. If dominoes on both sides of a domino are falling on it, it will stand.

The idea is to keep a variable current_count and total_count. Iterate over the dominoes.

1) If the current dominoes is not under any force, increase the current_count. 

2) If we encounter a left force one, either there was a domino under force towards right or not. To know this, we keep a flag and set to true, when we see a right moving domino. If the flag is false, no one among current_count will stand. Set current_count = 0. If flag is true, then if current_count is odd, the middle one will stand as can be seen in figure where the 6th domino stand. In that case increase total_count by 1 and set current_count  to 0. Otherwise we just set current_count to 0 and don't increase total_count. Also set flag to be false.

3)If we encounter right moving domino, set flag to true. Increase total_count by current_count and set current_count to 0;

After we come out of this loop, if current_count is not zero and flag is not true, then add the current_count to total_count and return total_count. (code)

3. Unusual Product

Given a binary square matrix of size n, the unusual square of the matrix is sum of n dot products, where ith dot product is dot product of ith row with ith column. Also unusual square is in modulo 2 space. Dot product and addition is done modulo 2. Now we are given three types of queries. Type 1 query inverts the contents of a row, type 2 query inverts the contents of a column, type 3 query prints the current unusual square.

This type of update and query problems give direction towards using  Binary Indexed Tree, but here I wasn't able to think of a array which I could update and query. So I started with a 3x3 matrix whose elements are Aij.
now unusual square = (A11*A11 + A12*A21 +A13*A31
                              + A21*A12 + A22*A22 + A23*A32
                              + A31*A13 + A32*A23 + A33*A33) modulo 2
We can see that some terms are repeated and will contribute to 0 in modulo 2.
so unusual square =  (A11*A11 + A22*A22 + A33*A33) modulo 2
which can also be written as:
 unusual square =  (A11 + A22 + A33) modulo 2

So we have concluded that unusual square is sum of diagonal elements modulo 2.
Now each query of type 1 and 2 will change exactly one of these diagonal elements. Hence unusual square will alternate between 0 and 1 in each query.

So calculate initial unusual square, then after each query of type 1 and 2, unusual square will change. For type 3, print current unusual square. (code)

4.Toy Sum
Given a subset X of numbers from 1 to s, we have to find a set Y such that the following condition holds.

s is given to be 1000000.

Example: X : 1,4,5

Let's say for each element in X we will find the element in Y for the condition to be true.

(1-1) = 0 = s-s

=> y1 = s

Similarly we get(s, s-3, s-4) as Y.

What if the number we want in Y is already in X. Let's say both 1 and s are in X.

Then (1-1) + (s-1) = s-1 = (s-y1) + (s-y2)

=> y1+y2 = s+1

We can check for any pair of x1,x2 such that x2 = S-(x1-1), y1 + y2 = s + 1

So now we need to find pairs y and s-y-1 both of them are not in X and not used in Y also.

So we count such pairs and after normal allocation ( for x in X add s-(x-1) ), we add the free pairs (y1 + y2 = s+1). (code)

We will discuss the last problem soon.