
NOI 2005 TASKS

Overview (pdf)
Task Statements (pdf)

Overview 

Executable file 
Input file 
Output file 
Task 1: MATRIX 
MATRIX.EXE 
MATRIX.IN 
MATRIX.OUT 
Task 2: RECT 
RECT.EXE 
RECT.IN 
RECT.OUT 
Task 3: WIDTH 
WIDTH.EXE 
WIDTH.IN 
WIDTH.OUT 
Task 4: PATHS 
PATHS.EXE 
PATHS.IN 
PATHS.OUT 
Task 5: PAIR 
PAIR.EXE 
PAIR.IN 
PAIR.OUT 
Task 6: WORD 
WORD.EXE 
WORD.IN 
WORD.OUT 
Notes:
 Each task will be tested on 5 data sets.
 The maximum execution time for every task is 5
seconds.
 Each data set is worth 20 points.
 Either zero mark or full mark (20 points) is awarded
to your answer to each data set. There is
no partial credit.
 The task statements are contained on 12 pages
following this overview page.
 In the event of tie breaking, a biggernumbered task
is favoured over a smallernumbered one.


Task 1: MATRIX 
Two m × n matrices A and B
are given. Matrix B is obtained from matrix A
by rowaddition operations and columnsubtraction operations.
A rowaddition operation adds 1 to each entry of a row.
A columnaddition operation subtracts 1 from each entry of
a column.
In this task, you have to find the numbers of rowaddition
operations r_{1}, ..., r_{m}
to be applied to row 1, ..., row m of A
respectively such that the following properties hold.
 There correspond
c_{1}, ..., c_{n}
columnsubtraction operations to be applied to
column 1, ..., column n of A
respectively so that these row and column operations
transform the given matrix A to the given
matrix B.
 The number of any row and column operations is
between 0 and 9 inclusively; that is,
0 ≤ r_{i} ≤ 9,
i = 1, ..., m and
0 ≤ c_{j} ≤ 9,
j = 1, ..., n.
 The value
r_{1} ...
r_{m}, considered as an integer,
is as small as possible.
You should concatenate the values
r_{1}, ..., r_{m}
and output it as a single mdigit integer
r_{1} ... r_{m}
(with possibly leading zeros). If the given matrix
B cannot be obtained from the given matrix
A with 0 to 9 rowaddition operations on each row
and 0 to 9 columnsubtraction operations on each column,
your program should output the value 1.
Example 1
Let
The required rowadditions and columnsubtractions are
shown as:
Since there are 4 and 0 rowaddition operations for
row 1 and row 2 respectively, the required output is
40
after checking that 4 is the smallest possible number
of row operations for row 1.
Example 2
Let
The required rowadditions and columnsubtractions are
shown as:
Since there are 4, 2, and 0 rowaddition operations for
row 1, row 2, and row 3, the required output is
420
after checking that 4 is the smallest possible number
of row operations for row 1.
Example 3
Let
It can be checked that it is impossible to obtain
B from A with 0 to 9 rowadditions on
each row and 0 to 9 columnsubtractions on each column.
So the output should be 1.
Input File: MATRIX.IN
The first line contains two integers m and n
separated by a space, 1 ≤ m ≤ 100,
1 ≤ n ≤ 100.
The matrix A is given by the next m lines
for row 1 to row m. Each of these m lines
contains n integers, with a space between two
adjacent integers. Similarly, the matrix B is given
by the next m lines. Each entry of the matrices is
an integer between 1000 and 1000 inclusively.
For Example 1, the input file contains 2 3
1 2 3
4 5 6
1 0 0
0 1 1
Output File: MATRIX.OUT
The output file contains an mdigit integer.
For Example 1, the output file contains 40


Task #1 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #1 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 

Task 2: RECT 
A rectangle is axisparallel if its top and bottom
sides are parallel to the xaxis and its left and
right sides are parallel to the yaxis.
From now on by a rectangle we mean an axisparallel
rectangle.
A rectangle will be specified by a 4tuple
(x_{1}, y_{1},
x_{2}, y_{2})
in which (x_{1}, y_{1}) is
the bottomleft corner and
(x_{2}, y_{2}) is
the topright corner of the rectangle.
We will also say the rectangle
(x_{1}, y_{1},
x_{2}, y_{2})
is a
(x_{2}  x_{1}) ×
(y_{2}  y_{1}) rectangle.
Two rectangles are incomparable if neither will
fit inside the other possibly with translation and
90° rotation; otherwise, the two rectangles
are comparable. Given a list of rectangles, you are to
output the number of pairs of incomparable rectangles.
Example 1
Consider three rectangles:
 the 2 × 2 rectangle A: (0, 0, 2, 2);
 the 3 × 1 rectangle B: (0, 0, 3, 1);
 the 2 × 3 rectangle C: (1, 1, 3, 4);
