Blank File for solving problems for Google Code Jam

import sys, copy;
def readData():
return
def solve():
return “Not Implemented”
inputFile = sys.argv[1] if (len(sys.argv) > 1) else “input.txt”;
outputFile = sys.argv[2] if (len(sys.argv) > 2) else (inputFile + “out.txt”) if (len(sys.argv) > 1) else “output.txt”;
print inputFile, outputFile
file = open(outputFile, “w”)
with open(inputFile, ‘r’) as f:
t = int(f.readline())
print t
for i in range(1, t + 1):
file.write(“Case #” + str(i) + “: “)
readData()
file.write(str(solve()) + “\n”)
file.close()

Crossover problem: Super Stack

Recently I participated in Crossover Senior Architect Tournament.

The last problem was scored in 100 points and it required some optimization since for four tests there was a message that the process hasn’t finished in 5 seconds. Most of participants who were eligible to continue scored equally on this problem getting 84 points of 100.

ss8f

ss8af

ss8bf.png

ss9f

Super Stack
Implement a simple stack that accepts the following commands and performs the operations associated with them:

push k: Push integer k onto the top of the stack.
pop: Pop the top element from the stack. It is guaranteed that this will not be called on an empty stack.
inc e k: Add k to each of the bottom e elements of the stack.
Complete the superStack function from the provided code. It has one parameter: an array of n strings, operations. The function must create an empty stack and perform each of the n operations in order and, after performing each operation, print the value of the stack’s top element on a new line; if the stack is empty, print EMPTY instead.

Input Format

The provided code reads the following input from stdin and passes it to the function:

The first line contains an integer, n, denoting the number of operations to perform on the stack.

Each line i of the n subsequent lines contains a space-separated string describing operations[i].

Constraints

1 ≤ n ≤ 2 × 10^5
-10^9 ≤ k ≤ 10^9
1 ≤ e ≤ |S|, where |S| is the size of the stack at the time of the operation.
It is guaranteed that pop is never called on an empty stack.
Output Format

After performing each operation, print the value of the stack’s top element on a new line; if the stack is empty, print EMPTY instead.

Sample Input 0

12
push 4
pop
push 3
push 5
push 2
inc 3 1
pop
push 1
inc 2 2
push 4
pop
pop
Sample Output 0

4
EMPTY
3
5
2
3
6
1
1
4
1
8
Explanation 0

The diagram below depicts the stack after each operation:

After each operation, we print the value denoted by Current Top on a new line.

In other words, we have an empty stack, S, we express as an array where the leftmost element is the bottom of the stack and the rightmost element is its top. We perform the following sequence of n = 12 operations as given in the operations array:

push 4: Push 4 onto the top of the stack, so S = [4]. We then print the top element, 4, on a new line.
pop: Pop the top element from the stack, so S = []. Because the stack is now empty, we print EMPTY on a new line.
push 3: Push 3 onto the top of the stack, so S = [3]. We then print the top element, 3, on a new line.
push 5: Push 5 onto the top of the stack, so S = [3, 5]. We then print the top element, 5, on a new line.
push 2: Push 2 onto the top of the stack, so S = [3, 5, 2]. We then print the top element, 2, on a new line.
inc 3 1: Add k = 1 to bottom e = 3 elements of the stack, so S = [4, 6, 3]. We then print the top element, 3, on a new line.
pop: Pop the top element from the stack, so S = [4, 6]. We then print the top element, 6, on a new line.
push 1: Push 1 onto the top of the stack, so S = [4, 6, 1]. We then print the top element, 1, on a new line.
inc 2 2: Add k = 2 to bottom e = 2 elements of the stack, so S = [6, 8, 1]. The top element is 1, so we print 1 after this operation.
push 4: Push 4 onto the top of the stack, so S = [6, 8, 1, 4]. We then print the top element, 4, on a new line.
pop: Pop the top element from the stack, so S = [6, 8, 1]. We then print the top element, 1, on a new line.
pop: Pop the top element from the stack, so S = [6, 8]. We then print the top element, 8, on a new line.

super-stack

Crossover problem: Shrinking Number Line

Recently I participated in Crossover Senior Architect Tournament.

The third problem was scored in 75 points and it was a little bit unclear. Most of participants who were eligible to continue scored equally on this problem getting 56 points of 75.

s5af.png

s5f

s66f.png

The problem description is below.

Shrinking Number Line

We have an array of n integers, point, and an integer, k. We can perform either of the following operations once for each point[i] in point:

Increment point[i] by k.
Decrement point[i] by k.
We want to perform an operation on each point[i] such that the difference between the maximum and minimum values in the array after performing all operations is minimal.

Complete the minimize function in the from the provided code. It has two parameters:

An array of n integers, point, where the value of each element corresponds to a point on the number line.
An integer, k, denoting the value that each element must either be incremented or decremented by.
The function must perform one operation on each pointi such that the absolute difference between the maximum and minimum values in the modified point array is minimal, then return an integer denoting the minimal difference between the modified array’s new maximum and minimum values.

Input Format

The provided code reads the following input from stdin and passes it to the function:

The first line contains an integer, n, denoting the number of elements in the point array.

Each line i of the n subsequent lines (where 0 ≤ i < n) contains an integer describing point[i].

The last line contains an integer, k.

Constraints

1 ≤ n ≤ 100
1 ≤ k ≤ 10^5
-10^5 ≤ point[i] ≤ 10^5
Output Format

The function must perform one operation on each pointi such that the absolute difference between the maximum and minimum values in the modified point array is minimal, then return an integer denoting this minimal difference between the array’s new maximum and minimum values. This is printed to stdout by the provided code.

Sample Input 0

3
-3
0
1
3
Sample Output 0

3
Explanation 0

We have point = [-3, 0, 1] and k = 3. If we add k to the first element and subtract it from the latter two elements, we get point = [-3 + 3, 0 − 3, 1 − 3] = [0, -3, -2]. We then take the absolute difference between the maximum and minimum values in point, which is |0 − -3| = 3, and return 3 as our answer.

Sample Input 1

3
4
7
-7
5
Sample Output 1

4
Explanation 1

We have point = [4, 7, -7] and k = 5. If we subtract k from the first and second elements and add k to the third element, we get point = [4 − 5, 7 − 5, -7 + 5] = [-1, 2, -2]. We then take the absolute difference between the maximum and minimum values in point, which is |-2 − 2| = 4, and return 4 as our answer.

Sample Input 2

2
-100000
100000
100000
Sample Output 2

0
Explanation 2

We have point = [-100000, 100000] and k = 100000. If we add k to the first element and subtract k from the second element, we get point = [-100000 + 100000, 100000 − 100000] = [0, 0]. We then take the absolute difference between the two values in point, which is |0 − 0| = 0 as there are only two elements, and return 0 as our answer.

 

Crossover problem: Anagram Difference

Recently I participated in Crossover Senior Architect Tournament.

The second problem was scored in 75 points and it was quite simple. I was surprised that nobody except me got the perfect score on such a simple problem.

s4af.png

s4f.png

The problem description is below.

Anagram Difference

We define an anagram to be a word whose characters can be rearranged to create another word. Given two strings, we want to know the minimum number of characters already in either string that we must modify to make the two strings anagrams; if it’s not possible to make the two strings anagrams, we consider this number to be -1. For example:

tea and ate are anagrams, so we would need to modify a minimum of 0 characters.
tea and toe are not anagrams, but we can modify a minimum of 1 character in either string to make them anagrams.
act and acts are not anagrams and cannot be converted to anagrams because they contain different numbers of characters, so the minimum number of characters to modify is -1.
Complete the function from the provided code. It has two parameters:

An array of n strings, a.
An array of n strings, b.
The function must return an array of integers where each element i denotes the minimum number of characters you must modify to make ai and bi anagrams; if it’s not possible to modify the existing characters in a[i] and b[i] to make them anagrams, element i should be -1 instead.

Note: You can only modify existing characters in the strings, you cannot delete or append characters to change a string’s length.

Input Format

The provided code reads the following input from stdin and passes it to the function:

The first line contains an integer, n, denoting the number of elements in a.

Each line i of the n subsequent lines contains an integer describing a[i].

The next line contains an integer, n, denoting the number of elements in b.

Each line i of the n subsequent lines contains an integer describing b[i].

Constraints

Each string consists of lowercase English alphabetic letters (i.e., a to z).
1 ≤ n ≤ 100
It is guaranteed that a and b contain the same number of elements.
0 ≤ length of a[i], length of b[i] ≤ 10^4
1 ≤ length of a[i] + length of b[i] ≤ 10^4
Output Format

The function must return an array of integers where each element i denotes the minimum number of characters you must modify to make a[i] and b[i] anagrams; if it’s not possible to modify the existing characters in a[i] and b[i] to make them anagrams, element i should be -1 instead. This is printed to stdout by the provided code.

Sample Input 0

5
a
jk
abb
mn
abc
5
bb
kj
bbc
op
def
Sample Output 0

-1
0
1
2
3
Explanation 0

Given a = [a, jk, abb, mn, abc] and b = [bb, kj, bbc, op, def], we perform the following n = 5 calculations:

Index 0: a and bb cannot be anagrams because they contain different numbers of characters, so we return -1 at this index.
Index 1: jk and kj are already anagrams because they both contain the same characters at the same frequencies, so we return 0 at this index.
Index 2: abb and bbc differ by a minimum of one character, so we return 1 at this index.
Index 3: mn and op differ by a minimum of two characters, so we return 2 at this index.
Index 4: abc and def differ by a minimum of three characters, so we return 3 at this index.
After checking each pair of strings, we return the array [-1, 0, 1, 2, 3] as our answer.

Crossover multiple choice tests: aptitude test and technical test

Recently I participated in Crossover Senior Architect Tournament.

cr4f

After the first problem there were two multiple choice tests: Aptitude test and technical test. Aptitude test had questions about English mistakes, logical puzzles and something else. Technical test had questions about selected track (java or ruby).

I became a leader just after those two multiple choice tests.

Two participants with lowest scores were disqualified after three rounds.

cr3f

 

Crossover problem: Longest Even Length Word

Recently I participated in Crossover Senior Architect Tournament. The very first problem was scored in 50 points and it was very simple. More than 7 participants were able to solve this problem. I was able to solve this problem in both languages: java and ruby however I didn’t receive the double points for that.

crossoverf

crossover1f

The problem description is below.

Longest Even Length Word

Consider a string, sentence, of space-separated words where each word is a substring consisting of English alphabetic letters only. We want to find the first word in sentence whose length is both even (i.e., contains an even number of characters) and greater than or equal to the length of any other word in the sentence. For example, if sentence is Time to write great code, then the word we’re looking for is Time because it’s the first word with a maximal even length; if sentence is Write code for a great time, then the word we’re looking for is code because it’s the first word with maximal even length.

Complete the function from the provided code. It has one parameter: a string, sentence. The function must return a string denoting the longest even length word in sentence. If there are two such words having the maximum even length, return the word that appears first in sentence; if none of the words in sentence are even in length, return 00 instead.

Input Format

A single line of space-separated strings denoting sentence.

Constraints

1 ≤ length of sentence ≤ 10^5
The sentence string consists of spaces and English alphabetic letters (i.e., a through z and A through Z) only.
Output Format

Return a string denoting the longest even length word in sentence.

Sample Input 0

It is a pleasant day today
Sample Output 0

pleasant
Explanation 0

The sentence is It is a pleasant day today. It has three even length words: It (with length 2), is (with length 2), and pleasant (with length 8). We then return the longest of these strings, which is pleasant.

Sample Input 1

You can do it the way you like
Sample Output 1

like
Explanation 1

The sentence is You can do it the way you like. It has three even length words: do (with length 2), it (with length 2), and like (with length 4). We then return the longest of these strings, which is like.

QR 2014 Magic Trick (Problem A) analysis

Tags

, , , ,

Welcome again to my Code Jam analysis!

Today I am going to explain you Magic Trick (Problem A) from Qualification Round which took place in last Saturday. There is a link to description here.
So, this problem is quite simple, all you need to do is to calculate an intersection of two sets. If these sets are disjoint then you should output “Volunteer cheated!”.
If these sets have more than one common element then you should output “Bad magician!”. Otherwise, that is, if sets have exactly one common element then you should output that element.
I want to discuss implementation of solution this problem in different languages.
For example, Delphi has built-in type called Set and built-in operation * (multiplication star sign) to calculate intersection of two sets and your program could look like following

program MagicTrick;

{$APPTYPE CONSOLE}

{$R *.res}

uses
System.SysUtils;

var
f, g: TextFile;
answer: String;
T, a1, a2: Byte;
deck1, deck2: array[0..3, 0..3] of Byte;

procedure ReadData;
var
i, j: Byte;
begin
Readln(f, a1);
for i := 0 to 3 do  begin
for j := 0 to 3 do
Read(f, deck1[i, j]);
Readln(f);
end;
Readln(f, a2);
for i := 0 to 3 do  begin
for j := 0 to 3 do
Read(f, deck2[i, j]);
Readln(f);
end;
end;

type
TByteSet = Set Of Byte;
function len(s: TByteSet; out element: Byte): Byte;
var
i: Byte;
begin
Result := 0;
for i := 1 to 16 do
if i in s then begin
Inc( Result );
element := i;
end;
end;

procedure ProcessData;
var
i, e: Byte;
s1, s2, s: TByteSet;
begin
s1 := [];
s2 := [];
for i := 0 to 3 do
Include(s1, deck1[a1 – 1, i]);
for i := 0 to 3 do
Include(s2, deck2[a2 – 1, i]);
s := s1 * s2;
case len(s, e) of
1: answer := IntToStr(e);
0: answer := ‘Volunteer cheated!’;
else answer := ‘Bad magician!’;
end;
end;

procedure OutputVerdict(casenum: Word);
begin
writeln(g, ‘Case #’, casenum, ‘: ‘, answer);
end;

var
i: Word;
s, sout: String;

begin
try
s := ParamStr(1);
if (s = ”) then begin
s := ‘input.txt’;
sout := ‘output.txt’;
end else
sout := StringReplace(s, ExtractFileExt(s), ‘o.txt’, []);
AssignFile(f, s);
Reset(f);
AssignFile(g, sout);
Rewrite(g);
try
Readln(f, T);
for i := 1 to T do begin
ReadData;
ProcessData;
OutputVerdict(i);
end;
finally
CloseFile(f);
CloseFile(g);
end;
Readln;
except
on E: Exception do begin
Writeln(E.ClassName, ‘: ‘, E.Message);
readln;
end;
end;
end.

If you wanted to implement this on C++ then you would have to write more characters to calculate sets intersection like following

#include <iostream>
#include <fstream>
#include <string>

#include <algorithm>
#include <set>
#include <iterator>

using namespace std;

int a1, a2;
int deck1[4][4], deck2[4][4];

string solve() {
set<int> s1;
set<int> s2;
set<int> intersect;

for ( int i = 0; i < 4; i++)
s1.insert(deck1[a1 – 1][i]);
for ( int i = 0; i < 4; i++)
s2.insert(deck2[a2 – 1][i]);

set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));
switch (intersect.size()){
case 1:
return to_string(static_cast<long long>(*intersect.begin()));
break;
case 0:
return “Volunteer cheated!”;
break;
default:
return “Bad magician!”;
}
}

