Sunday, August 17, 2014

a bit of uva: UVa 10125 - Sumsets

Problem Statement:
UVa 10125 - Sumsets

Given a set \(S\) of distinct integers, find the largest \(d\) such that \(a + b + c = d\) where \(a,b,c,d\) are all distinct elements in S.

Simple brute force approach will give an \(O(N^4)\) complexity, which is bad since \(|S|\) can be as large as 1000 in this problem. Therefore the problem begs for a more efficient approach, and indeed an \(O(N^2\lg{N})\) solution exist, and we need to utilize binary search to achieve this running time.

Firstly, notice that the problem can be restated as finding \(a,b,c,d\) that satisfy \(a+b = d - c\). This simple restatement of the problem has a huge implication: we can find all possible values of \(a+b\) in \(O(N^2)\) time, similarly for \(d-c\), hence total we need \(O(N^2)\) to generate all \(a+b\) and all \(d-c\), which can be stored in two arrays or vectors, say \(P\) and \(Q\) respectively. Next, we sort \(P\) and \(Q\). Why sorting? so that we can do a binary search! From here on the task is simple; we need to try all elements in \(P\) and find whether there exist an element with the same value in \(Q\). If there is, then check whether they have distinct \(a,b,c,d\), and if so we update our answer on \(d\).

Each binary search has time complexity of \(O(\lg{N^2})\), which happen \(N^2\) times, so we have running time of \(O(N^2\lg{N})\) over all. Beautiful isn't it.