Home
18th NOI
Committee
Eligibility
Rules & Regulations
Programme
Coding Environment
Instructions (PDF)
About NOI
About NOI
Acknowledgment
About IOI
Competition
Problem Sets
Results
Support
Contacts

Tasks Archive : 13 | 12 | 11 | 10 | 09 | 08 | 07 | 06 | 05 | 05 (Prelim) | 04 | 03 | 02 | 01 | 00 | 99 | 98

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:
  1. Each task will be tested on 5 data sets.
  2. The maximum execution time for every task is 5 seconds.
  3. Each data set is worth 20 points.
  4. Either zero mark or full mark (20 points) is awarded to your answer to each data set. There is no partial credit.
  5. The task statements are contained on 12 pages following this overview page.
  6. In the event of tie breaking, a bigger-numbered task is favoured over a smaller-numbered one.

Task 1: MATRIX
Two m × n matrices A and B are given. Matrix B is obtained from matrix A by row-addition operations and column-subtraction operations. A row-addition operation adds 1 to each entry of a row. A column-addition operation subtracts 1 from each entry of a column.

In this task, you have to find the numbers of row-addition operations r1, ..., rm to be applied to row 1, ..., row m of A respectively such that the following properties hold.
  • There correspond c1, ..., cn column-subtraction 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 ≤ ri ≤ 9, i = 1, ..., m and 0 ≤ cj ≤ 9, j = 1, ..., n.
  • The value r1 ... rm, considered as an integer, is as small as possible.
You should concatenate the values r1, ..., rm and output it as a single m-digit integer r1 ... rm (with possibly leading zeros). If the given matrix B cannot be obtained from the given matrix A with 0 to 9 row-addition operations on each row and 0 to 9 column-subtraction operations on each column, your program should output the value -1.

Example 1
Let

The required row-additions and column-subtractions are shown as:

Since there are 4 and 0 row-addition 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 row-additions and column-subtractions are shown as:

Since there are 4, 2, and 0 row-addition 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 row-additions on each row and 0 to 9 column-subtractions 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 m-digit 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 axis-parallel if its top and bottom sides are parallel to the x-axis and its left and right sides are parallel to the y-axis. From now on by a rectangle we mean an axis-parallel rectangle.

A rectangle will be specified by a 4-tuple (x1, y1, x2, y2) in which (x1, y1) is the bottom-left corner and (x2, y2) is the top-right corner of the rectangle. We will also say the rectangle (x1, y1, x2, y2) is a (x2 - x1) × (y2 - y1) 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, x1, y1, x2, y2, a space spearates two adjacent integers. Recall that coordinates (x1, y1), (x2, y2), specify respectively the bottom-left and top-right corner of the rectanlge. All coordinate values are in the range of 0 to 10,000; that is, 0 ≤ x1 ≤ 10000, 0 ≤ y1 ≤ 10000, 0 ≤ x2 ≤ 10000, 0 ≤ y2 ≤ 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 w2 and write it in the output file. For instance, in Figure 1, we have so w2 = 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 = (xa, ya), B = (xb, yb), and C = (xc, yc) 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 w2. 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 minimum-cost shortest path.

For example, again consider Figure 1. The shortest path for Node 0 to Node 1 is the 1-link 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 minimum-cost 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 minimum-cost 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 Source-Node Destination-Node Link-Cost.

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

Output File: PATHS.OUT
The output file contains a single integer which is the path cost of a minimum-cost 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 minimum-cost 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 { S1, S2, ..., Sk } 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 { S1, S2, ..., Sk }. An (l, d)-pattern is a length-l string W = W[1]W[2] ... W[l] which satisfies teh following property:
  • For every string Si (i = 1, 2, ..., k), there exists a length-l substring X = X[1]X[2] ... X[l] of Si 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 S1, S2, ..., Sk. (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 Techsailor Group