The Way Through The Forest

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]....

UVA 787 and Big Number Multiplication Problem Background: Big Numbers in this problem Big numbers are effectively storing sequence of digit chunks and directly manipulating them as if they were a large number. The most intuitive way to do this is to make an array where every element is a digit, but this is not effectively using the memory. Hence, it is logical to store numbers "millions at a time", i.e. 324876498726832746  [2]  | [1] | [0] like that. Necessities to Implement Notice that although this problem may LOOK like DP, it's really solvable by O(N^2) enumeration. Also notice that in this enumeration we will only be multiplying a large number with a normal number. Pseudocode for algorithm: CREATE LargeNumber NAME best SET -INFINITY FOR EACH i BETWEEN 0 and LENGTH OF list DO:     CREATE LargeNumber NAME product SET 1     FOR EACH j BETWEEN i AND LENGTH OF list DO         SET product TO product TIMES list[j] ...

USACO 2018 US Open Contest, Gold Problem 2. Milking Order We need to find the biggest number X such that the first X observations are satisfied. Notice that this is perfect to do a binary search on: the invariant is that if the first X observations are satisfied, all observations X-1 will be satisfied; if the first X are insatisfied, all observations X+1 will not be satisfied. So how do we check if all observations to X are satisfied? Let us assemble a graph, in which each observation O_1, O_2, O_3, ... O_i, ... O_l(o) is represented as an edge between O_i and O_i+1 for all i. These observations are satisfiable if and only if this graph has a topological sorting. Lexicographic topological sorting on a graph can be done in O(E + V log_2 V) time (log_2 V because of priority_queue to extract lowest element). So, our total time complexity will be O((E + NlogN) logM). Here, E=200K (the sum of the M_i), N=100K, and M=50K, so it's fast enough. LTS can be easily implemented with ...

Notice that any integer sequence of length N where K elements are the same, this is a valid painting; Bessie can use her last stamp on the consecutive K elements and then incrementally work outwards (that is, backwards).. It's easier to use complementary counting - we wish to find the # of sequences such that there exists NO K elements that are the same. So, here's an unoptimized DP equation that is over N: dp ( n ) = ( M − 1 ) ⋅ ∑ c = 1 K − 1 dp ( n − c ) . Notice that if this recurrence equation is being called on a value of N that is less than K, dp(n) = M^N. This is very important for our optimization. However, this is effectively O(NK), which only gets 3/4 credit. Let us make another different DP equation, S, defined as: s ( n ) = ∑ n i = 1 dp ( n ) a Hence, dp(n) = s(n)-s(n-1), so  s ( n ) − s ( n − 1 ) = ( M − 1 ) ( s ( n − 1 ) − s ( n − K ) ) ,or  s ( n ) = M s ( n − 1 ) − ( M − 1 ) s ( n − K ). But wait! Remember that dp(n) = M^N if n is less ...