Cow Contest [Neal Wu, 2007]

N (1 <= N <= 100) cows, conveniently numbered 1..N, are participating in a programming contest. As we all know, some cows code better than others. Each cow has a certain constant skill rating that is unique among the competitors.

The contest is conducted in several head-to-head rounds, each between two cows. If cow A has a greater skill level than cow B (1 <= A <= N; 1 <= B <= N; A != B), then cow A will always beat cow B.

Farmer John is trying to rank the cows by skill level. Given a list the results of M (1 <= M <= 4,500) two-cow rounds, determine the number of cows whose ranks can be precisely determined from the results. It is guaranteed that the results of the rounds will not be contradictory.

INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..M+1: Each line contains two space-separated integers that  describe the competitors and results (the first integer, A, is the winner) of a single round of competition: A and B

SAMPLE INPUT (file contest.in):

5 5
4 3
4 2
3 2
1 2
2 5


OUTPUT FORMAT:

* Line 1: A single integer representing the number of cows whose ranks
        can be determined

SAMPLE OUTPUT (file contest.out):

2

OUTPUT DETAILS:

Cow 2 loses to cows 1, 3, and 4. Thus, cow 2 is no better than any of the cows 1, 3, and 4. Cow 5 loses to cow 2, so cow 2 is better than cow 5.  Thus, cow 2 must be fourth, and cow 5 must be fifth. The ranks of the other cows cannot be determined.

First, note that the problem can be converted into a graph, with the cows as the nodes, and the games as the edges. (In particular, note that the graph is a directed acyclic graph, or a DAG.)
For a certain cow X, X's rank can be determined if and only if the following property is true: for every other cow Y, either cow X must be better than cow Y, or cow Y must be better than cow X.
Thus, we can find which pairs of vertices in the graph are connected either by doing a BFS for O(NM) overall or Floyd-Warshall for O(N3) overall. Then, for each cow, we check if every other cow is connected to it, and if so, we increment our answer by 1.
The following is a sample solution:
#include <cstdio>
using namespace std;

FILE *fout = fopen ("contest.out", "w");
FILE *fin = fopen ("contest.in", "r");

const int MAXN = 105;

int N, M, total = 0;
bool reach [MAXN][MAXN];

void main ()
{
    fscanf (fin, "%d %d", &N, &M);

// cows are 'connected' to themselves
    for (int i = 0; i < N; i++)
    reach [i][i] = true;

// read input
    int a, b;
    for (int i = 0; i < M; i++)
    {
        fscanf (fin, "%d %d", &a, &b);
        a--, b--;

        reach [a][b] = true;
    }

// use Floyd-Warshall to compute transitive closure
    for (int k = 0; k < N; k++)
        for (int i = 0; i < N; i++)
            if (reach [i][k])
                for (int j = 0; j < N; j++)
                    if (reach [k][j])
                        reach [i][j] = true;


    for (int i = 0; i < N; i++)
    {
        bool good = true;

    // we can find the rank of a cow if all other cows are connected to it
        for (int j = 0; j < N; j++)
            if (!reach [i][j] && !reach [j][i])
            {
            good = false;
            break;
            }

        if (good)
            total++;
    }

    fprintf (fout, "%d\n", total);
}

Running [Neal Wu, 2007]

The cows are trying to become better athletes, so Bessie is running on a track for exactly N (1 <= N <= 10,000) minutes. During each minute, she can choose to either run or rest for the whole minute.

The ultimate distance Bessie runs, though, depends on her 'exhaustion factor', which starts at 0. When she chooses to run in minute i, she will run exactly a distance of Di (1 <= Di <= 1,000) and her exhaustion factor will increase by 1 -- but must never be allowed to exceed M (1 <= M <= 500).  If she chooses to rest, her exhaustion factor will decrease by 1 for each minute she rests. She cannot commence running again until her exhaustion factor reaches 0. At that point, she can choose to run or rest.