int main(int argc, char* argv[]) {
string inputFile = (argc > 1) ? argv[1] : “input.txt”;
string outputFile = (argc > 2) ? argv[2] : (argc > 1) ? (inputFile + “out.txt”) : “output.txt”;
ifstream in;
ofstream out;
in.open(inputFile);
out.open(outputFile);

int tests;
in >> tests;
for (int test = 1; test <= tests; ++test) {
out << “Case #” << test << “: “;
// Grab input
in >> a1;
for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
in >> deck1[i][j];
}
}
in >> a2;
for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
in >> deck2[i][j];
}
}
// Solve the problem and give feedback to the end user;
out << solve() << endl;
cerr << “: ” << test << endl;
}

in.close();
out.close();

cout << inputFile << ‘\n’ << outputFile << ‘\n’;
cin.get();
return 0;
}

As for me, it seems quite annoying that you have to write all of this stuff

set_intersection(s1.begin(),s1.end(),s2.begin(),s2.end(), std::inserter(intersect,intersect.begin()));

to perform a simple set intersection operation. I used to put just some sign between two sets variable to get such result.

To perform a set intersection in Java you can call retainAll method on one set passing another set as argument, it will modify first source to contain intersection of both sets:

s1.retainAll(s2);

and the whole solution could look like following:

