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 442C - Artem and Array

Problem Statement:
442C - Artem and Array

Solution:
As per normal, greedy problem is difficult to fathom, but always a nice exercise for this lazy mind such as mine.

First and foremost, we should use a random access linked list to solve this problem. You can create a random access linked list by using an array representing the nodes, and use the array indexes to point to each other. So by representing linked list in an array, we can have the best of both worlds (at least for this problem).

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} \).

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 267 Div. 2 Problem E - Alex and Complicated Task

Problem Statement:
467E - Alex and Complicated Task

Solution:
We maintain an array P and a set S, and we consider the elements from left to right:
1. If \(v = a_i\) is not in S yet, add it in and note its index. Hence S will store the index j of the first occurrence of the number \(v\).
2. Else, we set P[i] to index of j of \(v = a_i\) we stored in S.
3. If between P[i] and i there exist P[j] that is less than P[i], then the element P[j], P[i], j, and i forms one desired sequence! Store them and reset S.

Codeforcees Round 283 Div. 2 Problem E - Distributing Parts

Problem Statement:
496E - Distributing Parts

Solution:
This is more for self-reference, I suggest you read the official tutorial on Codeforces for a better discussion on this problem.

This problem is a bipartite matching problem: match smaller "job" segments into bigger container "worker" segments, where each worker segment has certain capacity. If we model each segments as vertices, then we have a graph with \(V\) vertices. This problem cannot be solved efficiently using maxflow algorithm, since V can be very huge, hence there must be some greedy idea behind it. And as I learnt from the editorial, the idea is to consider both jobs and workers in increasing order of their lower bounds. In this iteration, we keep track of a set S of workers that we have encountered, which has the following invariant:
For all i, by the time we reach i-th segment, the lower-bound of this segment is always bigger or equal to any lower bounds of segments in S.

Hence if the i-th segment we are facing is currently a job segment, we just need to find a worker segment in S that has a bigger upper bound than that of the job segment. If there are multiple choices, we must choose the lowest one available. I think this choice can be proven to yield optimal matching by exchange arguments.

If the implementation of S is done by using RB tree, the running time of this algorithm will be \(O(V\lg{V})\).

Topcoder SRM 640 Div. 1 250 - ChristmasTreeDecoration

Problem Statement:
SRM 640 Div. 1 250 - ChristmasTreeDecoration

Solution:
We can employ a greedy scheme:
1. For each possible remaining edge, choose the one that connects two vertices with different colors and that does not result in a loop.
2. If it is not possible anymore to do that, the remaining edges needed to form the tree will all need to connect vertices of the same color.

TopCoder SRM 639

SRM 639 Div. 1 

First Problem:
250 - AliceGame

Solution:
The problem is very mathematical in a sense. First observation: there will always be one winner and one loser in a round. So if we sum up the scores obtained by the two players, we will get the total number of scores accumulated from round 0 to round N consecutively. Hence if the sum of the players score is in the form of \( 2 \sum_{i=0}^{N} {i} - N = N^2 \), for some integer N, then the players have played N rounds, otherwise it is impossible to obtain those scores.

Topcoder SRM 638 Div. 1 Hard - CandleTimer

Follow up to this post

Problem Statement:
Topcoder SRM 638 Div. 1 HARD - CandleTimer

Solution:
Just solved this problem, and I must say that this problem is very challenging (at least for me) in a sense that there are quite a lot of stuff going on. The way the candles are burnt rings some bells to the intuition behind Dijkstra algorithm, and indeed the way to solve this problem is through some modification of Dijkstra.

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 string balancing: SPOJ - ANARC09A

Problem Statement:
SPOJ - ANARC09A

Summary:
Given a string consisting of open and close brackets, find the number of operations needed to balance the brackets. An operation is defined as flipping a bracket. Balanced is in the usual sense: if S,T is balanced, then {}, {S}, ST are all balanced.

Solution:
I used DP approach which is quite expensive in terms of running time and memory, the idea is to keep track of the number of open brackets.
Let S(k, open) be the number of min operations to balance the string
with |open| open brackets by the time we start at k.
Let current bracket be cur. We have several cases:
1. open is 0, and cur = '}', then we have to flip.
   S(k, open) = 1 + S(k+1, open+1)
   open is 0 and cur = '{', then we cannot flip.
   S(k, open) = S(k+1, open+1)

a bit of greedy: SPOJ - CHOCOLA

Problem Statement
SPOJ - CHOCOLA

