(*
 * Program:  bowling_bram
 * Author:   Bram Kuijvenhoven (bram at kuijvenhoven.net)
 * Language: Pascal (FreePascal 2.x or higher recommended)
 * Notes:    Example/test solution to 'Bowling' problem of BAPC 2006
 *           + Testcase generator
 *           + Dumb and Semi-optimal solutions
 *           OOP based solution; allows for modular approach
 *)

program bowling_bram;


uses
  Classes, SysUtils, Math;
  
const
  MIN_P = 2;
  MAX_P = 100;
  MIN_G = 2;
  MAX_G = 1000;
  MIN_SCORE = 0;
  MAX_SCORE = 300;
  
type

  TSolution = class;

  { TTestCase }

  TTestCase = class
    P,G:integer;
    Score:array of array of PInteger;
    Solution:TSolution;

    constructor Create(AP,AG:integer);
    constructor Read;
    constructor FromArray(AP,AG:integer; const AScore:array of integer);
    constructor RandomUniform(AP,AG:integer; Seed:cardinal);
    constructor RandomGaussian(AP,AG:integer; const Means, StdDevs:array of integer; Seed:cardinal);
    constructor RandomGaussian(AP,AG:integer; Mean, StdDev:integer; Seed:cardinal);
    destructor Destroy; override;

    function Solve:TSolution;
    function SolveSubOptimal:TSolution;
    function SolveBruteForce:TSolution;
    function Check:string;
    function Permute(Seed:cardinal):TTestCase;
    function Merge(Other:TTestCase):TTestCase;
    procedure Write;
  end;

  { TSolution }

  TSolution = class
    P:integer;
    MinScore,MaxScore:array of integer;
    TestCase:TTestCase;
    constructor Create(AP:integer);
    procedure Write;
  end;
  
{ TTestCase }

constructor TTestCase.Read;
var
  Player: Integer;
  Game: Integer;
begin
  readln(P,G);
  Create(P,G);
  for Player:=0 to P-1 do
  begin
    for Game:=0 to G-1 do
    begin
      System.read(Score[Player,Game]^);
    end;
    readln;
  end;
end;

type
  PPlayerScore = ^TPlayerScore;
  TPlayerScore = record
    Score:integer;
    Player:integer;
  end;

function PIntegerCompare(Item1,Item2: pointer):integer;
begin
  Result:=PInteger(Item1)^-PInteger(Item2)^;
end;

function PPlayerScoreCompare(Item1,Item2: pointer):integer;
begin
  Result:=PPlayerScore(Item1)^.Score-PPlayerScore(Item2)^.Score;
end;

function TTestCase.Solve:TSolution;
var
  Scores:array of TList;
  CompetitorScore:array of integer;
  Player, Game, Competitor: Integer;
  AllScores: TList;
  List: TList;
  Max: Integer;
  Index: Integer;
  CompetitorIndex: Integer;
  I: Integer;
  PlayerScore:PPlayerScore;