import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.logging.Level;
import java.util.logging.Logger;

public class pa {

private static int a1, a2;
private static int deck1[][], deck2[][];

public static void main(String[] args) {
String inputFile = (args.length > 0) ? args[0] : “input.txt”;
String outputFile = (args.length > 1) ? args[1] : (args.length > 0) ? (inputFile + “out.txt”) : “output.txt”;
try {
Scanner sc = new Scanner(new FileReader(inputFile));
PrintWriter pw = new PrintWriter(outputFile);

int n = sc.nextInt();
sc.nextLine();
for (int c=0; c<n; c++) {
Read(sc);
System.out.println(“Test case ” + (c+1) + “…”);
pw.print(“Case #” + (c+1) + “: “);
pw.print(solve());
pw.println();
}
pw.flush();
pw.close();
sc.close();
} catch (FileNotFoundException ex) {
Logger.getLogger(pa.class.getName()).log(Level.SEVERE, null, ex);
}
}

private static void Read(Scanner sc) {
a1 = sc.nextInt();
deck1 = new int[4][4];
deck2 = new int[4][4];
for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
deck1[i][j] = sc.nextInt();
}
}
a2 = sc.nextInt();

for ( int i = 0; i < 4; i++ ) {
for ( int j = 0; j < 4; j++ ) {
deck2[i][j] = sc.nextInt();
}
}
}

