Codeforces Round #359 (Div. 1) - C. Optimal Point

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

Summary:
Find the minimum point M (x, y, z) in Z^3 such that the maximum Manhattan distance between M and a set of points {(x[i], y[i], z[i]) in Z^3} of size <= 100000 is the minimum. Manhattan distance between two points (x, y, z) and (a, b, c) is defined as |x-a| + |y-b| + |z-c|. Furthermore, x, y and z is in [-10^18, 10^18].

Codeforces 455E - Function

Problem Statement:
http://codeforces.com/contest/455/problem/E

Summary:
Given a function f(i, j) = min (f(i-1, j), f(i-1, j-1)) + a[j], where f(1, j) = a[j], and m queries (m <= 10^5) in the form (i, j), compute f(i, j) of each queries.

Codeforces 536A - Tavas and Karafs

Problem Statement:
536A - Tavas and Karafs


Solution (from the official editorial, which is more succinctly written. I'm placing it here for my self reference.):
Given a sequence \(s_i\), we are only allowed to perform m-operation: choose at most m numbers in the sequence and decrease them by 1. Then it is provable that by performing at most t m-operation, we can reduce all \(s_i\) to 0, if and only if \( \max s_i \leq t\) and \( \sum_i s_i \leq tm \).
Proof:
Forward direction: if we can reduce all \(s_i\) using t operations, then it is clear that the biggest \(s_i\) must not exceed t, and that the total sum of \(s_i\) will not be more than \(mt\). The interesting part is to prove that this conditions are sufficient.

Codeforces Round 296 Div. 1 B / Div. 2 D - Clique Problem

Problem Statement:
528B - Clique Problem

Solution:
This problem is brilliantly crafted. I really enjoy solving this problem, as the ideas are really natural.

Firstly, we notice that we can sort the vertices by its x coordinates, and we hope that some nice property can be established. Indeed,  suppose v[i] = (x[i], w[i]) is an array of vertices in sorted order with respect to x, then let C[i] be the maximum size of a clique that can be formed by choosing amongst v[1], v[2], to v[i], with the added constraint that v[i] must be included in C[i]. Then we claim that:
C[i] = max (C[j] + 1) where j is less than i.
Why is this true? Consider a clique C[j] for which we have:
|x[i] - x[j]| = x[i] - x[j] \(\geq \) w[i] + w[j].

Codeforces Round #294 Div. 2 Problem C - A and B and Team Training

Problem Statement:
519C - A and B Team Training

Solution:
Nice problem, in fact the problems for this round are good stuff.

Let's express the groups as tuples (1, 2) and (2, 1), in the form of (number_of_experts, number_of_newbies). We have the following constraints :
\( a (1, 2) + b (2, 1) \leq (n, m) \)
where a and b denotes the number of groups of the respective arrangements. We want to maximize \(X = a+b \), and we can search for the maximum possible X using binary search. Rewrite the constraints in term of X and a, we have \( 2X - a \leq n\) and \( a + X \leq m \). Additionally, a must be non negative and cannot be bigger than X.

Codeforces Round #291 Div. 2 D - R2D2 and Droid Army

Problem Statement:
514D - R2D2 and Droid Army


Solution:
The problem statement is a bit hard to understand, but other than that the problem is excellent. I love the idea of combining binary search with segment tree / Fenwick tree!

The strategy is as follows: We want to know, for each i-th droid, what is the longest segment [j, i] possible such that we can kill all j-th to i-th droid using at most k shots (of course j \(\leq \) i). To find j, we can use binary search on [0, i] droids. If we need more than k shots to kill all droids in [j,i], we must increase j, since any choices of j less than the current j will also need more than k shots. Otherwise, if we need at most k shots to kill droids in [j,i], we can decrease j, since any choices of j bigger than the current j will also need at most k shots. What an awesome property.

Codeforces Rockethon 2015 Problem F1 - Scaygerboss

Problem Statement:
513F1 - Scaygerboss

Solution:
Happy to solve another maximum flow problem :) The official editorial to this problem is well-written so check them out if you have not. Here I will discuss on the approach for the easier version of the problem only, as that is the max my brain can currently comprehend :D

