Fixed points

Go to the Jutge statement of the problem

Let S = x_1, \dots, x_n be a sequence of integer numbers such that x_1 < \cdots < x_n.

For every integer number a and every index 1 \leq i \leq n, define f_a(i) = x_i + a. Write a program that, given S and a, tells whether there is some i such that f_a(i) = i.

Input: Input consists of several cases. Every case begins with n, followed by S, followed by a number m, followed by m different integer numbers a_1, \dots, a_m.
Assume 1 \leq n \leq 10^6.

Output: For every case, print its number starting at 1. Afterwards, for every a_j print the position of its fixed point. If no fixed point exists, state so. If there is more than one fixed point, print the smallest one. Print a blank line after the output for every case.

Hint

Look at the sequence given by x_i + a - i, for i=1,\dots, n, and we want to search for the first occurrence of 0 in that sequence (why?). If the sequence was increasing/decreasing then great, dichotomic search! Is it increasing/decreasing? Yes/No, why?

A possible C++ code to start the problem

//Fixed points
#include<iostream>
#include<vector>

using namespace std;

int fixpoint(const vector<int> &v, int left, int right, int a){
  // This procedure should return the smallest fixed point, 
  // -1 if there is no fixed point
  // i.e. the smallest i s.t. v[i] + a == i
  // Would your divide and conquer approach work if v[1] <= v[2] <= v[3] ...?
}

int main(){
    int cnt = 1;
    int n;
    while (cin >> n ){
        vector<int> v(n+1);//Indices start at 1
        for(int i = 1; i <=n; ++i) 
            cin >> v[i];
        int m;
        cin >> m;
        vector<int> a(m);
        for (int i = 0; i < m; ++i) 
            cin >> a[i];
        cout << "Sequence #" << cnt << endl;
        for (int i = 0; i < m; ++i){
            // Call fixpoint(v, 1, n, a[i]); 
            // and format the output accordingly
         }
        cout << endl;
        ++cnt;
    }
}

A possible solution

//Fixed Points
#include<iostream>
#include<vector>

using namespace std;

int fixpoint(const vector<int> &v, int left, int right, int a){
    if (left > right) return -1;
    if (left == right){
        if (v[left] + a == left) return left;
        else return -1;
    }
    int mid = (left+right)/2;
    /*
    Since the ordering on v is strict, for k>0
    v[x-k]<=v[x]-k 
    therefore if v[x] + a < x then
    v[x-k] +a <= v[x] - k +a < x - k 
    hence, x-k cannot be a fixpoint
    */
    if (v[mid] + a < mid) return fixpoint(v, mid+1, right, a);
    else                  return fixpoint(v, left, mid, a);

}

int main(){
    int cnt = 1;
    int n;
    while (cin >> n ){
        vector<int> v(n+1);//Indices start at 1
        for(int i = 1; i <=n; ++i) 
            cin >> v[i];
        int m;
        cin >> m;
        vector<int> a(m);
        for (int i = 0; i < m; ++i) 
            cin >> a[i];
        cout << "Sequence #" << cnt << endl;
        for (int i = 0; i < m; ++i){
            int fp = fixpoint(v, 1, n, a[i]);
            if (fp>=0) cout << "fixed point for "    << a[i] << ": " << fp << endl;
            else       cout << "no fixed point for " << a[i]               << endl;
         }
        cout << endl;
        ++cnt;
    }
}

Other Links