Monthly Archives: July 2014

Hackerrank Weekly Challenge #7 // Problem 2: Chocolate in Box

If you want to me write an editorial to problem 3, 4 or 5 from Hackerrank Weekly Challenge #7, let me know in the comment section down below.

Problem statement

The problem is available here.

There are 1 \leq n \leq 10^6 stacks numbered from 1 to n. The i-th stack contains 1 \leq a_i \leq 10^9 objects. Two players are playing the following game with the stacks:

Players takes turns. Player 1 starts. In each turn, the current players can remove any number of objects from any single non-empty stack and he has to remove at least one object. The player who is unable to make a move loses. The task is to decide, how many different moves players 1 can take in the first turn in order to win a game. Both players play optimally.

Solution

If you've hear about the game of Nim, you probably already recognized it here. If not, read about it and remember, because this is one of the most fundamental games in game theory.

The theorem says:

The player making the first move has a winning strategy if and only if XOR of the binary representations of sizes of the stacks is nonzero.

In order to solve the problem, you have to decide, how many ways are to select the stack and take some number of object from it, in such a way, that the XOR of sizes of the remaining stacks equals 0, because then player 2 loses and you win. Let \oplus be the symbol of XOR operation.

The first basic observations is that:

a\oplus b = 0 if and only if a = b.

In order to get the answer for the problem, we have to examine every stacks and add 1 to the result, if we can make a move on this stacks. The fact is that in one move, we can take some objects only from one stack, so the other stacks remain the same. We will examine every stack separately.

Let's assume that we examine the i-th stack and let L = a_1 \oplus a_2 \ldots a_{i-1} \oplus a_{i+1} \ldots a_n - the XOR of sizes of all stacks without stack i. Based on above observation, we are interested in taking some number of a_i objects is such a way, that the number of remaining objects on this stack equals L. Obviously, we can do it if and only if L < a_i , because we have to take at least one object, so we can make the XOR of all stacks equal 0 for any 0 \leq L < a_i.

The time complexity of this solution is O(n). You can compute L for every stacks using prefix/suffix sums for XOR or by "unxoring".

Hackerrank Weekly Challenge #7 // Problem 1: Die Hard 3

If you want to me write an editorial to problem 34 or 5 from Hackerrank Weekly Challenge #7, let me know in the comment section down below.

Problem statement

The problem is available here.

You're given 3 integers 1 \leq a, b, c \leq 10^3, where a and b are capacities of two jugs in some arbitrary unit. You have to decide, if it's possible to fill one of these jugs with exactly c units of water. You'are allowed to take any number of two actions:

  1. Fill any jug with water from the river - there is an unlimited amount of water in the river
  2. Pour some water from one jug to the other.

Solution

This is a famous math puzzle. The theorem says:

The amount of water in each jug is always a linear combination of a and b.

Moreover, you can produce any linear combination of a and b not greater than \max(a, b) using filling and/or pouring.

The second theorem says that an integer n is a linear combinations of a and b if and only if n is a multiple of \gcd(a, b).

If you want to know more about it or see proofs of these theorems, I recommend to read the Chapter 4 from Mathematics for Computer Science - MIT. Obviously the author of the problem was inspired by that book, because the name and the story behind it is the same as in the book.

In order to solve the problem, you only have to compute d: = \gcd(a, b) and check if c is not greater than max(a, b) and c is a multiple of d. If it is, the answer is YES.

Codechef Long // July Challenge - GERALD09 the tiebreaker problem

The June challenge is over. I am very happy, because I finished 19th overall, which is my personal best:

July_challenge_final

While editorials for all problems are available on Codechef forum, almost every solution to the tie breaker problem is unique, so I want to share mine, because it is completely different from the one posted in the official editorial.

Problem statement

The full problem statement is here. You are given a matrix T with n \leq 15 rows and m \leq 15 colums. In addition, you are given an integer k, where 1 \leq k \leq n^2 \cdot m^2. Your task is to fill the matrix with letters from 4-letters alphabet \{A, C, G, T\} in such a way, that the number of different submatrices of matrix T is as close to k as possible - the less the difference is the greater score you have.

Solution

I used the concept of 2 dimensional variant of polynomial hashing in order to count the number of different submatrices in time O(n^2 \cdot m^2). The concept allows to compare any two submatrices in O(1) time.

