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