Every maximum flow problems are interesting, and this one further reinforces that statement. Here we are to match the males and females into a cell for which each cell can be associated with at most a pair of matching. We are to find the minimum possible time for all the males and females can move to their designated cells, amongst all possible matching. Here we can use binary search to guess the minimum value, and check whether that value can result in a valid matching using maximum flow.

Codeforces Round #286 (Div.1 C / Div.2 E) - Mr. Kitayuta vs. Bamboos

Problem Statement:
506C - Mr. Kitayuta vs. Bamboos

Solution:
A very nice problem, another problem that I would never solve if not for the official tutorial :D The official tutorial is very well-written, so you should check them out! Kudos for the problem setter and the writer for the editorial! Only read this if you are still stuck :P This post is more for my self-referential note.

Since there is no easy way to construct an instance of the solution with a global minimum, one should think, is it easier if we guess the answer instead? Hence we turn ourselves to binary search. Let's assume we have a value X, we have a nice property on the search space: if it is possible to hit the bamboos such that at the end of M day all the bamboos are at most of height X, then all bigger X will be feasible, hence we want to find smaller X. Otherwise, if X is not feasible, then all smaller X will not be feasible too, hence in this case we want to find bigger X instead. This forms the basis of the binary search.

Codeforces Round: Goodbye 2014

A really nice set of problems :) Well done for the problem setters!
Have just solved problem A to E, loved them so far. Haven't tried F and G yet.

EDIT: just found out that the official tutorial has been released, and it looks really good!

Problem A 
Problem Statement:
500A - New Year Transportation

Solution:
Wow, a pretty intimidating problem A!

The idea is very straight forward, since \(a_i\) is actually a representation of a directed edge connecting vertex \(i\) with \(i+a_i\). Simply run a DFS from node 1 and return YES if we reached the destination node.

Codeforces Round 271 Div. 2 Problem E - Pillars

Problem Statement:
474E - Pillars

Solution:
This problem has a very interesting use of segment tree in combination with DP. The DP idea is very standard: let f[i] be the maximum length of jumps using pillars from [1..i], ending at i. Then f[i] = max of f[j] + 1, for all j such that \(|h_i-h_j| \geq d\). Then what's left is to find an efficient way to find those j that satisfies the requirement, and at the same time, find the maximum f[j] amongst all such j. This is where the segment tree comes in.

Codeforces Round #283 Div. 2 Problem D - Tennis Game

Problem Statement:
496D - Tennis Game

Solution:
Another problem where harmonic series comes into the picture! Just realized on how to solve this problem after the contest finished :P

Firstly build 2 arrays of cumulative scores of both players. Then we try every possible t from 1 to N:
1. We search for all positions in which the set ends using binary search several times. At any junction, if we cannot find the desired cumulative scores in which a set can end, it means that t is not valid.
2. Keep track on the scores of of the player, and who scored the last point.
3. t is valid iff the scores are not equal, and the last player who scored the last point is also the one who have higher score.

TopCoder SRM 641 Div. 1 250 - TrianglesContainOrigin

Problem Statement:
SRM 641 Div. 1 250 - TrianglesContainOrigin

Solution:
A pretty error prone computational geometry problem. The idea is actually quite simple, but the implementation can be quite tedious. Since no three points can form a collinear line, we can draw a line to each point P from the origin O and deterministically define that point by the angle defined by the line and the x-axis (that means the vector OP and the unit normal vector i of x-axis). Once we have converted every points as these angles and sort them, we can make use of another observation: if we choose two points with corresponding angles alpha and beta, then to form a triangle that contains the origin, we need to choose those points with angles between (alpha + 180, beta + 180). Otherwise, any triangle formed using points beyond these region will not contain the origin. This means that we can use binary search to find the number of points lying in the desired region. Overall we will have a \(O(N^2 \lg{N})\) running time complexity.

Codeforces Round #277.5 Div. 2 - Problem E Hiking

For complete discussion to this round: link to discussion

Problem Statement:
E. Hiking