Solution:
Greedy Algorithm: We choose the highest cost cut each time until no cut is left.
Proof of optimality:
Firstly notice that the number of cuts needed no matter how we do the cutting is C(n,m) = n+m+n*m, and this can be easily proven by induction. So the total number of cuts is always the same. Now the problem asked us to minimize the cost function \(S = a_1 w_1 + a_2 w_2 + \ldots + a_N w_N\) where \(w_i\) is the cost of cutting a certain edge, while \(a_i\) is the corresponding coefficients. The coefficient \(a_i\) is determined by the total number of cuts we done using edge \(w_i\) at the end of the cutting process. Notice that sum of the coefficients are always constant, hence we want to find a distribution of \(a_i\) obtainable such that S is minimum. To do so we claim that by performing cuts on highest cost edge as early as possible, we can reach optimal S. If we encounter several edges having the same cost, we can cut any one of them first, since in the end we will cut them all up as early as possible, hence end up with the same coefficient \(a_i\). The proof goes as follows:
Without loss of generality let \(w_1 \leq w_2 \leq w_3  \leq \ldots \leq w_N\).  Let \(O\) be another optimal cutting of \(S\) that have same coefficients different from that of \(S\). Let \(w_m\) be the highest cost edge such that the coefficient in O does not tally with that of S. This means that \(a_m\) in O will definitely be larger than that of S, since the one in S is the smallest possible \(a_m\) obtainable as we do the cutting as early as possible. Indeed, if \(a_m\) is smaller, then we have 2 cases:
1. Some of \(a_i\) in O before \(a_m\) are bigger or smaller than that of S as the result. Then this contradicts the fact that \(a_m\) is the first to deviate from S.
2. None of \(a_i\) in O is affected by the deviation in \(a_m\). This is only possible if the cut \(w_m\) is independent of the cut made in \(w_i\) before \(w_m\). But that only means that \(a_m\) is already the minimum possible, hence to have a smaller value will be a contradiction.
Hence \(a_m\) must be bigger, and hence there are some \(a_j\) after \(a_m\) in O that are smaller as the result to make up the difference. This difference is over \(w_j\) which are smaller than \(w_m\), hence in the end we will have \(S < O\), a contradiction since O is optimal. Hence S must have been optimal in the first place.

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

/* SPOJ: CHOCOLA
Idea: Greedy Algorithm Stays Ahead
The number of breaks needed is always the same.
#Proof:
C(n,m) = n + m + n*m
C(0,0) = 0 (a single box choclate needs 0 cut)
Cut horizontally:
C(n,m) = 1 + C(a,m) + C(b,m) such that a+b+1 = n
C(n,m) = 1 + a+m+a*m + b+m+b*m
       = 1 + (n-1) + 2*m + (n-1)*m
       = n + m + n*m   :)
equally for vertical cut
#
Observation: the problem is similar to weight distribution problem
Observation: each cut will happen sooner or later
Observation: the "weight" of a cut is non decreasing
Observation: if a vertical and horizontal cost are equal, cutting 
order does not matter. Proof?
So we greedily choose the largest cut-cost each time
*/

int x[1003], y[1003];

int main(){
    int tc;
    cin >> tc;
    while(tc--){
        int m,n;
        cin >> m >> n;
        for(int i=1;i<m;++i){
            cin >> x[i];
        }
        for(int i=1;i<n;++i){
            cin >> y[i];
        }
        int h = 1,v=1;
        sort(x+1,x+m);
        reverse(x+1,x+m);
        sort(y+1,y+n);
        reverse(y+1,y+n);
        int i=1,j=1;
        int ans = 0;
        while(i<m && j<n){
            if(x[i] > y[j]){
                ans += x[i]*v;
                ++h;
                ++i;
            } else {
                ans += y[j]*h;
                ++v;
                ++j;
            }
        }
        if(i<m){
            int sum = 0;
            while(i<m){
                sum += x[i];
                ++i;
            }
            ans += sum*v;
        } else {
            int sum = 0;
            while(j<n){
                sum += y[j];
                ++j;
            }
            ans += sum*h;
        }
        cout << ans << endl;
    }
    return 0;
}

a bit of greedy: UVa 10670 - Work Reduction

Problem Statement:
UVa 10670 - Work Reduction

Summary:
We want to transform an integer N into integer M. Then we are given 2 operations:
1. \( N \mapsto N-1\), with cost \(A\)
2. \( N \mapsto \frac{N}{2} \) (round down), with cost \(B\)
What is the lowest cost?

