Regional Finals - Rochester Institute of Technology

ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 1: Avoidland
Avoidland is a puzzle played on an n × n board with n pawns. The pawns are initially placed
on the squares of the board, at most one pawn per square. The goal is to move the pawns
so that they “avoid” each other – there cannot be a row or a column with more than one
pawn. In one move a pawn can move to a neighboring unoccupied square, that is, a square
that shares a side with the pawn’s current location and there is no pawn on it. Given the
initial locations of the pawns, what is the minimum number of moves needed to solve the
puzzle?
Input specification:
The first line contains k, the number of Avoidland puzzles. Each Avoidland puzzle is described on several lines. The first line contains n, then n lines follow. The i-th line contains
the initial row and column coordinates of the i-th pawn, separated by space. Each coordinate
is an integer between 1 and n. You may assume that n is at most 1,000,000.
Output specification:
The output contains one line for each Avoidland puzzle. The line contains the minimum
number of moves needed to solve the puzzle.
Sample input:
2
3
1 3
2 3
3 1
4
1
4
1
4
4
1
1
4
Sample output:
1
4
Explanation:
For sample input 1, we can move the second pawn to location (2,2). For sample input 2, we
can move the first pawn to location (1,3), then to location (2,3), and then move the second
pawn to location (3,1), then to location (3,2).
1
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 2: Brick Wall
Pat and Mat are trying to build a brick wall. They have three types of bricks – all have
the same depth and height but they are of three diﬀerent widths: 1, 2, and 3. As every
builder knows (and Pat and Mat learned after watching their walls fall down quite a few
times), a wall is built by layering rows of bricks, with the added requirement that for any
two neighboring bricks there has to be a brick above that covers the connection of the two
bricks (unless the bricks are in the top-most row). Pat and Mat somehow managed to build
quite a few rows and now they are about to do the last row. But they are having troubles
ﬁguring out whether it is possible to build the last row so that all connections in the row
below are covered. Of course, all the rows have to be of the same length and aligned on the
sides. Help!
Input specification:
The ﬁrst line contains k, the number of diﬀerent walls that need to be ﬁnished. Then 2k
lines follow, where every wall is described on two lines. The ﬁrst of these lines contains
four numbers N, c1 , c2 , c3 , separated by spaces, where N is the number of bricks in the
(currently) top-most row and ci describes the number of bricks of width i for i = 1, 2, 3 that
are available for the last row. The second line describes the currently top-most row – it
contains a sequence b1 , b2 , . . . , bN of brick lengths for the bricks that form the row, in the
order given by the sequence. You may assume that N is at most 100 and each of c1 , c2 , and
c3 is at most 300.
Output specification:
The output contains one line for each wall. The i-th line contains the string ”YES” if it is
possible to build the last row for the i-th brick wall, and ”NO” otherwise.
Sample input:
3
5
2
5
2
5
2
2
3
1
3
6
3
1
1
2
1
1
1
3
3 2
3
3 2
1
2 3
Explanation:
For the ﬁrst sample input, a possible solution
is shown in the ﬁgure below, with one brick
of length 2 unused.
Sample output:
YES
NO
NO
1
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 3: Cake
ˇ
Zofka
really likes cakes. Her most recent favorite is a rectangular-shaped cake with hard
chocolate glazing and white marzipan roses on top. The glazing has been pre-cut in a gridlike pattern at the bakery since this type of glazing is diﬃcult to cut after it hardens. The
bakers pride themselves in creating various creations with the roses – they place every rose
in the middle of one of the grid squares (at most one rose per square) but the placement
ˇ
diﬀers each time. Zofka
invited her friends to share the cake with her - together with her
there are as many people as there are roses on the cake as she and each of her friends like
ˇ
a piece with a rose. Zofka
can cut only rectangular pieces of the cake along the grid lines.
How should she cut the cake so that she and each of her friends gets a rectangular piece with
a rose and there is the smallest possible amount of leftover cake?
Input specification:
The ﬁrst line contains k, the number of cakes. Each cake is described on several lines. The
ﬁrst line contains p, q, and n, where p × q are the dimensions of the cake and n is the number
of roses. Then n lines follow, the i-th line contains the coordinates of the i-th rose, where
the ﬁrst coordinate is between 1 and p and the second coordinate is between 1 and q. You
may assume that p and q are at most 10,000.
Output specification:
The output contains n + 1 lines for each cake. The ﬁrst n lines contain four numbers each:
the j-th line contains aj , bj , cj , dj , where 1 ≤ aj ≤ cj ≤ p and 1 ≤ bj ≤ dj ≤ q and (aj , bj )
and (cj , dj ) correspond to the grid squares at the opposite corners of the rectangular piece for
the j-th person. The rectangular pieces have to be non-overlapping. The last line contains
a single number, the area of the leftovers. The area of the leftovers should be the smallest
possible.
Sample input:
Explanation:
1
4
2
3
1
4
A possible solution for the sample input is
shown in the ﬁgure below. The rectangular
pieces cover the cake entirely, so there are no
leftovers. This solution is described in the
sample output. Note that there are several
other correct outputs for the sample input.
5 4
2
4
4
5
Sample output:
1
3
3
1
0
1
1
5
4
2
4
4
2
3
4
5
5
1
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 4: Cover up
Dezider is making a game board for the game of Convexity. He drilled a bunch of holes in
a piece of wood. As the name of the game suggests the holes were on the boundary of a
convex polygon. After turning over the piece of wood, Dezider froze—he had damaged the
famous Picasso lithograph—The Bull No. 8. Now the question is: how to fix the damage?
Drawing a bunch of straight lines to cover the holes seems like a good repair method but,
of course, Dezider would like to draw as few lines as possible. He needs your help. Write
a program that, given the positions of the holes, finds the smallest number of straight lines
that can cover the holes.
Input specification:
The first line contains k, the number of problems. Each of the next k lines contains a description of one problem. The line starts with n, the number of holes. Then 2n numbers, the
coordinates of the holes, follow. You can assume n ≤ 1,000 and the coordinates are integers
between -1,000,000 and 1,000,000. The holes lie on the boundary of a convex polygon.
Output specification:
The output contains one line for each problem. The line for the i-th problem contains the
smallest number ℓ, such that ℓ straight lines can cover the holes.
Sample input:
2
4 0 0 1 1 1 0 0 1
8 0 0 2 2 0 2 2 0 1 0 1 2 0 1 2 1
Sample output:
2
3
1
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 5: Hopper
A hopper is a virtual creature that visits Java programs and explores their arrays. Scientists
observed a hopper and came to the following conclusions:
• a hopper only visits arrays with integer entries,
• a hopper always explores a sequence of array elements using the following rules:
– a hopper cannot jump too far, that is, the next element is always at most D
indices away (how far a hopper can jump depends on the length of its legs),
– a hopper doesn’t like big changes in values—the next element diﬀers from the
current element by at most M , more precisely the absolute value of the diﬀerence
is at most M (how big a change in values a hopper can handle depends on the
length of its arms), and
– a hopper never visits the same element twice.
• a hopper will explore the array with the longest exploration sequence.
The scientists now need to prepare arrays for further study of hoppers and they need your
help. They want a program that given an array and values D and M computes the length
of the longest exploration sequence in the array.
Input specification:
The ﬁrst line contains k, the number of problems. Then descriptions of the problems follow.
Each problem is described on two lines. The ﬁrst line of a problem description contains three
numbers n, D, M , where n is the length of the array (as described above, D is the maximum
length of a jump the hopper can make, and M is the maximum diﬀerence in values a hopper
can handle). The next line contains n integers—the entries of the array. We have 1 ≤ D ≤ 7,
1 ≤ M ≤ 10, 000, 1 ≤ n ≤ 10, 000 and the integers in the array are between −1, 000, 000
and 1, 000, 000.
Output specification:
The output contains one line for each problem—the length of the longest exploration sequence. The hopper can start and end at any location and the length is computed as the
number of visited locations.
Sample input:
Sample output:
3
8
1
8
1
8
1
8
3
2
3
7
2
7
1
7
1
8 2 6 4 3 5
1
8 2 6 4 3 5
1
8 2 6 4 3 5
1
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 6: Origami
Filip found a pile of square origami papers. In preparation for winter, and partly because he
did not really know what origami is, he decided to cut the papers into smaller pieces, place
the pieces on the blades of his ceiling fan, and turn the fan on. (He has a loft bed so he can
reach the ceiling fan easily.) As the pieces blew away, he watched it “snow”, over and over.
Now Filip is a little older, wiser, and he needs to clean his room. As he is picking up
the pieces of cut paper, he notices that there are nice patterns on them. He sorts them by
patterns and now he would like to tape them back together the way they used to be. Each
paper was a square, though the squares were of several diﬀerent sizes. The trouble is, Filip
is not sure if he found all the pieces! Help him ﬁgure out whether he can form a square out
of the pieces he got.
Each piece is a polygon (Filip is very proud of his straight-line cutting abilities) and
each piece originally touched the boundary of the square. Filip remembers that he cut each
square into at most 5 pieces. To form a square, the pieces cannot overlap. The patterns on
the pieces allow us to orient them so that it is suﬃcient to consider only 90 degree rotations;
however, you may need to ﬂip some pieces over.
Input specification:
The ﬁrst line contains k, the number of diﬀerent origami patterns. The pieces for each pattern
are described on several lines. The ﬁrst line is empty, followed by a line that contains n,
the number of paper pieces of the current pattern. Then 2n lines follow. The (2i − 1)-st
line contains pi , the number of vertices of the i-th polygon piece. The (2i)-th line contains
coordinates x1 , y1 , x2 , y2 , . . . , xpi , ypi . The coordinates represent the polygon – traversing
through the points outlines the shape of the polygon (counterclockwise). You may assume
that such traversal will be non-self-crossing.
The number of pieces n is at most 5, every polygon has at most 30 vertices, and the
coordinates are integers between -10 and 10.
Output specification:
The output contains one line for each origami pattern. The line contains the word “YES” if
it is possible to ﬁt the pieces together to form a square, and “NO” otherwise.
Sample input:
3
6
1 1 1 5 0 5 0 3 -1 3 -1 1
6
0 0 2 0 2 4 0 4 1 3 0 2
5
-1 -1 1 -1 1 0 0 1 -1 0
1
3
4
0 0 1 0 1 4 0 4
3
3 3 7 3 7 6
3
3 3 7 3 7 6
2
6
0 1 4 1 4 0 5 0 5 4 0 4
6
0 0 5 0 5 1 2 1 2 2 0 2
Sample output:
YES
YES
NO
Explanation:
Figures corresponding to the three sample inputs are below.
Sample input 1:
Sample input 2:
Sample input 3:
2
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 7: Rebel Die
The rebel die needs to escape from the board prison. To accomplish the escape it needs
to blend in with the board on its way. Unfortunately, the guards colored the board using
various colors and ﬁguring out the correct camouﬂage seems very diﬃcult. The die is trying
to get from the top-left corner square to the bottom-right corner square. Fortunately, its
sides are of the same size as the squares of the grid and each grid square is colored by a
single color. The die wants to color its sides to blend in. The only moves it can do is to
ﬂip (along an edge) onto one of the neighboring squares (for most squares there are four
neighboring squares). To go unnoticed the top color of the die must always match the color
of the square on which it is (in particular, in the starting position the top color of the die
must match the color of the top-left corner square and in the ﬁnal position the top color of
the die must match the color of the bottom-right corner square). The die cannot do any
other moves (for example, it cannot rotate on a square). Please help the die to ﬁgure out if
a good camouﬂage exists.
Input specification:
The ﬁrst line contains k, the number of boards. Each board is described on several lines.
The ﬁrst line contains two integers m (the height of the board) and n (the width of the
board). Then m lines follow. Each of the m lines contains n integers. Each integer encodes
a color. Assume that 1 ≤ m, n ≤ 100 and the colors are integers from {0, 1, . . . , 29}.
Output specification:
The output contains one line for each board. The line for a board contains “YES” if there
exists a coloring of the die that allows the die to ﬂip from the top-left corner square (the
square in ﬁrst column of the ﬁrst row) to the bottom-right corner square (the square in the
last column of the last row) on that board. If such a coloring does not exist then the line
contains “NO”.
Sample input:
2
4
0
0
2
5
4
0
1
2
3
4
1
4
4
6
4
1
2
3
4
2
0
1
7
3
0
4
8
2
3
4
5
3
4
5
6
1
Sample output:
YES
NO
Explanation:
For the ﬁrst sample input, the coloring for the rebel die is shown below on a cube net. This
is the only camouﬂage that allows the die to get from the top-left corner to the bottom-right
corner and there is only one way how to do so.
0
0
2
5
4
1 0 2 8
3
2
1
4
4
6
2
0
1
7
3
0
4
8
ACM ICPC: The Northeast North America Regional Final
Rochester Institute of Technology, November 15, 2014
Problem 8: Sheep Pen
David and Martin retired from their jobs and became shepherds. After each winter they
need to rebuild the sheep pen. Each year they have a diﬀerent collection of straight fence
segments of various lengths. Naturally, they want to build a sheep pen that covers the largest
area. They always spend a lot of time choosing, rearranging, and placing the segments but
they are never sure whether they got the optimal solution. Please help them.
Input specification:
The ﬁrst line contains k, the number of years. Then k lines follow. Each line starts with n,
the number of fence segments and then contains a list of n integers, the lengths (in meters)
of the fence segments. The lengths are integers between 1 and 100. The number of fence
segments n is between 3 and 50.
Output specification:
The output contains one line for each year. The line for year i contains the maximum area
(in square meters) of a polygon whose sides have lengths given by the input for the i-th year.
Not all segment lengths listed need to be used. The answers should be output with precision
of two decimal places (rounded to the nearest number with two decimal digits). If no sheep
pen can be built, output 0.00.
Sample input:
3
4 1 1 1 1
3 1 1 1
5 1 1 2 2 7
Sample output:
1.00
0.43
2.00
1

Download Report