Thursday, June 1, 2017

Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Problem Statement:
Codeforces Round #416 (Div. 2) C. Vladik and Memorable Trip

Summary:
An integer array A of size n <= 5000 has entries which ranges from 1 to 5000. We pick disjoint segments of the array such that for each segment S:
1. If i in S, then any j s.t. a[j] == a[i] must also be in S
2. The score of S is computed as the XOR of its elements
Goal is to maximise the sum of scores of the chosen segments.

Solution:
I like this problem. This is solvable using a dynamic programming approach.

Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags

Problem Statement:
Codeforces Round #416 (Div. 2) E. Vladik and Entertaining Flags
Summary:
Given an integer matrix with size m x n with m <= 10, n <= 10^5, find the number of connected components in segment [l, r] of the matrix (i.e. rectangle (0, l) -> (m-1, r)). Two cells belong to the same connected component if they are adjacent (share the same edge) and have the same value.
There are q <= 10^5 such queries.

Solution:
A cool problem which can be solved using Segment Tree. This is made possible by the following observation: Consider two adjacent segments [l, m] and [m+1, r]. If we know the number of components on each segment, then we can iterate along the cells where the two segments meet to see if we can combine any adjacent components.

Sunday, May 28, 2017

Codeforces Round #415 (Div. 2) E. Find a car [or Div. 1 C]

Problem Statement:
Codeforces Round #415 (Div. 2) E. Find a car

Paraphrase:
An integer matrix M is defined as:
M[i][j] = the minimum integer x >= 1 such that:
- M[i][k] != x for all k < j
- M[k][j] != x for all k < i

Example:
1 2 3 4
2 1 4 3
3 4 1 2
4 3 2 1

Goal: Given a rectangular block in M {(x1, y1), (x2, y2)} and an integer K, compute the sum of elements in that rectangle, but exclude elements whose value is larger than K.


Thursday, March 16, 2017

UVa 434 - Matty's Blocks

Problem Statement:
UVa 434 - Matty's Blocks

Summary:
This problem pertains to a matrix of size K x K, where each entry is a non-negative integer.
Let the maximum values on each row be max_row[0 .. K-1], and the maximum values on each column be max_col[0 .. K - 1].

E.g.          
[ 1 4 2 5 3 ]  --> 5
[ 8 1 7 6 0 ]  --> 8
[ 3 3 4 1 5 ]  --> 5  max_row
[ 6 5 0 3 2 ]  --> 6
[ 2 4 1 6 6 ]  --> 6
  v v v v v
  8 5 7 6 5
  max_col

Our job is to fill in the matrix to fulfil those requirements. In general there are more than one way to do it. Compute:
1. Minimum sum of entries possible.
2. Maximum sum of entries possible.

Note that no constraint is placed on K in the original problem statement. It can be small, it can be very large.


Monday, February 27, 2017

a bit of algo: LZW Compression

LZW compression is a magic show. I am left awe-struck as the algorithm compresses and uncompresses bits of data. The magic is not in the fact that it does compress the data, no, that's the boring part. The magic is in the simplicity and elegance of it.

Compression
Given a string "bananababa", the algorithm starts with a code table. We initialize the code table with the following entries:

0 - a
1 - b
2 - n

This is called the initial code table.

LZW then iterates through the letters in the string while also updating the code table. The algorithm is simply:

buffer := empty;
for c in str:
    if buffer + c is in code_table:
        buffer := buffer + c;
    else:
        output code_table[buffer];
        add (next_index_number++, buffer + c) into code_table;
        buffer := c;
output code_table[buffer];

That's it! So with our example "bananababa", we get:


Wednesday, August 24, 2016

Codeforces Round #365 (Div. 2) - E. Mishka and Divisors

Problem Statement:
http://codeforces.com/contest/703/problem/E

Summary:
Given an array of n <= 1000 integers a[i] <= 10^12, and an integer k <= 10^12. Find subset of the array which product of the elements is divisible by k, such that the size of the subset is minimised. If more than one such subsets exist, return the one with smallest sum over the elements.

Monday, August 22, 2016

Codeforces Round #365 (Div. 2) - D. Mishka and Interesting sum

Problem Statement:
http://codeforces.com/contest/703/problem/D

Summary:
Given array a[i] for N <= 10^6 integers, and M <= 10^6 queries (L, R): collect all integers in a[L..R] that occur even number of times, and compute their XOR. E.g. for a = {1, 2, 2, 3, 4, 4}, query (2, 7) returns 2 XOR 4 = 6. If no such element in a particular query, return 0.