Introduction

In this entry I will show how to use lambda expressions to deal with a fairly common situation that arises in problems. Also this post is specific to C++ 11 and beyond where lambda expressions were introduced to the language.

The Situation

Sometimes in problems it is natural to store inputs in pairs. For example it may be important to keep track of both the size of an element and where it occurs in the input; or when an element has two important attributes. This usually results in a vector of pairs. Next it can be useful to apply an algorithm to this vector of pairs and this where lambda expressions shine.

An Example

For an example problem I will use the codeforces problem The Meeting Place Cannot Be Changed http://codeforces.net/problemset/problem/780/B. The idea of the problem is you have people at n points who each have a maximum speed and who want to meet. You have to figure out the minimum time they can meet. My solution is interesting for three reasons. Firstly and most importantly it uses a lambda expression to sort a vector of pairs. Secondly the approach differs from the editorial approach. Thirdly, the solution passes the system tests but I have a suspicion a specific type of example would cause it to exceed the maximum time limit.

My approach

I started with the basic observation the shortest time any two given people can meet is equal to the distance between them divided by the sum of their max speeds. To keep track of peoples max speeds and positions I stored them as a pair and placed the results in a vector of pairs. Next I concluded that the minimum time all people can meet is the maximum of all the shortest times any two people can meet. Of course at this point I tried to brute force all pairs and exceeded the time limit. To speed up a solution I came up with a way to eliminate some pairs while still getting the same result. To do this I used the basic observation if we have three people p1, p2 and p3 ordered in increasing starting coordinates if p1 is slower than p2 it will take longer for p1 to reach p3 than for p2 to reach p3. This means we can ignore the case of p2 getting to p3 in our calculation. At this point I used a lambda expression to sort the pairs in order of increasing starting points. Then I divided the pairs into two groups. For one group I stored the leftmost pair and all pairs to the right of it that had a lower speed than the leftmost pair. For the other group I stored the rightmost pair and all pairs to the left of it that had a lower speed than the rightmost pair. Next I used the brute force approach from before with pairs where the first element was in one group and the second element in the other. I expected some test to appear where half the elements are in the first group and the other half in the second group resulting in the time limit being exceed. This did not happen and the solution was successful.

Code

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>

using namespace std;
int main(){
    int n;
    cin>>n;
    vector<int> x,v;

    //store positions and speeds
    for(int i=0; i<n; i++){
        int a;
        cin>>a;
        x.push_back(a);
    }
    for(int j=0; j<n; j++){
        int b;
        cin>>b;
        v.push_back(b);
    }
    
    //store positions and speeds together in a vector pair
    vector<pair<int,int>> xv;
    for(int i=0; i<n; i++){
        xv.push_back(make_pair(x[i], v[i]));
    }
    

    //the lambda expression
    sort(xv.begin(), xv.end(), [](pair<int,int> vp, 
    pair<int,int> vp2){return vp.first<vp2.first;});
    
    vector<pair<int,int>> lc,rc;
    

    //splitting into the groups described
    int vm=xv[0].second;
    lc.push_back(xv[0]);
    for(auto p:xv){
        if(p.second<vm){
            vm=p.second;
            lc.push_back(p);
        }
        
    }   


    rc.push_back(xv[n-1]);
    int vm2=xv[n-1].second;
    for(int i=n-2; i>0; i--){
        if(xv[i].second<vm2){
            vm2=xv[i].second;
            rc.push_back(xv[i]);
        }
    }
    
    //brute forcing the groups
    double ans=0;
    for(auto p:lc){
        for(auto p2:rc){
            double d=(double)abs(p.first-p2.first)/(p.second+p2.second);
            ans=max(ans,d);
        }
    }
   
    cout<<setprecision(15)<<ans;
    
    return 0;
}

Final Comments

There are many other approaches to this situation that do not require lambda expressions with pairs. You could create your own class with its own methods or overloaded operators for interacting with STL algorithms. You could define a function, function object or overloaded operator that takes two pairs as arguments and use STL algorithms with these. However, once you understand the syntax for writing simple lambda expressions to use with STL algorithms I think you will find they are the least tedious of all options to code.