Solution:
Very interesting problem, with a very interesting solution. It requires us to realize that we can binary search the best ratio (surprise!). Now, suppose that we are given a ratio R. How do we know whether this ratio can be fulfilled? Is there a way such that our path will lead to a ratio less than or equal to R?

The relationship between R, the total picturesqueness P and the total frustration F by the time we get to point i is:
\(\frac{F}{P} \leq R\), or \(F \leq P*R\).
The important thing here is we want to maximize the "lax" \(P*R - F\) by the time we get to camp i, which is the remaining values or margin before the ratio overshoot \(R\). Hence, by the time we get to the last camp, we will end up with the maximum margin possible, and if this margin is a positive value, we can conclude that there exist a path such that the ratio between F and P is less than R. Otherwise, R cannot be satisfied.

Codeforces Round 275 (Div. 2)

Problem A:
483A - Counterexample

Lots of ways to find a counterexample, easiest is to give 3 consecutive numbers starting with an even number.

Problem B:
483B - Friends and Presents

This problem is solvable using binary search. First notice that the number of elements in [1 .. v] that is divisible by a prime p is \( \lfloor \frac{v}{p} \rfloor \), and the number of elements divisible by both p and q is \( \lfloor \frac{v}{pq} \rfloor \). We are not interested in those which are divisible by both, since we can't give it to either person. Hence we can group the elements in [1 .. v] into 3 categories: those which are divisible by p only, those divisible by p only, and those not divisible by either p or q (or both). We can give all that is divisible by q to the first person, and give the ones divisible by p to the second person. Then what remains is to check whether we can distribute the rest which are not divisible by p or q such that it satisfies them both. If so, we can search for a lower value v, otherwise we have to increase v.

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 cf: Codeforces Round #273 (Div. 2)

Problem B:
478B. Random Teams

Summary:
Divide N people into M groups, each group has at least one person. Find the minimum and maximum total number of pairing of people in the same group amongst all groupings.

Solution:
Haven't prove this yet:
Maximum is when M-1 groups have one person, and the last group has N-M+1 person.
Minimum is when M groups have equal number of people (or as evenly distributed as possible).

a bit of dp: SPOJ - RENT

Problem Statement:
SPOJ - RENT

Summary:
Given st[i] starting time, d[i] duration and p[i] price, find maximum total price possible from an optimal non-overlapping intervals.
\(N\leq 10000\) and \(st, d \leq 10^6\)

Solution:
This problem requires a DP technique coupled with Binary Search. We need to sort all intervals and start our construction from the last interval. Firstly, we mark dp[N] by 0. Then for each \(k = N-1, N-2 \ldots 0 \) we have the following relationship:
dp[k] = max(dp[k+1], dp[ index_of(st[k] + d[k]) ] + p[k])
Where index_of is a function which returns the index i of smallest st[i] such that st[i]  \(\geq \) st[k] + d[k] (i.e. the starting time of the closest non-overlapping interval). Implementation of index_of is naturally done by using a binary search. Hence overall we have a \(O(N\lg{N})\) running time algorithm.

a bit of codeforces: Round #268 (Div. 1) Problem B

Problem B:
468B - Two Sets

Summary:
Partition \(N\leq 10^5\) numbers into \(A\) and \(B\) such that if \(x \in A\) then \(a - x \in A\) and if \(x \in B\) then \(b-x \in B\) for two given constant \(a,b\).

Solution:
The numbers occur in pairs, and as such we can model the problem as a graph problem. Let's say that the partitioning is done by coloring the node with \(A\) or \(B\). We have two kinds of edge from each number \(x\) (as the vertex): an A-edge that connects \(a\) and \(x-a\), and/or a B-edge that connects \(b\) and \(x-b\). We can build this adjacency information in \(O(N\lg{N})\) time using binary search. Now to check whether we can color a node \(x\) with a color \(c\).
The color the nodes connected to \(x\) must have the same color as \(x\), since if it does not, then it can be quite easily shown that such coloring will lead to contradictory conclusions. Hence to complete the coloring, we have the following cases:
Case \(c = A\). (Case \(c=B\) is analogous)
1. node \(x\) does not have A-edge: then it is not possible to color the node with \(A\).
2. node \(x\) has an A-edge: then we continue this check recursively on the node \(a\), and the node \(b\) if it has one.
If the connected component satisfies this constraint, then we can color those nodes with color \(c\). Such checking will take \(O(N)\) time.