At the end of the N minute workout, Bessie's exaustion factor must be exactly 0, or she will not have enough energy left for the rest of the day.

Find the maximal distance Bessie can run.


INPUT FORMAT:

* Line 1: Two space-separated integers: N and M

* Lines 2..N+1: Line i+1 contains the single integer: Di

SAMPLE INPUT (file cowrun.in):

5 2
5
3
4
2
10


OUTPUT FORMAT:

* Line 1: A single integer representing the largest distance Bessie can run while satisfying the conditions.

SAMPLE OUTPUT (file cowrun.out):

9

OUTPUT DETAILS:

Bessie runs during the first minute (distance=5), rests during the second minute, runs for the third (distance=4), and rests for the fourth and fifth. Note that Bessie cannot run on the fifth minute because she would not end with a rest factor of 0.
This is a straightforward dynamic programming (DP) problem. To solve the problem, we want to find, for each k such that 0 <= k <= N, the maximum possible distance Bessie could have run after the first k minutes, if she has a rest factor of 0. (For example, if we can obtain a distance of 14 after 5 minutes with a rest factor of 0, or we can obtain a distance of 15 after 5 minutes with a rest factor of 0, we would always choose the second over the first.) Clearly, the best such value for 0 is 0. Then, for each minute i of the N minutes, we can compute all of the next values possible with the following method:
-First, try to not run during the minute, and see if this produces an improvement. (Thus, check if the best value for i is better than the one for i + 1.)
-Then, for each number k from 1 to M, let Bessie run for exactly k minutes and then rest for k minutes. See if this new value produces a greater value than the best value for i + 2k (which is the number of minutes finished after running for k minutes and resting for another k minutes).
Thus, since we do M updates for each of the N minutes, our total complexity is O(NM). The following is a sample solution:
#include <cstdio>
using namespace std;

FILE *fout = fopen ("cowrun.out", "w");
FILE *fin = fopen ("cowrun.in", "r");

const int MAXN = 10005;

int N, M, dist [MAXN], best [MAXN];

void main ()
{
    fscanf (fin, "%d %d", &N, &M);

    for (int i = 0; i < N; i++)
        fscanf (fin, "%d", dist + i);

    for (int i = 0; i < N; i++)
    {
     // skip the value
        if (best [i] > best [i + 1])
            best [i + 1] = best [i];

        int sum = best [i], pos = i;

        for (int j = 0; j < M && pos < N; j++)
        {
        // update each value
            sum += dist [i + j];
            pos += 2;

            if (sum > best [pos])
                best [pos] = sum;
        }
    }

    fprintf (fout, "%d\n", best [N]);
}


Telephone Lines [Paul Christiano, 2007]

Farmer John wants to set up a telephone line at his farm. Unfortunately, the phone company is uncooperative, so he needs to pay for some of the cables required to connect his farm to the phone system.

There are N (1 <= N <= 1,000) forlorn telephone poles conveniently numbered 1...N that are scattered around Farmer John's property; no cables connect any them.  A total of P (1 <= P <= 10,000) pairs of poles can be connected by a cable; the rest are too far apart.

The ith cable can connect the two distinct poles Ai and Bi, with length Li    (1 <= L_i <= 1,000,000) units if used. The input data set never names any {Ai,Bi} pair more than once. Pole 1 is already connected to the phone system, and pole N is at the farm. Poles 1 and N need to be connected by a path of cables; the rest of the poles might be used or might not be used.

As it turns out, the phone company is willing to provide Farmer John with K (0 <= K < N) lengths of cable for free. Beyond that he will have to pay a price equal to the length of the longest remaining cable he requires (each pair of poles is connected with a separate cable), or 0 if he does not need any additional cables.

Determine the minimum amount that Farmer John must pay.


INPUT FORMAT:

* Line 1: Three space-separated integers: N, P, and K

* Lines 2..P+1: Line i+1 contains the three space-separated integers:
        Ai, Bi, and Li

SAMPLE INPUT (file phoneline.in):

5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

