The Way Through The Forest

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

BZOJ 3343 and Chunks Problem Statement There are N≤1000000 counters. You are asked to do Q≤3000 actions on these counters, either: Increment all counters between L and R by W, given that 1≤L≤R≤N and 1≤W≤1000. This command will be in the format "M <L> <R> <W>", where L, R, and W are integers. Count the amount of counters between L and R and are greater than W, given that 1≤L≤R≤N and 1≤W≤1000. This command will be in the format "A <L> <R> <W>", where L, R, and W are integers. Core Idea Any array of integer size N can be broke up into √N+1 chunks of √N elements each for the first N blocks and then the remainder amount for the last block. Although this may seem as  the bloody obvious at first, splitting up an extremely large array into chunks and then doing work on the chunks can make a program vastly more efficient. There are various example: Searching - if a block's lowest value is above the targe...