private static String solve() {
Set<Integer> s1 = new HashSet<Integer>();
Set<Integer> s2 = new HashSet<Integer>();

for ( int i = 0; i < 4; i++)
s1.add(deck1[a1 – 1][i]);
for ( int i = 0; i < 4; i++)
s2.add(deck2[a2 – 1][i]);

s1.retainAll(s2);
switch (s1.size()) {
case 1:
return String.valueOf(s1.iterator().next());
case 0:
return “Volunteer cheated!”;
default:
return “Bad magician!”;
}
}

}

The language I enjoy the most is definitely Python. First, you can perform set intersection just using symbol “&”, it is pretty convenient and reminds Delphi usability. Second, the final code is incredibly short and elegant in comparison to any languages mentioned before in my post, just look at it:

import  sys,  copy;

a1,  a2  =  0,  0
d1,  d2  =  [[]]*2

def  solve():
        s1  =  set(d1[a1  –  1]);
        s2  =  set(d2[a2  –  1]);
        s  =  s1  &  s2
        l  =  len(s)
        return  s.pop()  if  l  ==  1  else  “Volunteer  cheated!”  if  l  ==  0  else  “Bad  magician!”;

inputFile  =    sys.argv[1]  if  (len(sys.argv)  >  1)  else  “input.txt”;
outputFile  =  sys.argv[2]  if  (len(sys.argv)  >  2)  else  (inputFile  +  “out.txt”)  if  (len(sys.argv)  >  1)  else  “output.txt”;
print  inputFile,  outputFile
file  =  open(outputFile,  “w”)

