Friday, June 20, 2014

a bit of topcoder: SRM 625 Div II 500

Problem Statement:
Incrementing Sequence

Summary:
Given a set of numbers $$S$$ of size $$N$$, and an integer $$k$$, determine whether we can transform $$S$$ to set containing integer $$1$$ to $$N$$ by adding multiples of $$k$$ to element of $$S$$.

I've just figured out how to solve this problem (and it is really just too late) but well, practice makes perfect :D

The idea is that if we sort $$S$$, we need to check the following conditions hold:
1. The last element of $$S$$ (which is the maximum element) must not exceed $$N$$
2. If $$S$$ can be transformed into $${1,2,\ldots,N}$$, that means there is an element $$a_i$$ in $$N$$ such that addition of $$k$$ to $$a_i$$ equals to $$N$$. In other words, $$a_i \equiv N \bmod{k}$$.

A greedy algorithm which picks the largest element in $$S$$ which satisfies the above conditions allows us to carry out such transformation:

string canItBeDone(int k, vector<int> A) {
sort(A.begin(),A.end());
while(!A.empty()){
int N=A.size();
if(A[N-1]>N)return "IMPOSSIBLE";
int j=N-1;
while((A[j]-N)%k!=0) {
--j;
if (j==-1) return "IMPOSSIBLE";
}
A.erase(A.begin()+j);
}
return "POSSIBLE";
}
This algorithm takes roughly $$O(N^2)$$ depending on the data structure used.