begin
  Solution:=TSolution.Create(P);
  Solution.TestCase:=self;
  // pre-processing: sort each players scores + all scores
  SetLength(Scores,P);
  AllScores:=TList.Create;
  AllScores.Capacity:=P*G;
  for Player:=0 to P-1 do
  begin
    List:=TList.Create;
    List.Capacity:=G;
    for Game:=0 to G-1 do
    begin
      List.Add(Score[Player,Game]);
      new(PlayerScore);
      PlayerScore^.Player:=Player;
      PlayerScore^.Score:=Score[Player,Game]^;
      AllScores.Add(PlayerScore);
    end;
    List.Sort(@PIntegerCompare);
    Scores[Player]:=List;
  end;
  AllScores.Sort(@PPlayerScoreCompare);
  // solve the problem for each player
  SetLength(CompetitorScore,G);
  for Player:=0 to P-1 do
  begin
    // for the maximum number of wins, the competitor scores are calculated as per sorted-game maxima:
    for Game:=0 to G-1 do
    begin
      Max:=0;
      for Competitor:=0 to P-1 do
        if Competitor<>Player then
          Max:=Math.Max(Max,PInteger(Scores[Competitor][Game])^);
      CompetitorScore[Game]:=Max;
    end;
    // the maximum number of wins is now calculated as follows
    List:=Scores[Player];
    Index:=G; // index into List
    CompetitorIndex:=G; // index into CompetitorScore
    repeat
      Dec(Index);
      Dec(CompetitorIndex);
      while (CompetitorIndex>=0) and (PInteger(List[Index])^<=CompetitorScore[CompetitorIndex]) do
        Dec(CompetitorIndex);
    until CompetitorIndex<0;
    // store maximum number of wins
    Solution.MaxScore[Player]:=G-1-Index;
    // for he minimum number fo wins, the competitor scores are calculated as the maxima of all their scores together
    CompetitorIndex:=AllScores.Count-1; // index into AllScores
    for Game:=G-1 downto 0 do
    begin
      while PPlayerScore(AllScores[CompetitorIndex])^.Player=Player do
        Dec(CompetitorIndex);
      CompetitorScore[Game]:=PPlayerScore(AllScores[CompetitorIndex])^.Score;
      Dec(CompetitorIndex);
    end;
    // the minimum number of wins is now calculated as follows
    List:=Scores[Player];
    Index:=G; // index into List
    CompetitorIndex:=G; // index into CompetitorScore
    repeat
      Dec(Index);
      Dec(CompetitorIndex);
      while (Index>=0) and (CompetitorScore[CompetitorIndex]<PInteger(List[Index])^) do
        Dec(Index);
    until Index<0;
    // store the minimum number of wins
    Solution.MinScore[Player]:=CompetitorIndex+1;
  end;
  // clean up
  for Player:=0 to P-1 do
    Scores[Player].Free;
  for I:=0 to AllScores.Count-1 do
    dispose(PPlayerScore(AllScores[I]));
  AllScores.Free;
  // return solution
  Result:=Solution;
end;

function TTestCase.SolveSubOptimal:TSolution;
var
  Scores:array of TList;
  CompetitorScore:array of integer;
  Player, Game, Competitor: Integer;
  OtherScores: TList;
  List: TList;
  Max: Integer;
  Index: Integer;
  CompetitorIndex: Integer;
begin
  Solution:=TSolution.Create(P);
  Solution.TestCase:=self;
  // pre-processing: sort each players scores
  SetLength(Scores,P);
  for Player:=0 to P-1 do
  begin
    List:=TList.Create;
    List.Capacity:=G;
    for Game:=0 to G-1 do
      List.Add(Score[Player,Game]);
    List.Sort(@PIntegerCompare);
    Scores[Player]:=List;
  end;
  // solve the problem for each player
  OtherScores:=TList.Create;
  OtherScores.Capacity:=(P-1)*G;
  SetLength(CompetitorScore,G);
  for Player:=0 to P-1 do
  begin
    // for the maximum number of wins, the competitor scores are calculated as per sorted-game maxima:
    for Game:=0 to G-1 do
    begin
      Max:=0;
      for Competitor:=0 to P-1 do
        if Competitor<>Player then
          Max:=Math.Max(Max,PInteger(Scores[Competitor][Game])^);
      CompetitorScore[Game]:=Max;
    end;
    // the maximum number of wins is now calculated as follows
    List:=Scores[Player];
    Index:=G; // index into List
    CompetitorIndex:=G; // index into CompetitorScore
    repeat
      Dec(Index);
      Dec(CompetitorIndex);
      while (CompetitorIndex>=0) and (PInteger(List[Index])^<=CompetitorScore[CompetitorIndex]) do
        Dec(CompetitorIndex);
    until CompetitorIndex<0;
    // store maximum number of wins
    Solution.MaxScore[Player]:=G-1-Index;
    // for he minimum number fo wins, the competitor scores are calculated as the maxima of all their scores together
    OtherScores.Count:=0;
    for Competitor:=0 to P-1 do
      if Competitor<>Player then
        for Game:=0 to G-1 do
          OtherScores.Add(Score[Competitor,Game]);
    OtherScores.Sort(@PIntegerCompare);
    for Game:=0 to G-1 do
      CompetitorScore[Game]:=PInteger(OtherScores[(P-2)*G+Game])^;
    // the minimum number of wins is now calculated as follows
    List:=Scores[Player];
    Index:=G; // index into List
    CompetitorIndex:=G; // index into CompetitorScore
    repeat
      Dec(Index);
      Dec(CompetitorIndex);
      while (Index>=0) and (CompetitorScore[CompetitorIndex]<PInteger(List[Index])^) do
        Dec(Index);
    until Index<0;
    // store the minimum number of wins
    Solution.MinScore[Player]:=CompetitorIndex+1;
  end;
  // clean up
  OtherScores.Free;
  for Player:=0 to P-1 do
    Scores[Player].Free;
  // return solution
  Result:=Solution;
