USACO Training: Controlling Companies

 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₁, ..., C_K with each company C_i owning x_i% of company B and x₁ + .... + 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 which one company controlled the other. For each pair of companies (i, j), I checked if i owns more than 50% of j or if i owns x companies which collectively own more than 50% of j.

What Went Wrong

Clearly this would not work - if we find out that i controls j, then in turn i might control k because it now controls j, and we would have to start all over again. Therefore, I looked for what the result using recursion. Every time we find that i controls j, we check every other company that could be affected, and then recurse.

USACO Training Method

The method used here to solve the problem is as follows. We keep track of which companies control which other companies, and every time we hear that so and so owns this much percent of so and so, we update our information.
The array "owns" keeps track of how much of company j is owned by company i, whether directly or via controlled companies. The array "controls" keeps track of which companies are controlled by which other companies.

Code

/*
USER: qlstudi3
LANG: C++14
TASK: concom
*/
#include <algorithm>
#include <fstream>
#include <vector>
#define MAXN 105
using namespace std;

ifstream cin("concom.in");
ofstream cout("concom.out");

int owns[MAXN][MAXN];
bool ctrl[MAXN][MAXN];

void controls(int i, int j)
{
 if(ctrl[i][j]) return;
 ctrl[i][j] = true;
 for(int k=0; k<=100; k++) owns[i][k] += owns[j][k];
 for(int k=0; k<=100; k++) if(ctrl[k][i]) controls(k, j);
 for(int k=0; k<=100; k++) if(owns[i][k] > 50) controls(i, k);
}

void own(int i, int j, int p)
{
 for(int k=0; k<=100; k++) if(ctrl[k][i]) owns[k][j] += p; 
 for(int k=0; k<=100; k++) if(owns[k][j] > 50) controls(k, j);
}

int main()
{
 int T; cin >> T;
 for(int i=0; i<=100; i++) ctrl[i][i] = 1;
 for(int t=0; t<T; t++)
 {
  int i, j, p;
  cin >> i >> j >> p;
  own(i, j, p);
 }
 for(int i=0; i<=100; i++)
  for(int j=0; j<=100; j++)
   if(i!=j && ctrl[i][j]) cout << i << " " << j << endl;
}