The Way Through The Forest

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 Training: Controlling Companies (concom) Some companies are partial owners of other companies because they have acquired part of their total shares of stock. For example, Ford at one point owned 12% of Mazda. It is said that a company A controls company B if at least one of the following conditions is satisfied: Company A = Company B Company A owns more than 50% of Company B Company A controls K (K >= 1) companies denoted C 1 , ..., C K with each company C i owning x i % of company B and x 1 + .... + x K > 50%. Given a list of triples (i,j,p) which denote company i owning p% of company j, calculate all the pairs (h,s) in which company h controls company s. There are at most 100 companies. Write a program to read the list of triples (i,j,p) where i, j and p are positive integers all in the range (1..100) and find all the pairs (h,s) so that company h controls company s. My 1st Method I enumerated the amount of companies to find pairs in whi...

LA 2678: Sub-sequence Problem Statement Analysis     We are asked to find the length of the shortest sub-sequence such that the sum of all elements in it is at least S. In other words, given the array A_0 ~ A_N-1, find the smallest possible X such that there exists a i which satisfies ∑A_j ≥ S, where j = i ~ i + X - 1.     For example, when A = [1, 2, 3, 4, 5], N = 5, and S = 11, the smallest possible X is 3 and the i is 2. This is sample test case 2. Algorithm: O(N^3)     The most naive method is to permute through all possible sub-sequence beginnings and ends. There are N beginnings and N/2 ends on average, making just permuting through possible sub-sequences O(N^2). Multiplying by the cost of finding the sum of that sub-sequence, O(N), gives us a total O(N^3) algorithm. Clearly that will not work! Algorithm: O(N^2)     However, we can use a prefix sum to improve on the cost of finding the sum of that sub-sequence....

Code Collection: VIJOS 1255 METHOD: O(n^3), Prefix Sum + O(n) Kadane's Algorithm (10/10) #include <algorithm> #include <iostream> #include <cstring> using namespace std; int aray[305][305], psum[305][305], comp[305]; const int SMALL = -22950001; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int R, C; cin >> R >> C; for(int i=1; i<=R; i++) for(int j=1; j<=C; j++) { cin >> aray[i][j]; if(aray[i][j] == 0) aray[i][j] = SMALL; psum[i][j] = aray[i][j] + psum[i-1][j]; } int best = aray[1][1]; for(int s=1; s<=R; s++) for(int e=s; e<=R; e++) { memset(comp, 0, sizeof comp); for(int i=1; i<=C; i++) { comp[i] = psum[e][i] - psum[s-1][i]; if(comp[i] < 0) comp[i] = SMALL; } int cmax = comp[1], cbest = comp[1]; for(int i=2; i<=C; i++) { cmax = max(comp[i], cmax+comp[i]); cbest = max(cbest...