INPUT DETAILS:

There are 5 poles. Pole 1 cannot be connected directly to poles 4 or 5. Pole 5 cannot be connected directly to poles 1 or 3. All other pairs can be connected. The phone company will provide one free cable.

OUTPUT FORMAT:

* Line 1: A single integer, the minimum amount Farmer John can pay. If it is impossible to connect the farm to the phone company, print -1.

SAMPLE OUTPUT (file phoneline.out):

4

OUTPUT DETAILS:

If pole 1 is connected to pole 3, pole 3 to pole 2, and pole 2 to pole 5 then Farmer John requires cables of length 4, 3, and 9. The phone company will provide the cable of length 9, so the longest cable needed has length 4.

We construct the following graph G: each pole is a vertex, and each possible connection between poles is an edge between corresponding vertices with weight equal to the distance between the poles.
Now imagine we have a function f(lim) that tells us if there exists a path from vertex 1 to vertex N using no more than K edges whose weights are greater than lim. If we have such a function f, we can perform a binary search for the answer: the smallest lim that works (in other words, the smallest k such that f(k) is true) is the minimum amount Farmer John must pay.
So the problem now is implementing function f(lim) efficiently, and to do so, we consider the graph H, which has the same vertices and edges as G but different edge weights. More precisely, an edge between vertices a and b in H has weight 0 if the corresponding edge in G has weight w <= lim, and weight 1 otherwise (if the corresponding edge in G has weight w > lim), so the shortest path between two vertices a and b in H represents the minimum number of edges with weight greater than lim on a path between a and b in G. Thus computing f(lim) is equivalent to checking if the shortest path between 1 and N in H is less than or equal to K, and we can do this in O(E log V) time with Dijkstra's.
In the worst case, we will need to evaluate function f O(log V) times (because of the binary search), so the total running time of the entire algorithm is O(E log2 V). (It's actually possible to compute the shortest path between two vertices in a graph where all edges have weight 0 or 1 in linear time, but that's not needed here.)

#include<fstream>
#include<vector>

using namespace std;

ifstream fin ("phoneline.in");
ofstream fout ("phoneline.out");

const int MAX = 1000 + 5;

vector <int> a[MAX], b[MAX];
int     e[MAX * 10];
bool mark[MAX];
int  dis [MAX], saf[MAX], head, tail;
int n, k, D, M;

void dfs (int u)
{
    dis[u] = D;
    mark[u] = true;
    saf[tail++] = u;
    for (int i = 0; i < a[u].size (); i++) {
        if (!mark[a[u][i]] && b[u][i] <= M)
            dfs (a[u][i]);
    }
}
void Bfs (int MM)
{
    M = MM;
    memset (mark, 0, sizeof mark);
    head = tail = 0;
    D = 0;
    dfs (n - 1);
    while (head < tail) {
        int k = saf[head++];
        for (int i = 0; i < a[k].size (); ++i) {
            if (!mark[a[k][i]]) {
                D = dis[k] + 1;
                dfs (a[k][i]);
            }
        }
    }
}

void bs (int x, int y)
{
    if (y == x + 1) {
        fout << e[y] << endl;
        exit (0);
    }
    int     mid = (y + x) / 2;
    Bfs (e[mid]);
    if (dis[0] <= k)
        bs (x, mid);
    else
        bs (mid, y);
}
void main ()
{
    int ee;
    fin >> n >> ee >> k;
    int     u, v, w;
    for (int i = 0; i < ee; ++i) {
        fin >> u >> v >> w;
        u--;
        v--;
        a[u].push_back (v);
        b[u].push_back (w);
        a[v].push_back (u);
        b[v].push_back (w);
        e[i + 1] = w;
    }
    sort (e, e + 1 + ee);
    Bfs (0);
    if (!mark[0]) {
        fout << "-1" << endl;
        return 0;
    }
    if (dis[0] <= k) {
        fout << "0" << endl;
        return 0;
    }
    bs (0, ee);
}