Lets make some observations:

  1. It is impossible to create a matrix with less than n \cdot m different submatrices, because every 2 submatrices of different size are different. It follows that,if k \leq n \cdot m, the best you can do is to fill the matrix with only one letter, lets cay A.
  2. It is impossible to create a matrix with more than M = n \cdot (n + 1) / 2 \cdot m \cdot (m + 1) / 2 different submatrices, because this is the number of all possible submatrices. It follows that if k \geq M, the best you can do is to return a matrix with n rows and m colums with the maximal number of different submatrices.
    My approach is to precompute for every of 225 pairs (n, m) the matrix with the maximum number of different submatrices. I did that by repeatedly exchanging some random letter in a matrix and if the resulting matrix has a greater number of different submatrices than it had before, then it becomes the resulting matrix. Of course it might not return the best matrix, but if you repeat the exchange many times it should be at least quite close to the optimal matrix. It is worth to mention, that such a a process can stuck in a local maximum, so it is better to choose the result from many different runs.
  3. Since the maximum allowed source file limit on Codechef is 50kb, you can store a lot precomputed information in it. Let R := \{s : n \cdot m < s < M\}. Based on two above cases, we know that k \in R. For every pair of (n, m), I assigned to mem[n][m][s] a matrix of size n \times m with exactly s different submatrices, where s is equally distributed over R. For example, let n, m = 10, then 100 < s < 3025 and we chose to memorize matrices which differ in number of different submatrices by 500, then we compute mem[10][10][s] for s \in \{600, 1100, 1600, 2100, 2600\}. It helps us to chose the initial matrix for the beginning of the on-line computation. For example, if n, m = 10, k = 1220 and we computed mem[10][10] as above, we select mem[10][10][1100] as the initial matrix. I computed mem using the same random method as in Step 2.
  4. Lets fill the matrix with the letter A only and consider, how many different submatrices we can generate by placing letter C in the i-th row and j-th column. If we do that, then every submatrix with the upper left corner in (i_1, j_1) where i_1 \leq i and j_2 \leq j and the lower right corner in (i_2, j_2), where i_2 \geq i and j_2 \geq j is unique, because any other matrix of the same size has either no letter C or has letter C at different relative position. It follows that using that method, we can create a matrix with up to about n^2 / 4 \cdot m^2 / 4 + n \cdot m different submatrices. The natural extension is to insert letters G and T at some positions different than (i, j) in our matrix, which helps us to create a matrix with up to about 3/16 \cdot n^2 \cdot m^2 + n \cdot m different submatrices.

We are ready now for the on-line computation. We choose as the initial matrix the one, which can be generated in any of the above steps with the closest number of different submatrices to k.

My online computation consists of only one technique. For any pair of (n, m), I set the number of computation steps to c \cdot 225 / (n^2 \cdot m^2) for the largest possible c which doesn't exceed the time limit, in which I try to exchange some random elements in the matrix and hope to generate a better one.

At the beginning, I count the number of different submatrices in my initial matrix. Then, for every computations step, I exchange exactly \sqrt{n \cdot m} random elements, again count the number of different submatrices and if it generated a better matrix, I store it as a current matrix.

Conclusion

While the obvious method is to try to exchange on-line some elements in order to achieve a better solution, the crucial step is to set up the initial matrix in the best possible way. I am pretty satisfied with my solution. It results in 20th best score in that problem and gave me 19th place in the contest.

Hackerrank Weekly Challenge #6 // Problem 3

Problem statement

You have to handle n \leq 10^5 customers. The i-th customer arrives at time t_i and the time of handling him is l_i. You are allowed to handle only one customer at the time. The task is to return the average time of waiting for all customers. You have to do it on-line, i.e. when customer arrives, you don't know anything about possible future orders. An interesting fact is when the problem is off-line, then it's NP-complete as discussed here. The full problem statement is here.

Solution

When greedy solution works, go for it.

We'll compute the total time of waiting and divide it by n at the end. First, sort all events by the time of arriving and break ties by the time of handling.

The greedy rule here is the following:

Because the problem is off-line, we know that we have to handle the customer which arrives first without delaying his order. When many, let's say k, customers arrive at the same time, it's better to handle the one with the minimal time of handling, because the time of handling of the first order you handle adds up to the remaining (k -1) customers as a waiting time. While we are handling a customer, new customers may arrive and each of them has to wait until we finish with the current one. As soon as we finish handling the current customer, we have to deal with remaining ones and we can think of them as of customers which arrived in the same time in which we finished with the current one (they've been already waiting from the time they arrived) and we already know how solve it. When there are no waiting customers, then the next one is again the first one which arrives after we deal with previous orders.

The time complexity of that solution is O(n \cdot \log n), because of sorting at the beginning and a priority queue to keep order of waiting customers.

You can look at my code here.