The Way Through The Forest

Hecking DONE with 4.4! Attempt 1 (WA 1/12) I tried using a straightforward max-flow min-cut as described my USACO, calculating the max flow and then enumerating over the edges in increasing weight order, testing if the removal of an edge decreases the max flow, and if so, removing this edge.  RESULT: After some preliminary debugging this passed the sample test case, but failed on the second case, due to the requirement that the amount of edges must be minimized. CONTEMPLATION: Here Teacher Huang advised me to undertake the method of "multiply input edge weight by 10000 and add 1" to account for the weighting of edge count as well, but I refused to believe this, as if we have a graph of the following edge list: (1, 2) weight 1 -> weight 10001, i.e. edge #1 (1, 2) weight 1 -> weight 10001, i.e. edge #2 (2, 3) weight 2 -> weight 20001, i.e. edge #3 Here, the max flow is obviously 20001, but the USACO algorithm will deduce the edges #

UVA 11389: The Bus Driver Problem Solution: Sort the arrays of morning times and evening times in opposite orders: sort morning times from least to greatest and evening times from greatest to least. Now, if we transpose (merge) the sorted arrays into one array, we can apply the greedy load balancing algorithm, by pairing numbers from opposite ends. Note that all numbers can be paired together since we have an equal amount of elements in the morning time array and night time array. The original greedy load balancing algorithm is optimal because the X-th smallest element is always paired with the X-th largest element. This, however, cannot be recreated here since there is an additional restriction: the pairs must include exactly one morning element and exactly one evening element. Hence, we have an "almost-sorted" array, from (pseudo) least to greatest, which looks like this (sample test case): morn    night 10 15 | 10 15 Now, if we start from opposite ends of the arr

It's about time I finished section 4.2 of USACO training... USACO Training: Job Processing We can compute the first variable of output by attempting to greedily assign the tasks to the type-A machines. This is completed by keeping track of both how much time an machine spends on finishing an arbitrary task AND how much time the machine ALREADY SPENT on finishing assigned TASKS. The first comes from input; the second is initially zero and gradually increases. We wish to minimize the time it takes to finish task N. The time it will take to finish any task i is the minimal possible value of m.1 + m.2 where m is any machine. Once the machine m is selected such that this value is minimized, increase the m.2 value of this machine by m.1. We repeat this process for all i from 1 to N. Notice that the answer is not dependent on what i is, but only on the m.1 and m.2 values. Assume we store these minimum values in an array, T[1] to T[N]. Clearly the first answer is T[N].