with  open(inputFile,  ‘r’)  as  f:
        t  =  int(f.readline())
        print  t
        for  i  in  range(1,  t  +  1):
                file.write(“Case  #”  +  str(i)  +  “:  “)
                a1  =  int(f.readline())
                print  a1
                d1  =  [[0  for  x  in  xrange(4)]  for  x  in  xrange(4)]
                d2  =  [[0  for  x  in  xrange(4)]  for  x  in  xrange(4)]
                for  j  in  range(4):
                        d1[j]  =  map(int,  f.readline().split())
                print  d1
                a2  =  int(f.readline())
                print  a2
                for  j  in  range(4):
                        d2[j]  =  map(int,  f.readline().split())
                print  d2
                file.write(str(solve())  +  “\n”)
file.close()

Voila, the problem is solved in four languages. If we download test samples and pass it to our program and upload output files back to google site, it would say that “Judge’s response for last submission: Correct.”
Congratulations!
Hope you liked this post.

EuroPython 2013 Captain Hammer (Problem B) analysis

Welcome again to my new blog called Code Jam analysis!

I claim that I am analyzing problems from past Code Jam competition.

In previous post I analyzed Moist (Problem A) from EuroPython 2013 competition.

Here I am going to again another problem from EuroPython 2013 which is called Captain Hammer (Problem B).
Its description is available by this link.

To solve this problem we have to solve first physical problem that lies underneath.

So we have a body which has starting velocity and distance between start point and end point.

This means we can write down motion equation.

r = r_0  + v*t – g*t^2/2

The motion is happening in one plane which means we can write down projection of this equation to horizontal and vertical axes.

r_x = r_0_x + v_x * t
r_y = r_0_y + v_y * t – g*t^2/2

We know that distance between start point and end point is D, this means r_x = D + r_0_x. Also we know that r_y = r_0_y = 0, and v_x = V cos θ and v_y = V sin θ. This gives

D = V cos θ t
0 = V sin θ t – g*t^2/2

Let’s extract t from first equation and substitute it into second equation

t = D / (V cos θ);
V sin θ = gt/2 = gD / (2V cos θ)

After moving denominator to left side of equation we will obtain

2V^2 sin θcos θ = gD

This gives

sin(2θ) = gD/V^2.

So to retrieve angle θ we have to calculate half or arcsine of gD/V^2.

However, most programming languages do not support arcsine function but support arctangent. So we need to translate this expression into arctangent form.

Let X be assigned value of gD/V^2. Then sin2θ = X, and θ = 1/2*arctan(X/sqrt(1-X^2)). Alternatively, we can use tangent half-angle formula and calculate θ as arctan( X / (1 + sqrt( 1 – X^2))).

Most programming languages return values in radians, so to convert them to values we should multiply them by 180 and divide by π.

Now we can start develop our program. Let’s use stub mentioned in previous post.

So we have to declare two global integer variables V and D, change declaration of answer to Extended (or Real or Double – it doesn’t really matter here).

var
V, D: Integer;
answer: Extended;

Procedure to read test case data would like like follows

procedure ReadData;
begin
Readln(f, V, D);
end;

And method to process test case data would look like follows

procedure ProcessData;
var
X: Extended;
begin
X := 9.8 * D / V / V;
if Abs( Abs(X) – 1 ) < 1e-10 then
answer := 45.0
else
answer := 90 / Pi * arctan( X / Sqrt( 1 – X*X)));
end;