end;

// generate all permutations and check the number of wins; runs in O(G*P*(G!)^(P-1)) time...
function TTestCase.SolveBruteForce: TSolution;
var
  PermScores:array of array of PInteger;

  procedure DetermineWins;
  var
    Wins:array of integer;
    Player,Game: Integer;
    WinScore,Winner: Integer;
  begin
    SetLength(Wins,P);
    for Player:=0 to P-1 do
      Wins[Player]:=0;
    // determine win counts
    for Game:=0 to G-1 do
    begin
      WinScore:=-1;
      Winner:=-1;
      for Player:=0 to P-1 do
        if PermScores[Player,Game]^>WinScore then
        begin
          Winner:=Player;
          WinScore:=PermScores[Player,Game]^;
        end
        else if PermScores[Player,Game]^=WinScore then
          Winner:=-1;
      if Winner>=0 then
        Inc(Wins[Winner]);
    end;
    // update minwin/maxwins
    for Player:=0 to P-1 do
    begin
      Solution.MinScore[Player]:=Min(Solution.MinScore[Player],Wins[Player]);
      Solution.MaxScore[Player]:=Max(Solution.MaxScore[Player],Wins[Player]);
    end;
  end;

var
  Player: Integer;

  procedure PermutePlayer;
  var
    Used: array of boolean;
    Game: Integer;
    
    procedure PermuteGame;
    var
      J: Integer;
    begin
      if Game>=G then
      begin
        Inc(Player);
        PermutePlayer;
        Dec(Player);
        Exit;
      end;
      
      for J:=0 to G-1 do
        if not Used[J] then
        begin
          Used[J]:=true;
          PermScores[Player,Game]:=Score[Player,J];
          Inc(Game);
          PermuteGame;
          Dec(Game);
          Used[J]:=false;
        end;
    end;
    
  var
    I:Integer;
  begin
    if Player>=P then
    begin
      DetermineWins;
      Exit;
    end;
    // init used
    SetLength(Used,G);
    for I:=0 to G-1 do
      Used[I]:=false;
    Game:=0;
    // permute
    PermuteGame;
  end;
  
var
  I: Integer;
begin
  Solution:=TSolution.Create(P);
  Solution.TestCase:=self;
  for Player:=0 to P-1 do
  begin
    Solution.MinScore[Player]:=G;
    Solution.MaxScore[Player]:=0;
  end;
  // init permutation generation
  SetLength(PermScores,P);
  for I:=0 to P-1 do
    SetLength(PermScores[I],G);
  for I:=0 to G-1 do
    PermScores[0,I]:=Score[0,I];
  Player:=1;
  // permute
  PermutePlayer;
  // return solution
  Result:=Solution;
end;

function TTestCase.Check: string;
var
  Player: Integer;
  Game: Integer;
begin
  if (P<MIN_P) or (P>MAX_P) then Exit(Format('P = %d is not within the valid range %d..%d',[P,MIN_P,MAX_P]));
  if (G<MIN_G) or (G>MAX_G) then Exit(Format('P = %d is not within the valid range %d..%d',[G,MIN_G,MAX_G]));
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      if (Score[Player,Game]^<MIN_SCORE) or (Score[Player,Game]^>MAX_SCORE) then
        Exit(Format('The score %d, for player %d, game %d, is not within the valid range %d..%d',
                    [Player,Game,Score[Player,Game]^,MIN_SCORE,MAX_SCORE]));
  Result:='';