Rectangle pair AB is incomparable (neither can
fit inside the other). But rectangle pair AC
is comparable (A fits inside C after a
translation), so is rectangle pair BC (B
fits inside C after a 90° rotation and a
translation).
Example 2
Consider four rectangles:
 the 1 × 3 rectangle A: (3, 3, 4, 6);
 the 3 × 1 rectangle B: (1, 2, 4, 3);
 the 2 × 2 rectangle C: (5, 6, 7, 8);
 the 2 × 2 rectangle D: (10, 10, 12, 12);
There are four incomparable rectangle pairs AC,
AD, BC, and BD. Thus the answer is
4.
Input File: RECT.IN
The first input line contains an integer which is the
number of rectangles n (where 0 ≤ n
≤ 10000). Each of the next n lines describes
a rectangle and contains four integers,
x_{1}, y_{1},
x_{2}, y_{2},
a space spearates two adjacent integers.
Recall that coordinates
(x_{1}, y_{1}),
(x_{2}, y_{2}),
specify respectively the bottomleft and topright
corner of the rectanlge. All coordinate values are
in the range of 0 to 10,000; that is,
0 ≤ x_{1} ≤ 10000,
0 ≤ y_{1} ≤ 10000,
0 ≤ x_{2} ≤ 10000,
0 ≤ y_{2} ≤ 10000.
For Example 1, the input file contains 3
0 0 2 2
0 0 3 1
1 1 3 4
Output File: RECT.OUT
The output file contains a single integer which is
the number of pairs of incomparable rectangles.
For Example 1, the output file contains 1


Task #2 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #2 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 

Task 3: WIDTH 
We consider a set S of n points in a
plane. The width w of S is the minimum
distance between two parallel lines that enclose S.
Figure 1: The width w of a set of three points.
For instance, in Figure 1, the set S consists
of n = 3 points (0,0), (0,3) and (3,0). The
width is achieved by the two lines l and
l', their distance is
In this task, you are given a set of points in the input
file and you need to compute the integer part of
w^{2} and write it in the output file.
For instance, in Figure 1, we have
so w^{2} = 4.5, and thus you need to
output the integer part of 4.5, which is 4.
We give you a useful formula to help you solve this
problem. Let
A = (x_{a}, y_{a}),
B = (x_{b}, y_{b}), and
C = (x_{c}, y_{c})
be three points. The height h (see Figure 2) of
the triangle ABC is given by the following
formula
Where s = 1 if ABC
is counterclockwise (as in Figure 2) and
s = 1 if ABC
is clockwise.
Figure 2: Triangle ABC.
Clearly, if all the points of S lie on a straight
line, the width w is zero.
Input File: WIDTH.IN
The first input line contains the integer n,
the number of points in S. Each of the next
n lines contains the x coordinate and
the y coordinate of an input point separated
by a space. For instance, the point set in Figure 1
corresponds to the following input file: 3
0 0
3 0
0 3
Note that the coordinates of the points are integers
ranging from 0 to 199 inclusively. There are at most
100,000 input points. A point may appear several times
in the input file. For instance, the following input
file is possible: 4
0 0
3 0
0 3
3 0
In this case, the answer to the problem is still 4.
Output File: WIDTH.OUT
The output file should contain the integer part of
w^{2}. For instance, the output file
for the point set in Figure 1 is: 4


Task #3 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #3 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 

Task 4: PATHS 
A graph is made up of a set of nodes and a set of links.
A link connects two nodes. For example, Figure 1 shows a
simple graph with 4 nodes and 5 links. In the figure,
each link has a specific direction, going from the
originating node to the destination node. Each link
has a cost attached to it. The m nodes of a graph
are identified by the integers 0, 1, ..., m  1.
Figure 1
Figure 2
A path connects one node to another, following the
direction of links from node to node. The length
of a path is the number of links used. The cost of a
path is the sum of link cost over the entire path.
For a given graph, your task is to find the minimum
cost among the costs of all the shortest paths between
Node 0 and Node 1. A shortest path with the minimum cost
is called a minimumcost shortest path.
For example, again consider Figure 1. The shortest path
for Node 0 to Node 1 is the 1link path 0 > 1 with
a path cost of 10. While there are cheaper paths:
0 > 2 > 1 and 0 > 3 > 1, they are longer (2 links).
Therefore, 0 > 1 is the minimumcost shortest path.
Consider another example, Figure 2. There are two shortest
paths of length 2, the path 0 > 3 > 1 has a lower
cost (cost = 4) than the path 0 > 2 > 1 (cost = 5).
Another path 0 > 2 > 3 > 1 (cost = 3) is cheaper but
longer. Therefore, the minimumcost shortest path is
0 > 3 > 1.
Input File: PATHS.IN
The first line contains two integers m and
n separated by a space, where m is the
number of nodes and n is the number of links.
The links of the graph and their costs are given by
the next n lines. Each line has three integers
(with a space between two adjacent integers), denoting
SourceNode DestinationNode LinkCost.
For example, the input data for the graph in Figure 1
is: 4 5
0 2 2
0 3 2
0 1 10
2 1 2
3 1 2
There are at most 100 nodes, and nodes are numbered
from 0 to 99. There are at most 1000 links and link cost
varies between 0 and 2^{15}  1.
Output File: PATHS.OUT
The output file contains a single integer which is the
path cost of a minimumcost shortest path from Node 0
to Node 1. For example, the output file of Figure 1
contains 10
Note that while there may be multiple minimumcost
shortest paths, the cost of these paths are the same.


