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.