UVa 434 - Matty's Blocks

Problem Statement:
UVa 434 - Matty's Blocks

Summary:
This problem pertains to a matrix of size K x K, where each entry is a non-negative integer.
Let the maximum values on each row be max_row[0 .. K-1], and the maximum values on each column be max_col[0 .. K - 1].

E.g.          
[ 1 4 2 5 3 ]  --> 5
[ 8 1 7 6 0 ]  --> 8
[ 3 3 4 1 5 ]  --> 5  max_row
[ 6 5 0 3 2 ]  --> 6
[ 2 4 1 6 6 ]  --> 6
  v v v v v
  8 5 7 6 5
  max_col

Our job is to fill in the matrix to fulfil those requirements. In general there are more than one way to do it. Compute:
1. Minimum sum of entries possible.
2. Maximum sum of entries possible.

Note that no constraint is placed on K in the original problem statement. It can be small, it can be very large.

Codeforces Round #360 (Div. 1) - D. Dividing Kingdom II

Problem Statement:
http://codeforces.com/contest/687/problem/D

Summary:
n < 1000 vertices, m = O(n^2) weighted edges (numbered from 1 to m), and q < 1000 queries (L, R) to consider all edges number L to R, group the endpoints of the edges into two groups 0 or 1, and minimize the weight of the edge with the largest weight having its endpoints in the same group.

Codeforces Codeforces Round #359 (Div. 1) - D. Kay and Eternity

Problem Statement:
http://codeforces.com/contest/685/problem/D

Summary:
In an infinite 2D array, there are n < 10^5 cells (x[i], y[i]) with value 1, where -1e9 <= x[i], y[i] <= 1e9. The rest of the cells are 0. For each m = 1 to n, compute the number of squares with dimension k x k (k <= 300), with the property that each of those squares has exactly m non-zero cells in it.

Codeforces 678F - Lena and Queries

Problem Statement:
http://codeforces.com/contest/678/problem/F

Summary:
There are n <= 300000 queries of the form: add lines ax+b, remove line ax+b, and the maximum intersection between vertical line x = q and all lines.

a bit of cf: Codeforces Round #274 (Div. 1)

Problem A:
480A. Exams

Solution:
Sort \( (a_i, b_i) \) pairs and go through the sorted pairs from top to bottom, greedily determining the smallest possible time for each exam.

Problem B:
480B. Long Jumps

Solution:
This problem is actually asking us to perform binary search multiple times. First we check whether there is \(a_i, a_j\) such that their difference is \(x\), which can be performed in \(O(N\lg{N})\) time using binary search. We do the same for \(y\), and then we have 3 cases:
1. If both \(x\) and \(y\) can be measured using the current ruler than output 0
2. We have only 1 of them measurable, then output 1 and the length that is not yet measurable.
3. None of \(x\) and \(y\) is measurable. Here we need to check whether we can just place 1 additional mark such that \(x\) and \(y\) are both measurable as a result. To do this, we form two lists: first list consists of all marks that is formed by adding each existing mark with x, and by subtracting each existing mark with x, while the second list is similarly formed but using y as the offset. Then we check if there is any identical element in both lists. To do this in \(O(N\lg{N})\) time, we sort each list, then for each element in the first list, we try to find the same element in the second list using binary search. If such element can be found, it means that we just need to add one additional marker with value equal to this element. Otherwise, we fallback to the worst case scenario which is to add two markers of value x and y.
While the approach is straightforward conceptually, the implementation is very error prone... (at least to me :( )

a bit of dp: SPOJ - BABTWR

Problem Statement:
SPOJ - BABTWR

Summary:
Given N (N<30) types of 3D boxes with dimension x,y,z, find the maximum height of tower can be formed by stacking those boxes together with the condition:
1. each type of box can be used as many times as possible
2. if a box is stacked on top of another, its baselines must be smaller than the one below.

Solution:
Rather than building the boxes one by one, we make use of the property that the boxes can be arranged in sorted order. Hence once we derived a suitable order of boxes that can be exploited, we perform a procedure similar to one in LIS to find the maximum height possible.

/* Idea:
Bottom Up: sort all boxes and possible orientations in terms of width and height.
WLOG width < height, hence comparison can be done between widths and heights exclusively.
Then do checks similar to LIS
*/

vector<pair<pair<int,int>,int> > stack;
int box[33][3];
int dp[99];
int N;

int main(){
    while(cin >> N, N!=0){
        stack.clear();
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                cin >> box[i][j];
            }
        }
        for(int i=0;i<N;++i){
            for(int j=0;j<3;++j){
                int a = box[i][j];
                int b = box[i][(j+1)%3];
                int c = box[i][(j+2)%3];
                if(a>b) swap(a,b);
                stack.push_back(make_pair(make_pair(a,b),c));
            }
        }
        sort(stack.begin(), stack.end());
        dp[0] = stack[0].second;
        int ans = 0;
        for(int i=1;i<3*N;++i){
            int h = stack[i].first.first;
            int w = stack[i].first.second;
            dp[i] = 0;
            for(int j=i-1;j>=0;--j){
                int ch = stack[j].first.first;
                int cw = stack[j].first.second;
                if(ch < h && cw < w) dp[i] = max(dp[i], dp[j]);
            }
            dp[i] += stack[i].second;
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

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;
}