end;

// shuffle per-player scores and return self
function TTestCase.Permute(Seed: cardinal):TTestCase;
var
  Used:array of boolean;
  NewScore:array of integer;
  Player: Integer;
  Game: Integer;
  Index: LongInt;
begin
  RandSeed:=Seed;
  SetLength(Used,G);
  SetLength(NewScore,G);
  for Player:=0 to P-1 do
  begin
    for Game:=0 to G-1 do
      Used[Game]:=false;
    for Game:=0 to G-1 do
    begin
      repeat
        Index:=Random(G);
      until not Used[Index];
      NewScore[Game]:=Score[Player,Index]^;
      Used[Index]:=true;
    end;
    for Game:=0 to G-1 do
      Score[Player,Game]^:=NewScore[Game];
  end;
  Result:=self;
end;

function TTestCase.Merge(Other: TTestCase): TTestCase;
var
  Player: Integer;
  Game: Integer;
begin
  if P<>Other.P then raise Exception.CreateFmt('self.P <> Other.P in merge',[]);
  for Player:=0 to P-1 do
  begin
    SetLength(Score[Player],G+Other.G);
    for Game:=0 to Other.G-1 do
    begin
      new(Score[Player,G+Game]);
      Score[Player,G+Game]^:=Score[Player,Game]^;
    end;
  end;
  G+=Other.G;
  Other.Free;
  Result:=self;
end;

procedure TTestCase.Write;
var
  Player: Integer;
  Game: Integer;
begin
  writeln(P,' ',G);
  for Player:=0 to P-1 do
  begin
    for Game:=0 to G-1 do
    begin
      if Game>0 then
        System.write(' ');
      System.write(Score[Player,Game]^);
    end;
    writeln;
  end;
end;

constructor TTestCase.Create(AP, AG: integer);
var
  Player: Integer;
  Game: Integer;
begin
  P:=AP;
  G:=AG;
  SetLength(Score,P);
  for Player:=0 to P-1 do
  begin
    SetLength(Score[Player],G);
    for Game:=0 to G-1 do
      new(Score[Player,Game]);
  end;
end;

// supply scores in a flat array, which is the concatenation of the scores per player
constructor TTestCase.FromArray(AP, AG: integer; const AScore: array of integer);
var
  Player: Integer;
  Game: Integer;
begin
  Create(AP,AG);
  if Length(AScore)<>P*G then raise Exception.CreateFmt('Wrong number of scores specified',[]);
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      Score[Player,Game]^:=AScore[G*Player+Game];
end;

constructor TTestCase.RandomUniform(AP, AG: integer; Seed: cardinal);
var
  Player: Integer;
  Game: Integer;
begin
  Create(AP,AG);
  RandSeed:=Seed;
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      Score[Player,Game]^:=Random(300);
end;

constructor TTestCase.RandomGaussian(AP, AG: integer; const Means, StdDevs: array of integer; Seed: cardinal);
var
  Player: Integer;
  Game: Integer;
begin
  Create(AP,AG);
  RandSeed:=Seed;
  if (Length(Means)<>P) or (Length(StdDevs)<>P) then Exception.CreateFmt('Means or StdDevs is not of length P = %d',[P]);
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      Score[Player,Game]^:=Max(MIN_SCORE,Min(MAX_SCORE,Round(RandG(Means[Player],StdDevs[Player]))));
end;

constructor TTestCase.RandomGaussian(AP, AG: integer; Mean, StdDev: integer; Seed: cardinal);
var
  Player: Integer;
  Game: Integer;
begin
  Create(AP,AG);
  RandSeed:=Seed;
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      Score[Player,Game]^:=Max(MIN_SCORE,Min(MAX_SCORE,Round(RandG(Mean,StdDev))));
end;

