Codeforces 442B - Andrey and Problem

Problem Statement:
442B - Andrey and Problem

Solution:
An interesting mathematical problem. The official editorial to this problem is excellent, so this post is more for my self reference.

First of all find a neat representation of the function we are going to optimize:
Let \(K = \{ p_1, p_2, \ldots, p_k \} \) be the probabilities of friends chosen, then the probability of having one problem is:
\(F = p_1(1-p_2)(1-p_3)\ldots (1-p_k) + (1-p_1)p_2(1-p_3)\ldots (1-p_k) + \ldots \)
       \(+ (1-p_1)(1-p_2)(1-p_3)\ldots p_k\),
which can be simplified as
\(F = (1-p_1)(1-p_2)\ldots (1-p_k) \{ \sum_{i=1}^{k} \frac{p_i}{1-p_i}  \} \)
Let \(P = (1-p_1)(1-p_2)\ldots (1-p_k)\) and \(S =  \sum_{i=1}^{k} \frac{p_i}{1-p_i} \).

SPOJ - Nested Dolls (MDOLLS)

Problem Statement:
SPOJ - Nested Dolls (MDOLLS)

Summary:
Given a list of dolls with width[i] and height[i] such that doll[i] can be nested inside doll[j] if width[i] < width[j] and height[i] < height[j]. Find the number of minimum resulting nested dolls possible.

Solution:
It is a very interesting (and difficult) problem. I thought it was something to do with longest increasing subsequence (by the way the problem is phrased haha) but actually formally this problem is that of bipartite matching, and there is a greedy approach to solve this problem based on the following observations:

a bit of greedy: UVa 10026 - Shoemaker's Problem

Problem Statement:
UVa 10026 - Shoemaker's Problem

Summary:
Given a list of jobs, we can only work on one job each day. Each job \(i\) takes \(t_i\) days to complete and for each day of not starting on the job, we must pay \(s_i\) fine. Once we start on a job, we will finish it before starting the next job. We are to find the best permutation/arrangement of the jobs that minimizes the total fine incurred.

Solution:
A great application of exchange argument that establishes the relationship that must hold in an optimal arrangement amongst all permutation. This optimization problem reduces to sorting problem.

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

/* 
The correct greedy algo and its proof: sort by fine/time
Proof:
s is fine, t is days
Suppose that (s_1,t_1), (s_2,t_2), ..., (s_n,t_n) is the optimal
arrangement such that the total fine is the lowest. Hence we have
O = s_1 (0) + s_2 (t_1) + s_3 (t_1 + t_2) + ...
    + s_i (t_1 + t_2 + ... + t_{i-1})
    + s_{i+1} (t_1 + t_2 + ... + t_{i-1} + t_i) 
    + ...
Since O is optimal, by exchange argument, if we exchange the position of
s_i,t_i and s_{i+1},t_{i+1}, we will have total fine O' which will cannot be lower
than O:
O' = ... + s_{i+1} (t_1 + t_2 + ... + t_{i-1})
         + s_i (t_1 + t_2 + ... + t_{i-1} + t_{i+1})
         + ...
         
hence 
    O' - O >= 0 
        <=> s_{i+1} (-t_i) + s_i (t_{i+1}) >= 0
        <=> s_i/t_i >= s_{i+1}/t_{i+1}

Hence in the optimal arrangement, s_i comes before s_{i+1} iff s_i/t_i >= s_{i+1}/t_{i+1}
*/

vector<int> arr, s, t;

bool comp(const int& L, const int& R){
    if(s[L] * t[R] == s[R] * t[L]) return L < R;
    return s[L] * t[R] < s[R] * t[L];
}

int main(){
    int TC;
    cin >> TC;
    bool flag = false;
    while(TC--){
        if(flag) printf("\n");
        flag = true;
        int N;
        cin >> N;
        arr.clear();
        s.clear();
        t.clear();
        for(int i=0;i<N;++i){
            int u,v;
            cin >> u >> v;
            s.push_back(u);
            t.push_back(v);
            arr.push_back(i);
        }
        sort(arr.begin(), arr.end(), comp);
        for(int i=0;i<N;++i){
            if(i != 0) printf(" ");
            printf("%d", arr[i]+1);
        }
        printf("\n");
    }
    return 0;
}