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.

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.

Codeforces Round #366 (Div. 1) - B. Ant Man

Problem Statement:
http://codeforces.com/contest/704/problem/B

Summary:
We are given a graph with nodes 1 to n, such that the cost of going from node i to node j is:
1) |x[i] - x[j]| + c[i] + b[j] if j < i
2) |x[i] - x[j]| + d[i] + a[j] if i < j.
Given a start node s and an end node e, find a hamiltonian path from s to e (hamiltonian path: a path that visits all nodes in the graph once) such that the total cost is minimised. (Also, x[i] is monotonically increasing. n <= 5000).

Kalman Filter - Preliminary Study

I am embarking on a project that works with sensors. Sensor readings are noisy, so they need to be filtered. There are many ways to filter a stream of noisy data, and one that I just learnt is called Kalman Filter. A good place to learn about it is: http://www.bzarg.com/p/how-a-kalman-filter-works-in-pictures/. Here I am going to discuss about this technique mostly for my own future reference.

Codeforces Round #253 (Div. 1) - A. Borya and Hanabi [Revisited]

Problem Statement:
http://codeforces.com/contest/442/problem/A

Summary:
A deck of cards, each card has a name (R, G, B, Y, W) and a value (1, 2, 3, 4, 5). Given an array of cards of unknown names and values, we can ask for hints to identify each of the cards. There are two types of hints: name hint or value hint. For example, when we ask a name hint 'R', all cards with name 'R' will be marked. Similarly, a value hint '2' will mark all cards with value '2'. What is the minimum number of hints needed so that we can identify all the cards exactly? (Note that some cards might be duplicated in the array).

Solution:
I have written about this problem previously (https://abitofcs.blogspot.sg/2015/01/codeforces-442a-borya-and-hanabi.html), however after solving this problem once again I learnt that it can be tackled from a different perspective using bitmap.

Codeforces Round #360 (Div. 1) - D. Dividing Kingdom II

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

Summary:
n < 1000 vertices, m = O(n^2) weighted edges (numbered from 1 to m), and q < 1000 queries (L, R) to consider all edges number L to R, group the endpoints of the edges into two groups 0 or 1, and minimize the weight of the edge with the largest weight having its endpoints in the same group.

Codeforces Round #360 (Div. 1) - C. The Values You Can Make

Problem Statement:
http://codeforces.com/contest/687/problem/C

Summary:
n, k <= 500, with n integers c[i] <= 500, output all x such that there exists a subset S of c with sum k, and S has a subset with sum x.