Implementation:

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

int adj[100003][2];
int N, A, B;
vector<pair<int,int> > m;
vector<int> mm, pp;
int mark[100003];

bool check(int par, int u, int col){
    //printf("%d %d %d\n", par,u,col);
    mark[u] = col;
    int v = adj[u][0];
    int w = adj[u][1];
    bool ret = true;
    if(adj[u][col] == -1) return false;
    if(v != -1 && v != par) ret &= check(u, v, col);
    if(w != -1 && w != par) ret &= check(u, w, col);
    return ret;
}
    

int main(){
    cin >> N >> A >> B;
    m.clear();
    mm = vector<int>(N+3);
    pp = vector<int>(N+3);
    for(int i=0;i<N;++i){
        int u;
        cin >> u;
        m.push_back(make_pair(u, i));
    }
    sort(m.begin(), m.end());
    for(int i=0;i<N;++i){
        mm[i] = m[i].first;
        pp[m[i].second] = i;
        mark[i] = -1;
        adj[i][0] = adj[i][1] = -1;
    }
    bool ok = true;
    for(int i=0;i<N;++i){
        int lo = i, hi = N-1, mid;
        int u = A-mm[i];
        int v = B-mm[i];
        bool found = false;
        if(adj[i][0] != -1 || adj[i][1] != -1) found = true;
        while(lo <= hi){
            mid = (lo+hi)/2;
            if(mm[mid] < u){
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        if(mm[lo] == u){
            adj[i][0] = lo;
            adj[lo][0] = i;
            found = true;
        }
        lo = i, hi = N-1;
        while(lo <= hi){
            mid = (lo+hi)/2;
            if(mm[mid] < v){
                lo = mid+1;
            } else {
                hi = mid-1;
            }
        }
        if(mm[lo] == v){
            adj[i][1] = lo;
            adj[lo][1] = i;
            found = true;
        }
        if(!found){
            ok = false;
            break;
        }
    }
    /*
    for(int i=0;i<N;++i){
        printf("%d %d %d\n", i, adj[i][0], adj[i][1]);
    }
    */
    if(!ok) printf("NO\n");
    else {
        for(int i=0;i<N;++i){
            if(mark[i] != -1) continue;
            bool ch = check(-1, i, 0);
            if(ch) continue;
            ch = check(-1, i, 1);
            if(!ch){
                ok = false;
                break;
            }
        }
        if(!ok) printf("NO\n");
        else {
            printf("YES\n");
            for(int i=0;i<N;++i){
                if(i!=0) printf(" ");
                printf("%d", mark[pp[i]]);
            }
            printf("\n");
        }
    }
    return 0;
}
    

a bit of codeforces: Round #211 (Div. 2)

Mostly a note to myself, since the solution to the problems below require greedy approach which I am still unable to fully prove.

Problem C
C. Fixing Typos

Summary:
Given a string, and a property "typo" iff:
1. there exists a sequence of consecutive letters of the same alphabet of length more than 2
2. there exists 2 couples which are back to back (where a "couple" is two consecutive letters of the same alphabet)
Produce a string without the property "typo" by removing as little letters as possible.

Greedy approach:
1. If there are typos of type 1, then reduce them to sequences with length 2.
2. Scan the string for type 2, and sequentially eliminate a letter from the second couple.

Implementation can be done by creating a finite state machine:

/* PROBLEM C FIXING TYPOS
 * Requires greedy algorithm
 * First idea: do incremental building of string, and simulate a finite state machine
 * Idea of proof: greedy algo stay ahead
 * 3 cases:
 * 1. aax..  -> if addition form a couple, eliminate, until state escaped
 * 2. aa.. -> if a added, delete. else go to 1
 * 3. ..
 */

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

int main(){
    string str;
    string ans = string();
    cin >> str;
    int state = 0;
    int sz = str.size();
    char prev = str[0];
    ans += prev;
    for(int i=1;i<sz;++i){
        if(str[i] == prev){
            if(state == 0){
                state = 1;
                ans += str[i];
            }
        } else {
            if(state == 1){
                state = 2;
            } else if(state == 2){
                state = 0;
            }
            ans += str[i];
            prev = str[i];
        }
    }
    cout << ans << endl;
    return 0;
}

Problem D
D. Renting Bikes

Summary:
Given n boys, m bikes, b[1 .. n] of personal budgets, p[1 .. m] of prices of each bikes, and a value a of shared budget. Furthermore, each boy cannot buy more than one bike, and personal budget can only used individually. Find k the maximum number of boys who can own a bike, and state the minimum total personal budget needed to pay for k bikes.

Solution:
Binary search on k (wow) since we have a nice property: if we can pay for k bikes, then we definitely can pay for any number of bikes less than k, so we just need to test for bigger k, and vice versa. That means we have to do this \( O(\lg{N}) \) times, and each time we need to check whether k is possible. To do this we have a greedy approach that runs in \(O(N)\). But beforehand we need to sort b[i] and p[i] first. Greedy approach:
Define a variable spend which record the amount of personal budget spent, and a variable cur which record the remaining current shared budget. The richest k boys will pay for the cheapest k bikes. Now we iterate through the boys starting from the poorest rich kid (haha) amongst all those k boys. We assign the bikes in the corresponding order to the boys, such that the poorest kid pays for the cheapest bike and the richest kid pays for the most expensive one. Now we check one by one: for each boy, if the boy has a personal budget bigger than the price of the bike, let him pay the whole price of the bike, otherwise use the remaining shared budget. If we can reach the last person, then we can buy k bikes. Now, we are left with spend and cur, and naturally spend is the maximum personal budget needed to pay for k bikes, while cur will contain the unused shared budget at the end. Hence we can find minimum personal budget by just subtracting spend with cur.

Implementation:

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

/* PROBLEM D RENTING BIKES
 * Binary Search and Greedy Algorithm
 * to check what is the maximum number of boys, use binary search
 */

int n,m,a;
int b[100005];
int p[100005];


int main(){
    cin >> n >> m >> a;
    for(int i=0;i<n;++i){
        cin >> b[i];
    }
    for(int i=0;i<m;++i){
        cin >> p[i];
    }
    sort(b, b+n);
    sort(p, p+m);
    int hi = min(m,n), lo = 0, mid;
    int ans=0, ms=0;
    while(lo <= hi){
        mid = (lo+hi)/2;
        int cur = a;
        int tmp = 0;
        bool ok = true;
        int j = n-mid;
        for(int i=0;i<mid;++i){
            if(b[j] >= p[i]){
                tmp += p[i];
            } else if(b[j] < p[i]){
                tmp += b[j];
                cur -= p[i] - b[j];
                if(cur < 0) {
                    ok = false;
                    break;
                }
            }
            ++j;
        }
        if(ok){
            ans = mid;
            ms = tmp - cur;
            if(ms < 0) ms = 0;
            lo = mid+1;
        } else {
            hi = mid-1;
        }
    }
    cout << ans << " " << ms << endl;
    return 0;
}

a bit of codeforces: Multiplication Table (Interesting Binary Search)

Problem Statement:
448 D - Multiplication Table

Summary:
Given a table of dimension M x N, where \(1 \leq M,N \leq 10^5\), and with the property that cell \(i,j\) contains \(i*j\), find the \(k\)-th largest element in the table.

We can certainly generate all \(i*j\) and store them inside a vector, and simply iterate through to the \(k\)-th element (\(O(N^2)\)), but that will take forever when \(M,N\) are large. Furthermore, we actually can perform a very cool binary search to find the k-th element! Firstly, notice that if we are given a number \(S\), we can find its rank in \(O(N)\) time by simply checking on each row how many cells are less than or equal to \(S\) (we will actually end up with the largest rank of \(S\) if \(S\) occurs several times on the table). After obtaining the rank, we can check whether it is less than or bigger than \(k\), and we perform a corresponding binary search until we end up with the correct value of S. The approach is therefore \(O(N\lg{N})\) which is fast enough for the time limit.