Solution:
Naturally there is a greedy scheme to follow:
1. If we can divide by 2, take \(min \{ A \lceil \frac{N}{2} \rceil, B \} \)
2. If cannot, use operation 1 for the remaining steps

Proof?

I was exploring on the maths for a bit, for the case \(N = 2^k\) and \(2^{k-2} < M < 2^{k-1}\), I get this results...

Suppose we do a few operation 1 (\(x\) times) and then do operation 2. We will end up with \(2^k \mapsto 2^k-x \mapsto \lfloor \frac{2^k-x}{2} \rfloor\). Meanwhile, if we follow greedy scheme, we have \(2^k \mapsto 2^{k-1}\) instead.  I will call the former "deviation" from greedy scheme. Then I observe that greedy scheme actually stays ahead of the deviation. If I take \(  \lfloor \frac{2^k-x}{2} \rfloor \) as the "rendezvous" point, we have 2 costs:
By deviation: \(C' = xA + min \{ A \lceil \frac{2^k-x}{2} \rceil, B \} \)
By greedy scheme: \(C = min \{ 2^{k-1}A, B \} + x'A\)  where \(2^{k-1}-x' = \lfloor \frac{2^k-x}{2} \rfloor \)
Now, if \(x\) even, we have \(x' = \frac{x}{2}\), while when \(x\) is odd, we have \(x' = \frac{x+1}{2}\). Hence we can say \(x' \geq \frac{x}{2}\), and also \(x \geq x' \) for all \(x \geq 1\).
We have to check the following cases:

Case 1: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A > B\)
Then \( C' = xA + B \geq x'A + B = C \). Hence greedy scheme is at least equal, and at best cost less than the deviation.

