ACM-ICPC Asia Phuket
Regional Programing Contest 2009
Sponsored by IBM
Hosted by Prince of Songkla University, Phuket Campus
4
th
November 2009
There are 11 problems (A-K) to solve within 300 minutes (5 hours).
Solve as many problems as you can, in an order of your choice.
Use C or C++ or Java to program at your convenience for any problems.
Input and output of each program are standard input and output.
Platinum Local Sponsor
ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2009 - Phuket, Thailand
1/23
Problem A
Airplane Parking
During this economic crisis time, Jack has started an incredible new business related to air
travel, a parking-lot for airplane. He bought a very large land to park airplanes. However the
land is very narrow, so that the only way airplanes can go in or go out of the parking lot must
be in the Last-In First-Out fashion (see picture below). He only has spaces in the parking lot
so he cannot take some airplane at the end out so that other airplanes can move.
Because of the limitation of the parking lot, it is not possible to accommodate all requests for
parking. Each request consists of the planned arrival time and planned departure time, which
are the times the airplane arrives at the parking lot. An example below shows a request table
for 4 planes.
Airplane Arrival Departure
1
2
3
4
1
2
3
6
10
5
7
9
In this case, it is possible to accommodate airplane 1, 2, and 4. But it is not possible to
accommodate both airplanes 2 and 3.
It is possible that different planes plan to arrive or depart the parking lot at the same time. Jack
has the best crews working with him, so that they will manage to arrange the plane to the
parking lot in the best way that if it is possible to park and take out the planes they will be able
to do it. Consider another example.
Airplane Arrival Departure
5
6
7
10
10
13
12
15
17
Although airplane 5 and 6 arrive at the same time, Jack's crews know that airplane 5 will have
to be out before airplane 6, so when both airplanes arrive they put airplane 6 in first, following
by airplane 5.
Given a list of parking requests, you want to find the maximum number of airplanes that can be
parked in this parking lot, provided that they can only depart in the Last-In First-Out fashion.
ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2009 - Phuket, Thailand
2/23
Input
The first line contains an integer
T
, the number of test cases (1 <
T
< 5). Each test case is in
the following format.
The first line starts with an integer
N
(1 <
N
< 300) denoting the number of airplanes. The next
N
lines describe the request table. Each line 1 +
i
, for 1 <
i
<
N
, contains two integer
S
i
and
T
i
,
(0 <
S
i
<
T
i
< 1,000,000,000) which are the planned arrival time and planned departing time
for airplane
i
.
Output
For each test case, you program must output a single line consisting of one integer, the
maximum number of airplanes that can be parked in Jack's parking lot.
Sample Input Sample Output
2
4
1 10
2 5
3 7
6 9
3
10 12
10 15
13 17
3
2
ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2009 - Phuket, Thailand
3/23
Problem B
Elias Omega Coding
Introduction
Elias code can be used to efficiently encode positive integers when there is no prior
information about the cardinality of the integers to be encoded and it is known that the
probability of getting a large integer is smaller than or equal to the probability of getting a small
integer. For practical reasons, however, in this contest we do pose a limit on the size of the
input integers. For the same reason we restrict the input integer to be greater than 1.
Elias developed three variants of the code: the Elias gamma, Elias delta, and Elias omega
coding methods. This problem presents the Elias gamma and Elias omega methods and calls for
implementing the Elias omega code. The following is a background, definition, and illustration
of the problem.
Background
Suppose that Alice wants to transmit a positive integer n to Bob through a binary channel
and let β n stand for the binary representation of n. If Bob knows |β(n) | (the number of bits
required for the binary representation of n) in advance, then Alice should use β(n) for the
transmission. On the other hand, if Bob does not have this information, then Alice can first send
|β(n)|, using efficient and distinguishable encoding, then she can send the actual beta code
F
1
= β (n). The end result is a two field code < F
1
,F
2
> .
Elias code and its variants differ in the way they encode these two pieces of information
(F
1
and F
2
). The main difference between variants lies in the representation of F
1
. This may
imply modifications in the representation of F
1
. In addition, some of the variants apply repetition
or recursion to the representation of F
1
. We use a specific variant specified below.
Definition
Formally, in Elias gamma coding, a positive integer n is encoded using two concatenated bit
fields. The first field, the prefix, contains [log
2
n] bits of 0 ( [x] is the floor of x). The second
field, the postfix, is the actual binary representation of n using [log
2
n]+1 bits. For example, the
binary representation of the decimal number 9 is 1001. Under Elias coding 9 is encoded as
0001001. The first three leading zeros denote that four bits are required for the binary
representation of 9. The next four bits contain the binary representation of 9. Elias delta code
applies the gamma code to the prefix([log
2
n]) of the gamma code and Elias omega code applies
a recursion over the prefix Elias gamma representation of [log
2
n].
Illustration (detailed example)
To further illustrate the Elias omega code, consider the integer 536870907. The binary
representation of this integer is 1 1111 1111 1111 1111 1111 1111 1011 which is required 29
bits. Hence, in the first step it is encoded as follows:
< F
1
,F
2
> =
< 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>
where blanks, dots, commas, and brackets, are inserted for readability.
To emphasize, for this contest the recursion stops when the first field of a recursive
stage contains one 0.
ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2009 - Phuket, Thailand
4/23
Looking at all the bits generated by all the steps and using β(n) to denote the binary
representation of n, we have:
a. <28 0’s, β(536870907)> =
< 0000 0000 0000 0000 0000 0000 0000, 1 1111 1111 1111 1111 1111 1111 1011>
b. < <4 0’s, β(28)>, β(536870907) > =
< <0000, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
c. <<<2 0’s, β(4)>, β(28)> , β(536870907) > =
< <<00, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
d. <<<<one 0, β(2)>, β(4)>, β(28)>, β(536870907 ) > =
< <<<0, 10>, 100>, 1 1100>, 1 1111 1111 1111 1111 1111 1111 1011>
Taking away all the blanks, dots, commas, and brackets we get that the Elias omega code
of 536870907 is: 0101001110011111111111111111111111111011. This code is distinguishable
(uniquely decodable). It can be decoded in a unique way and yield back the number 536870907.
Problem statement
Given some positive integers in the range of 2 – 2x10
9
, you are to write a program to produce the
Elias omega codes for these integers.
Input
The input contains positive integers each in a separate line. Each integer is in between 2 -
2,000,000,000, inclusive. The end of input is indicated by a zero. The input can contain up to one
hundred lines.
Output
The output consists of lines each corresponding to an input integer except the last zero. Each line
contains the Elias omega code of each input integer. The output should not contain any blanks or
blank lines.
Sample Input Sample Output
2
510
7
120000
536870905
49
5
0
010
0111000111111110
010111
0101001000011101010011000000
0101001110011111111111111111111111111001
010101110001
010101
ACM-ICPC Asia Phuket Regional Programming Contest - 4 November 2009 - Phuket, Thailand
5/23