Alternatively we have calculate angle using tangent half formula

answer := 180 / Pi * arctan( X / (1 + Sqrt( 1 – X * X)));

Also we have to slightly modify method that outputs results to prevent from showing result real number in exponential form

procedure OutputVerdict(casenum: Word);
begin
writeln(g, ‘Case #’, casenum, ‘: ‘, answer : 10 : 10);
end;

Voila, the problem is solved. If we download test samples and pass it to out problem and upload output files back to google site, it would say that “Judge’s response for last submission: Correct.”
Congratulations!

EuroPython 2013 Moist (Problem A) analysis

Tags

, , , ,

Welcome to my new blog called Code Jam analysis!
I am going to publish here analysis of certain problems from Google Code Jam competition.

Let’s start with analyzing some really simple problem.

For example, problem A from EuroPython 2013 Moist competition.

Its description is available by this link.

If we read this description we could recognize insertion sort described (visit wikipedia for more information on this).

So the simplest solution to solve this problem would be to implement insertion sort and modify it to count how many insertions have taken place.

I use as stub following code:

program blank;

{$APPTYPE CONSOLE}

{$R *.res}

uses
System.SysUtils;

var
f, g: TextFile;
answer: Int64;
T: Word;

procedure ReadData;
begin
//Readln(f, A, N);
end;

procedure ProcessData;
begin
answer := 0;
end;

procedure OutputVerdict(casenum: Word);
begin
writeln(g, ‘Case #’, casenum, ‘: ‘, answer);
end;

var
i: Word;
s, sout: String;

begin
try
s := ParamStr(1);
if (s = ”) then begin
s := ‘input.txt’;
sout := ‘output.txt’;
end else
sout := ExtractFileName(s) + ‘out.txt’;
AssignFile(f, s);
Reset(f);
AssignFile(g, sout);
Rewrite(g);
try
Readln(f, T);
for i := 1 to T do begin
ReadData;
ProcessData;
OutputVerdict(i);
end;
finally
CloseFile(f);
CloseFile(g);
end;
writeln(‘Reading finished’);
Readln;
except
on E: Exception do begin
Writeln(E.ClassName, ‘: ‘, E.Message);
readln;
end;
end;
end.

since many code jam problems have the same pattern: read T variable from input file, for each of T tests, read its data, process it and output answer.

First of all, we can write or copy from wikipedia naive implement of insertion sort.

procedure insertsort(var a: array of integer);
var i,j,x: integer;
begin
for i := 1 to High(a) + 1 do
begin
x := a[i];
j := i – 1;
while ( j >= 0 ) and ( x < a[j] ) do
begin
a[j + 1] := a[j];
j := j – 1;
end;
a[j + 1] := x;
end;
end;

Then we can adapt it for our use case, since we have array of strings, not array of integer.

Also we have to add increment of answer variable if insertion occurs.

procedure insertsort(var a: array of String);
var
i, j: integer;
x: String;
begin
for i := 1 to High(a) do
begin
x := a[i];
j := i – 1;
        if ( j >= 0 ) and ( x < a[j] ) then
         Inc(answer);
while ( j >= 0 ) and ( x < a[j] ) do
begin
a[j + 1] := a[j];
j := j – 1;
end;
a[j + 1] := x;
end;
end;

After that we could run some tests to test if our implementation is correct.

Finally we can start solving given problem.

So, first let’s declare global string array variable and variable N for its length.

var
ar: array of String;
N: Word;

Then let’s implement ReadData method.

All we need to do is to read variable N and read string array in a “for” loop.

procedure ReadData;
var
i: Byte;
begin
Readln(f, N);
SetLength(ar, N);
for i := 0 to N – 1 do
Readln(f, ar[i]);
end;

After this let’s implement ProcessData method.

All we need to do here is initialize answer variable and call “insertSort” method.

procedure ProcessData;
begin
answer := 0;
insertsort(ar);
end;

Voila, the problem is solved. If we download test samples and pass it to out problem and upload output files back to google site, it would say that “Judge’s response for last submission: Correct.”
Congratulations!