a bit of uva : UVa 11157 - Dynamic Frog

Problem Statement:
UVa 11157 - Dynamic Frog

Summary:
Given an integer \(N\) and two sets of numbers (all different), \(S = \{s_1,s_2,\ldots,s_n\}\) (small rocks) and \(B = \{b_1,b_2,\ldots,b_m\}\) (big rocks), we construct 2 sequence from 0 to N and from N to 0 respectively, one ascending and the other descending,  such that each element on S can only be use once, while we can use elements from B twice (one on the ascending sequence, the other on the descending sequence). Amongst all such construction, find the minimum distance between two consecutive element in both sequences.
(Actually the summary seems more confusing haha)

Firstly, notice that we can break the problem into smaller sub-problems since big rocks can be used twice, so essentially we can treat them as two ends. Now the base sub-problem is made up of all small rocks. Here, we need to choose a way to go forward and backward such that each small rocks is only used once, and that the maximum leap we make will be minimum overall (minimax, or the lowest maximum possible, so to say).

Here my intuition was to choose alternate rocks to jump on. I was not convince that this will lead to optimal solution, so I want to prove it. Consider this case where N = 20:
\(S = \{1, 5, 9, 11\}\)
If I choose \(\{1, 9\}\) for the jump forward, the jump backward will be using \(\{5, 11\}\). Smallest distance for jump forward will be minimax of \(\{|0-1|, |1 - 9|, |9 - 20|\}\) while second jump will be the minimax amongst \(\{|0-5|, |5 - 11|, |11 - 20|\}\). If we choose another configuration, that is for the first jump we choose \(\{1,11\}\) instead, the minimax for first jump will increase while the second will decrease, and essentially the minimax for the whole jump will increase. We can do this analysis more formally and extend it to general N cases, but we get the idea.

Implementation:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > small;
vector<int> big;
int N, end;
int main(){
 int TC;
 scanf("%d",&TC);
 for(int T=1;T<=TC;++T){
  printf("Case %d: ",T);
  big.clear();
  small.clear();
  scanf("%d %d",&N,&end);
  big.push_back(0);
  small.push_back(vector<int>());
  int itv = 0;
  for(int i=0;i<N;++i){
   char state;
   int M;
   scanf(" %c-%d", &state, &M);
   if(state == 'B'){
    small.push_back(vector<int>());
    big.push_back(M);
    ++itv;
   } else {
    small[itv].push_back(M);
   }
  }
  big.push_back(end);
  int mleap=-1;
  for(int i=0;i<=itv;++i){
   int sz = small[i].size();
   int temp = -1;
   for(int j=2;j<sz;++j)
     temp = max(small[i][j]-small[i][j-2], temp);
   if(sz <= 1)
    temp = max(big[i+1] - big[i], temp);
   if(sz > 1){
    temp = max(small[i][1] - big[i], temp);
    temp = max(big[i+1] - small[i][sz-2], temp);
   }
   mleap = max(mleap, temp);
  }
  printf("%d\n", mleap);
 }
 return 0;
}