Case 2: if \( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A > B\)
\(C' = xA + \lceil \frac{2^k-x}{2} \rceil A = xA + (2^k - x - 2^{k-1}+x')A\)
\(C' = x'A + A2^{k-1} > x'A + B = C\) again!

Case 3: if \( A \lceil \frac{2^k-x}{2} \rceil > B \) and \(2^{k-1}A < B\)
This is impossible by the love of God

Case 4: if\( A \lceil \frac{2^k-x}{2} \rceil < B \) and \(2^{k-1}A < B\)
then C = C' by simple algebra.

Yay then I can say that the greedy scheme actually stays ahead once there is a deviation from the scheme as we can always reach the state at at worst equal cost to the one resulting from the deviation :D

But for the case in general.. no idea yet

Now.. that's why people always ponder upon the paradox of why such a simple greedy algorithm can actually be so complicated.. A facade of all facades

a bit of greedy: UVa 100249 - The Grand Dinner

Problem Statement:
UVa 100249 - The Grand Dinner

Summary:
Given several groups of people, each group consisting of several people, and given several tables of varying capacities, is it possible to place everyone in the tables such that people from the same group are not seated in the same table? If so, print out the possible arrangement.

Solution:
Apparently the problem is solvable by modeling it as some kind of matching problem and by finding the max-flow on the matching graph. However, apparently also, the problem can be solved using a greedy strategy by first sorting the groups in order of size, as well as the table in order of capacity, and start trying to assign each person in the group starting from the largest group down the sorted order of tables. Haven't thought of a proof yet...

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

/* First IDEA:
sort by no of ppl, sort by table
for each group, go through table in sorted order assign what is available
if possible, print arragement, otherwise no arrangement is possible
proof: dunno yet
*/

vector<pair<int,int> > ppl, tbl;
int pp[73] /*, tt[53]*/;
int ppp[73][103], ttt[73];
int main(){
    int N,M;
    while( cin >> M >> N ){
        if(N+M==0) break;
        ppl.clear();
        tbl.clear();
        for(int i=0;i<M;++i){
            int u;
            cin >> u;
            ppl.push_back(make_pair(u,i));
        }
        for(int i=0;i<N;++i){
            int u;
            cin >> u;
            tbl.push_back(make_pair(u,i));
        }
        sort(ppl.begin(), ppl.end());
        sort(tbl.begin(), tbl.end());
        reverse(ppl.begin(), ppl.end());
        reverse(tbl.begin(), tbl.end());
        for(int i=0;i<M;++i){
            pp[ppl[i].second] = i;
        }
        for(int i=0;i<N;++i){
            //tt[tbl[i].second] = i;
            ttt[i] = tbl[i].first;
        }
        bool ok = true;
        for(int i=0;i<M;++i){
            int sz = ppl[i].first;
            int k = 0;
            for(int j=0;j<sz;++j){
                bool found = false;
                for(;k<N;++k){
                    if(ttt[k] > 0){
                        found = true;
                        ppp[i][j] = tbl[k].second;
                        --ttt[k];
                        break;
                    }
                }
                if(!found){
                    ok = false;
                    break;
                }
                ++k;
            }
            if(!ok) break;
        }
        if(!ok) printf("0\n");
        else {
            printf("1\n");
            for(int i=0;i<M;++i){
                int sz = ppl[pp[i]].first;
                for(int j=0;j<sz;++j){
                    if(j != 0) printf(" ");
                    printf("%d", ppp[pp[i]][j]+1);
                }
                printf("\n");
            }
        }
    }
    return 0;
}

a bit of greedy: UVa 10037 - Bridge

Problem Statement
UVa 10037 - Bridge

Summary:
(A very famous puzzle actually) \(N\) people trying to cross the bridge with one flashlight. Only groups with at most \(2\) people can cross the bridge, and a group has to carry flashlight in order to cross. Each person has a speed, which is the time needed for him to cross the bridge. Furthermore, the time needed for a group to cross the bridge is as fast as the slowest person in that group. Find the minimum time needed to cross everyone off to the other side.

Solution:
There is a greedy "intuition" (or is it? :( ) as follows:

/* 
Suggested Greedy algo: Incremental construction:
The idea is to always bring the first and second slowest to the other side
with the help of the first and second fastest 
say the fastests are A<B
and the slowest are X>Y
then we have 2 cases:
1. M = (A,X) + (A,0) + (A,Y) + (A,0)
   M = 2*A + X + Y
2. M' = (A,B) + (A,0) + (X,Y) + (B,0)
   M' = 2*B + A + X
And incrementally choosing the minimum of M and M' at each step.
Proof? I dont know
*/

The proof to the intuition is somewhat more elaborate, by representing the problem as a graph problem.

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

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 srm: Minimizing Absolute Values - SRM 629 Div II 550

Problem Statement:

Given \( M = \sum^{n}_{i=1} |a_ix - b_i| \), find \(x\) that minimizes \(M\).

The solution to the problem hinges on the following lemma:

Lemma 1:

If \(x\) minimizes M, then \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \). 

Proof:

The proof comes from an observation that the curve for M is made up of segments of straight lines with sharp turns on each \(x \in \{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \} \). Why? Let's assume without losing generality that \(\{ \frac{b_1}{a_1}, \frac{b_2}{a_2}, \ldots , \frac{b_n}{a_n} \}\) is sorted in increasing order. Each \( (\frac{b_k}{a_k}, \frac{b_{k+1}}{a_{k+1}}) \) forms a segment on the real number line, and \(x\) can only be one of the segment at any point of time. In any segment, each \(a_ix - b_i\) will be either positive or negative and the parity will not change as long as \(x\) stays in the same segment. This means that in each segment, \(M = Ax - B\), which is a straight line. From here it is clear that if \(x\) minimizes M, it cannot be in the middle of the line segment, since moving along the downward slope will gives us even smaller M. Hence \(x\) must be on the segment ends, and hence leads to Lemma 1.

From here, we can perform a \(O(N^2)\) complete search to find \(x\).

a bit of uva : UVa 11157 - Dynamic Frog

Problem Statement:
UVa 11157 - Dynamic Frog

Summary:
Given an integer \(N\) and two sets of numbers (all different), \(S = \{s_1,s_2,\ldots,s_n\}\) (small rocks) and \(B = \{b_1,b_2,\ldots,b_m\}\) (big rocks), we construct 2 sequence from 0 to N and from N to 0 respectively, one ascending and the other descending,  such that each element on S can only be use once, while we can use elements from B twice (one on the ascending sequence, the other on the descending sequence). Amongst all such construction, find the minimum distance between two consecutive element in both sequences.
(Actually the summary seems more confusing haha)

Firstly, notice that we can break the problem into smaller sub-problems since big rocks can be used twice, so essentially we can treat them as two ends. Now the base sub-problem is made up of all small rocks. Here, we need to choose a way to go forward and backward such that each small rocks is only used once, and that the maximum leap we make will be minimum overall (minimax, or the lowest maximum possible, so to say).

Here my intuition was to choose alternate rocks to jump on. I was not convince that this will lead to optimal solution, so I want to prove it. Consider this case where N = 20:
\(S = \{1, 5, 9, 11\}\)
If I choose \(\{1, 9\}\) for the jump forward, the jump backward will be using \(\{5, 11\}\). Smallest distance for jump forward will be minimax of \(\{|0-1|, |1 - 9|, |9 - 20|\}\) while second jump will be the minimax amongst \(\{|0-5|, |5 - 11|, |11 - 20|\}\). If we choose another configuration, that is for the first jump we choose \(\{1,11\}\) instead, the minimax for first jump will increase while the second will decrease, and essentially the minimax for the whole jump will increase. We can do this analysis more formally and extend it to general N cases, but we get the idea.

Implementation:

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int> > small;
vector<int> big;
int N, end;
int main(){
 int TC;
 scanf("%d",&TC);
 for(int T=1;T<=TC;++T){
  printf("Case %d: ",T);
  big.clear();
  small.clear();
  scanf("%d %d",&N,&end);
  big.push_back(0);
  small.push_back(vector<int>());
  int itv = 0;
  for(int i=0;i<N;++i){
   char state;
   int M;
   scanf(" %c-%d", &state, &M);
   if(state == 'B'){
    small.push_back(vector<int>());
    big.push_back(M);
    ++itv;
   } else {
    small[itv].push_back(M);
   }
  }
  big.push_back(end);
  int mleap=-1;
  for(int i=0;i<=itv;++i){
   int sz = small[i].size();
   int temp = -1;
   for(int j=2;j<sz;++j)
     temp = max(small[i][j]-small[i][j-2], temp);
   if(sz <= 1)
    temp = max(big[i+1] - big[i], temp);
   if(sz > 1){
    temp = max(small[i][1] - big[i], temp);
    temp = max(big[i+1] - small[i][sz-2], temp);
   }
   mleap = max(mleap, temp);
  }
  printf("%d\n", mleap);
 }
 return 0;
}

a bit of bitmask : UVa 10718 - Bit Mask

So today I learn a new bitwise manipulation technique :D

Problem Statement:
UVa 10718 - Bit Mask

Summary
For \(N, M, U, L\) such that \(L \leq M \leq U\), find minimum \(M\) such that \(M\) OR \(N\) is maximum (where OR refers to bitwise OR operation).

This problem requires a strategy to switch on bits on M (starting from all 0 bit) such that we only switch on a bit on M when we absolutely need to, but we must also ensure that M can fall between L and U.

Strategy:
For i-th bit of N starting from the leftmost bit:
1. If the i-th bit of N is ON, the best case scenario is we do not need to turn on the i-th bit of M. That is, if by letting the i-th bit of M off, we can still have M in between L and U, we will do so. Otherwise, the i-th bit of M must be on.
2. Else, if the i-th bit of N is OFF, the best case to maximize M OR N is by switching the i-th bit of M to ON. However, if the resulting M is higher than U, we must switch the i-th bit of M to OFF instead.

As such, the resulting M will be in between L and U.

For example, when N = 101101, L = 011010, U = 011110

i = 5:
leftmost bit of N is ON, hence M should be off, and indeed the resulting M can still fall between L and U.
i = 4:
bit of N is OFF, hence we would like to turn it on. The resulting M = 01**** can still be less than U, i.e the lowest M = 010000 is indeed less than U, so we can do so.
i = 3:
bit of N is ON, hence we want that bit on M to be OFF. but M = 010*** will always be less than L, i.e the highest possible M = 010111 is not lower than L, hence we must have that bit to be switched ON, i.e M = 011***
i = 2:
bit of N is ON, and we want M to be OFF. M = 0110** can still be in between L and U, i.e. the highest possible M = 011011 is not lower than L.
i = 1:
bit of N is OFF. If we switch that bit of M on, M = 01101* can still be less than U.
i = 0:
the rightmost bit is ON, so we want that bit on M OFF, and we have our minimum M such that M OR N is maximum.

Here is the code:

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

typedef long long ll;

int main(){
 ll N,U,L,ans;
 while(scanf("%lld %lld %lld",&N,&L,&U)!=EOF){
  ans = 0;
  for(int i=0;i<=32;++i){
   ll state = (N & (1L<<(32-i)));
   //printf("%lld\n", state);
   //printf("%lld\n", ans);
   if(state){
    //if the bit is set
    //if not setting this bit can still fulfill the constraint
    ll temp = state -1;
    temp |= ans;
    if(temp < L){
     ans |= state;
    }
   } else {
    //if not set, should set if fulfill constraint
    ll temp = ans;
    temp |= (1L<<(32-i));
    if(temp <= U){
     ans = temp;
    }
   }
  }
  printf("%lld\n",ans);
 }
 return 0;
}