Task #4 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #4 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 

Task 5: PAIR 
A popular solitaire board game is played on a rectangular
m × n game board consisting of
mn squares. The board initially comes entirely
populated with either animals or obstacles. An 'X'
in a square denotes an obstacle, a digit '0''9' in
a square denotes the species of the animal.
Pairs of animals can only be removed if they are of
the same species. If a pair of animals are removed, the
squares in which they were located become empty and
stay empty for the rest of the game. To be removed, a
candidate pair must either be adjacent to each other
or have a path between them. Two squares are adjacent
if they are side by side horizontally or vertically.
A path is a sequence of adjacent empty squares.
The path length of a path is simply the number of
empty squares in the path.
You should output the maximal number of pairs of animals
it can remove from the board and the minimal cumulative
path length needed to achieve this.
Example 1
Consider a 3 × 4 board with the following
configuration:
The two animals of species 1 can be removed because
they are adjacent and the path length between them is 0.
After their removal, there is a path of length 2 between
the two animals of species 0, thus these two animals can
be removed too. To remove these two pairs of animals,
the cumulative path length is 0 + 2 = 2. This is also the
minimal cumulative path length as there is only one way
to remove both pairs of animals. Thus the answer is 2 2.
Example 2
Consider a 4 × 1 board with the following
configuration:
If we first remove the two middle animals of species 9
and then remove the top and bottom animals of species 9,
two pairs of animals are removed with a cumulative path
length 0 + 2 = 2.
But we can remove the top two animals of species 9 and
then remove the bottom two animals of species 9. This
also removes two pairs of animals with a cumulative
path length 0 + 0 = 0.
Clearly a zero cumulative path length is minimal.
Thus the answer is 2 0.
Input File: PAIR.IN
The first line of the input file contains the integers
m and n separated by a space,
1 ≤ m ≤ 5, 1 ≤ n ≤ 5.
Each of the subsequent m lines contains
n characters, each character is one of
'X', '0', '1', ..., '9'. There is no space between
adjacent characters.
For Example 1, the input file looks like: 3 4
XX0X
X11X
X0XX
Output File: PAIR.OUT
The output file contains two integers separated by a
space. The first integer is the maximal number of pairs
of animals that can be removed. The second integer is
the minimal cumulative path length needed to achieve
the maximal number of pairs.
For Example 1, the output file contains: 2 2


Task #5 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #5 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 

Task 6: WORD 
Consider a set of k strings
{ S_{1},
S_{2}, ...,
S_{k} }
where every character used in the k strings
is either a space or any of hte 26 characters in
{ 'a', 'b', 'c', ..., 'z' }. For some constants
l and d, our aim is to compute an
(l, d)pattern for
{ S_{1},
S_{2}, ...,
S_{k} }.
An (l, d)pattern is a lengthl
string W = W[1]W[2] ...
W[l] which satisfies teh following
property:
 For every string S_{i}
(i = 1, 2, ..., k), there
exists a lengthl substring
X = X[1]X[2] ...
X[l] of S_{i}
such that the hamming distance of X
and W is less than or equal to d.
(The hamming distance of X and W
is the number of pairs of
(X[j], W[j]) such that
X[j] ≠ W[j]) for
j = 1, 2, ..., l.)
In this task, you are given numbers l and d
and a set of strings; you need to compute an
(l, d)pattern for the given set of strings.
You can assume that an
(l, d)pattern exists and is unique.
Example 1
Consider the following 3 strings, the corresponding
(3,0)pattern is "oil".
 oil is expensive
 we have three oilers
 be more oily
Example 2
Consider the following 4 strings, the corresponding
(5,1)pattern is "apple".
 you have two applas
 i am an ppple
 we are acples
 adples are good for health
Input File: WORD.IN
The first line contains two integers
l and d separated by a space, where
1 ≤ l ≤ 10, 0 ≤ d ≤ 2.
The second line contains the integer k, where
1 ≤ k ≤ 30.
The remaining k lines contain the k
strings
S_{1},
S_{2}, ...,
S_{k}.
(Each string is of length at most 50). For Example 2,
the input file looks like: 5 1
4
you have two applas
i am an ppple
we are acples
adples are good for health
Output File: WORD.OUT
The output file contains a string of length l.
For Example 2, the output file looks like: apple
This string represents an
(l, d)pattern for the set of strings
and l and d given in the input file.
The input is always such that there exists exacly
one (l, d)pattern.


Task #6 Input files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 
Task #6 Output files: 
[ Set #1 
Set #2 
Set #3 
Set #4 
Set #5 ] 


Design by 