destructor TTestCase.Destroy;
var
  Player: Integer;
  Game: Integer;
begin
  for Player:=0 to P-1 do
    for Game:=0 to G-1 do
      dispose(Score[Player,Game]);
  Solution.Free;
  
  inherited Destroy;
end;

{ TSolution }

constructor TSolution.Create(AP: integer);
begin
  P:=AP;
  SetLength(MinScore,P);
  SetLength(MaxScore,P);
end;

procedure TSolution.Write;
var
  Player: Integer;
begin
  for Player:=0 to P-1 do
    System.writeln(MinScore[Player],' ',MaxScore[Player]);
end;

// Program
procedure GenerateTestCases;
var
  TestCases:array of TTestCase;

  procedure AddTestCase(ATestCase:TTestCase);
  begin
    SetLength(TestCases,Length(TestCases)+1);
    TestCases[High(TestCases)]:=ATestCase;
  end;
  
var
  I: Integer;
  Error: string;
begin
  // code that generates testcases
  //  example testcases
  AddTestCase(TTestCase.FromArray(3,3,[102, 86, 94,       98, 73,112,       95, 84,125]));
  AddTestCase(TTestCase.FromArray(3,4,[100,110,112,116,   98,112,110,112,   90, 98,113,113]));
  //  other testcases
  AddTestCase(TTestCase.FromArray(3,4,[100,110,112,116,   98,102,102,102,   90, 98,113,113]));
  AddTestCase(TTestCase.FromArray(3,4,[100,100,110,110,  110,110,110,110,  105,105,105,115]).Permute(234879));
  AddTestCase(TTestCase.FromArray(3,4,[  0,  0,  0,  0,    0,  0,  0,  0,    0,  0,  0,  0]));
  AddTestCase(TTestCase.FromArray(3,4,[  0,100,200,300,    0,100,200,300,    0,100,200,300]).Permute(24689));
  AddTestCase(TTestCase.FromArray(3,4,[100,110,120,130,  101,111,121,131,  102,112,122,132]).Permute(32461));
  AddTestCase(TTestCase.FromArray(10,4,[100,110,120,130,  101,111,121,131,  102,112,122,132,
                                        103,113,123,133,  104,114,124,134,  105,115,125,135,
                                        106,116,126,136,  107,117,127,137,  108,118,128,138,
                                        109,119,129,139]).Permute(6598));
  AddTestCase(TTestCase.FromArray(4,10,[100,110,120,130,140,150,160,170,180,190,
                                        101,111,121,131,141,151,161,171,181,191,
                                        102,112,122,132,142,152,162,172,182,192,
                                        103,113,123,133,143,153,163,173,183,193]).Permute(41096));
  AddTestCase(TTestCase.FromArray(2,10,[130,130,130,130,170,170,170,170,190,190,
                                        163,163,163,163,163,163,183,183,183,193]).Permute(41096));
  AddTestCase(TTestCase.RandomUniform(3,4,132356781));
  AddTestCase(TTestCase.RandomUniform(30,40,132356781));
  AddTestCase(TTestCase.RandomUniform(100,1000,132356781));
  AddTestCase(TTestCase.RandomGaussian(3,10,  [100,110,120],[20,80,20],67342856));
  AddTestCase(TTestCase.RandomGaussian(3,100, [100,110,120],[20,80,20],67342856));
  AddTestCase(TTestCase.RandomGaussian(3,1000,[100,110,120],[20,80,20],67342856));
  AddTestCase(TTestCase.RandomGaussian(3,1000,[100,110,120],[20,80,20],67342856).Permute(92416788));
  AddTestCase(TTestCase.RandomGaussian(11,10,  [100,100,100,110,110,110,120,120,120,180,180],
                                               [ 20, 40, 60, 20, 40, 60, 20, 40, 60,  2,  2],4359871));
  AddTestCase(TTestCase.RandomGaussian(11,100, [100,100,100,110,110,110,120,120,120,180,180],
                                               [ 20, 40, 60, 20, 40, 60, 20, 40, 60,  2,  2],4359871));
  AddTestCase(TTestCase.RandomGaussian(11,1000,[100,100,100,110,110,110,120,120,120,180,180],
                                               [ 20, 40, 60, 20, 40, 60, 20, 40, 60,  2,  2],4359871));
  AddTestCase(TTestCase.RandomGaussian(2,  10,  150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(2,  100, 150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(2,  1000,150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(2,  1000,150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(10, 1000,150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(100,1000,150,20,498451656));
  AddTestCase(TTestCase.RandomGaussian(100,1000,150,40,498451656));
  AddTestCase(TTestCase.RandomGaussian(100,1000,150,80,498451656));
  AddTestCase(TTestCase.RandomGaussian(3 ,10,  [ 80,120,160],[20,20,10],287901246).Merge(
              TTestCase.RandomGaussian(3 ,10,  [180,140,160],[10,20,10],287901246)));
  AddTestCase(TTestCase.RandomGaussian(3 ,500, [ 80,120,160],[20,20,10],287901246).Merge(
              TTestCase.RandomGaussian(3 ,500, [180,140,160],[10,20,10],287901246)).Permute(4561546));
  AddTestCase(TTestCase.RandomGaussian(10 ,5  ,100,80,823167675).Merge(
              TTestCase.RandomGaussian(10 ,5  ,160,80,823167675)));
  AddTestCase(TTestCase.RandomGaussian(20 ,50 ,100,80,823167675).Merge(
              TTestCase.RandomGaussian(20 ,50 ,160,80,823167675)));
  AddTestCase(TTestCase.RandomGaussian(100,500,100,80,823167675).Merge(
              TTestCase.RandomGaussian(100,500,160,80,823167675)));
  AddTestCase(TTestCase.RandomGaussian(100,400,100,10,823167675).Merge(
              TTestCase.RandomGaussian(100,300,110,10,823167675)).Merge(
              TTestCase.RandomGaussian(100,300,120,10,823167675)).Permute(67355625));
    // write them
  writeln(Length(TestCases));
  for I:=0 to High(TestCases) do
  begin
    Error:=TestCases[i].Check;
    if Error<>'' then
      writeln(Format('Error in testcase %d: %s',[I,Error]))
    else
      TestCases[i].Write;
    TestCases[i].Free;
  end;
end;

type
  TSolver = (soOptimal,soSuboptimal,soBruteForce);
var
  Solver:TSolver = soSubOptimal;

procedure ReadSolveWrite;
var
  NumTestCases,TestCaseIndex:integer;
begin
  readln(NumTestCases);
  for TestCaseIndex:=1 to NumTestCases do
  try
    case Solver of
      soOptimal:    TTestCase.Read.Solve.Write;
      soSuboptimal: TTestCase.Read.SolveSubOptimal.Write;
      soBruteForce: TTestCase.Read.SolveBruteForce.Write;
    end;
  except on E:Exception do
    writeln(Format('An exception occured while processing testcase %d: %s',[TestCaseIndex,E.Message]));
  end;
end;

var
  I: Integer;
  Generate:boolean = false;

begin

  for I:=1 to ParamCount do
    if ParamStr(I)='--brute-force' then
      Solver:=soBruteForce
    else if ParamStr(I)='--sub-optimal' then
      Solver:=soSuboptimal
    else if ParamStr(I)='--optimal' then
      Solver:=soOptimal
    else if ParamStr(I)='--generate' then
      Generate:=true
    else
    begin
      writeln('Usage: ./bowling_bram [OPTIONS]');
      writeln('Options:');
      writeln('  --brute-force  Use brute force solver: O(PG (G!)^P)');
      writeln('  --generate     Generate testcases instead of solve');
      writeln('  --help         show this help text');
      writeln('  --optimal      Use optimal solver:     O(PG log(PG))');
      writeln('  --sub-optimal  Use suboptimal solver:  O(PPG log(PG))  <-- Default');
      Halt;
    end;

  if Generate then
    GenerateTestCases
  else
    ReadSolveWrite;

end.

