ACM ICPC ASIA MANILA 2009: PHOTOS, Day 1. Team Registration, Welcome Lunch, Opening Session, Coaches' Forum, 'Cocktails', Open Forum

.
Link to blog post: http://raffysaldana.blogspot.com/2009/11/acm-icpc-asia-manila-2009-photos-day-1.html


ACM International Collegiate Programming Contest

Asia Manila Regional

October 22 - 23, 2009

Ateneo de Manila University, Quezon City, Philippines

Event Sponsor: IBM

.

DAY 1, Thursday, October 22, 2009

Welcome Lunch
Opening Session
Practice Session
Coaches Forum
Merienda/Cocktails
Open Forum

.

Click on the link below to see larger images:

http://www.facebook.com/album.php?aid=168530&id=682835049&l=1cda75d5ce

.

ACM ICPC Asia Manila 2009: Team Registration Photos

.
Link to blog post: http://raffysaldana.blogspot.com/2009/11/acm-icpc-asia-manila-2009-team.html

ACM International Collegiate Programming Contest

Asia Manila Regional

October 22 - 23, 2009

Ateneo de Manila University, Philippines

Sponsored by IBM

.

REGISTRATION, Thursday, October 22, 2009

.

Click on the link below to see larger images:

.

http://www.facebook.com/album.php?aid=168235&id=682835049&l=877d6a96d5

.

ACM ICPC Asia Manila 2009: Problem D

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-d.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem D: ‘Composition of Polynomials’
Input file: d.in
Output file: stdout
Execution time limit: 15 seconds


Given two polynomials, p(x) of degree M, and q(x) of degree N, both with integer coefficients, your problem is to write a computer program that prints the coefficients of the composition polynomial f(x) = p(q(x)).

For example, if p(x) = 2x^3 + 5x – 4 and q(x) = 3x^2 – 4x + 1, then f(x) = p(q(x)) = 2(3x^2 – 4x + 1)^3 + 5( 3x^2 – 4x + 1) – 4 = 54x^6 – 216x^5 + 342x^4 – 272x^3 + 129x^2 – 44x + 3

INPUT. Input shall consist of several data sets. Each data set will be given in three lines of input. The first line will give the values of M and N, separated by one or more spaces. The second line will give the coefficients of each term of p(x), separated by one or more spaces, and arranged in increasing powers of x. The third line will give the coefficients of each term of q(x), separated by one or more spaces, and arranged in increasing powers of x. Both M and N will be between 0 and 10, inclusive. Each coefficient will be small, in the range -20 to 20 inclusive, but a small value raised to 10th power is not guaranteed to be a small integer. Input for the next data set will immediately follow that of the previous data set. An input of M = 0 and N = 0 will signify the end of input data.

SAMPLE INPUT
3 2
-4 5 0 2
1 -4 3
2 2
-7 0 2
5 3 2
0 0

OUTPUT.
For each data set, print one line of output of the form:“Data set N: <composition polynomial>”,
where N is the data set number, starting from 1, and <composition polynomial> is the resulting polynomial in decreasing powers of x, with zero terms omitted. If the power of a term is 1, then the power must not be printed. If the coefficient of a term is 1, you may optionally print or not print the coefficient.

OUTPUT FOR SAMPLE INPUT
Data set 1: 54x^6–216x^5+342x^4–272x^3+129x^2–44x+3
Data set 2: 8x^4+24x^3+58x^2+60x+43


(Acknowledgment: This problem was contributed by Dr. Pablo Manalastas, Ateneo de Manila University).
.

ACM ICPC Asia Manila 2009: Problem J

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-j.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem J: ‘So Long Pal’
Input file: j.in
Output file: stdout
Execution time limit: 120 seconds


A string is a palindrome if it reads the same whether read forward or backward. For example, “MaDaM” and “1234554321” are palindromes, while “APPLE”, “00110”, and “mADam” are not palindromes.

Non-palindromes, however, may also contain palindromes. For example, the longest palindrome in “APPLE” is “PP”, the longest palindrome in “00110” is “0110”, and the longest palindrome in “Philippines” is “ippi”.

Input

The file consists of several test cases, each with a case number and the test case. A test case specifies a string with length 2 up to 100.

Output

For each test case, output the length of the longest palindrome in the string. Note that non-letters and non-digits are considered in searching for palindromes in the string, but are eventually not counted in the length of the longest palindrome.

Sample Input

Case 1: 1234554321
Case 2: Yes
Case 3: M*aD*aM
Case 4: M*aDa*M
Case 5: M*aDa*m
Case 6: 22r1*+00+*1r?
Case 7: ?0&910$$0190+
Case 8: 0&910$0$0+
Case 9: 0&910$+
Case 10: $+*+$

Output for the Sample Input

Case 1: 10
Case 2: 1
Case 3: 1
Case 4: 5
Case 5: 3
Case 6: 6
Case 7: 6
Case 8: 3
Case 9: 1
Case 10: 0


(Acknowledgment: This problem was contributed by Dr. Nelson Marcos, De La Salle University - Manila)

.

ACM ICPC Asia Manila 2009: Problem I

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-i.html


2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem I: ‘U Fill Me Up’
Input file: i.in
Output file: stdout
Execution time limit: 30 seconds

An n x m matrix can be filled by consecutive numbers starting from a number p, in a diagonal fashion starting at the upper right corner. For example, the 4 x 7 matrix below is filled up by numbers starting from 4.

(See Figure 1)

From the matrix, the sum of the elements covered by the region specified by indices (x1, y1) and (x2, y2) can be computed. For example, the sum of the elements covered by the region specified by index (1, 2) to index (2, 4) is 106 (because 21 + 14 + 13 + 23 + 20 + 15 = 106).

Input

The file consists of several test cases, each with a case number and the test case. A test case specifies the dimensions n and m of the matrix (where 0 <> 0, and x1 <= x2 and y1 <= y2). Output

For each test case, output the sum of the elements in the specified region.

Sample Input

Case 1: 4 7 4 1 2 2 4
Case 2: 4 7 4 3 6 4 7
Case 3: 4 7 4 5 2 6 8
Case 4: 4 7 4 4 7 5 10
Case 5: 8 5 1 2 1 2 5

Output for the Sample Input

Case 1: 106
Case 2: 47
Case 3: 0
Case 4: 10
Case 5: 48


(Acknowlegment: This problem was contributed by Dr. Nelson Marcos, De La Salle University - Manila)

.

ACM ICPC Asia Manila 2009: Problem H

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-h.html

NOTE: Click on the images to see larger views.

.

(Acknowledgment: This problem was contributed by Dr. Felix Muga II, Ateneo de Manila University)

.

ACM ICPC Asia Manila 2009: Problem G

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-e.html

( Note: Click on the figure to see a larger view. )

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem G: ‘A eiH1 aNy 1’
Input file: g.in
Output file: stdout
Execution time limit: 30 seconds

The recent rise in the number of people contracting the flu virus had led to the study on its spread pattern. Given a population of N people in a community, there will be some people who are naturally immune from the flu virus and there are those who are not. Depending on the movement of the person, he or she also has a varying radius of transmission as represented by circles in Figure 1. However, we shall assume that each person can only be infected at center of his/her area. Figure 1 illustrates the spread of the flu virus after 4 transmissions. The first infected person is labeled with a value of 0, infecting 2, 2, 1 and 1 person, respectively, for each transmission.

(See Figure 1)

The flu virus is eventually contained at this point in time. We shall assume the center point of all people will remain the same.

Input
The input consists of multiple test cases. Each test case starts with a line containing an integer N (1 ≤ N ≤ 30) indicating the number of people in the population. Starting on the next line are 3-tuple data (x y r) representing the persons x, y coordinates and r radius of transmission. Each 3-tuple data are space delimited. Persons who are immune to the flu virus have a radius of 0. The first entry in each test case is the first person affected with the flu virus. The last test case is followed by a line containing a single zero. The coordinate system sets the origin in the top left corner of the entire area. The variables x and y are positive integers not exceeding 200. The variable r is a non-negative integer not exceeding 200.

Output

For each test case, print the case number (starting with 1) followed by the number of transmission before the flu virus is eventually contained.

Sample Input

23
50 30 20
45 20 0
70 25 0
85 30 0
10 30 0
10 40 10
25 35 0
25 20 10
35 35 10
55 35 0
65 35 20
80 40 15
105 40 10
20 55 10
40 50 10
60 50 10
85 50 10
90 55 10
110 55 5
50 65 20
70 65 5
25 70 0
95 75 0
0

Output for the Sample Input

Case 1: 4 transmissions

(Acknowledgment: This problem was contributed by Dr. Caslon Chua, De La Salle University-Manila)

.

ACM ICPC Asia Manila 2009: Problem F

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-f.html


Figure 1. (Note: Click on the figure to see a larger view.)


2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem F: ‘Ordered Pairs and Positive Integers’
Input file: f.in
Output file: stdout
Execution time limit: 60 seconds

See Figure 1.

(Acknowledgment: This problem was contributed by Dr. Allan Sioson, Ateneo de Naga University)
.

ACM ICPC Asia Manila 2009: Problem E

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-e_28.html

Figure 1 and Figure 2.
(Note: Click on the figures to see a larger views.)


2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem E: ‘Been Rational’
Input file: e.in
Output file: stdout
Execution time limit: 30 seconds

.

See Figure 1 and Figure 2.

.

(Acknowledgment: This problem was contributed by Dr. Allan Sioson, Ateneo de Naga University)

.

ACM ICPC Asia Manila 2009: Problem C

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-c_27.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem C: ‘Minimal Bounding Rectangle’
Input file: c.in
Output file: stdout
Execution time limit: 60 seconds

Given N points on the plane, namely, (x[0],y[0]), (x[1],y[1]), . . . , (x[N-1],y{N-1]), a divider line is one that passes through two of these points such that all the N points are on one side of the line or on the line itself. Given any divider line L(P, P') that passes through the two points P and P', a unique bounding rectangle R(P, P') of minimal area can be found that contains all the N points inside the rectangle or on its sides, such that one side of R(P, P') is on L(P, P'). You problem is to write a computer program that will determine all such bounding rectangles of minimal area such that one side is on a divider line, and report the the smallest area among all such rectangles.

For example, given the six points A(0,0), B(0,2), C(1,1), D(2,2), E(3,1), and F(4,0). The divider line passing through AB defines a bounding rectangle of minimal area 8 square units. The divider line passing through AF defines a bounding rectangle of minimal area 8 square units. The divider line passing though DF defines a bounding rectangle of minimal area 12 square units. Finally the divider line passing through BD defines a bounding rectangle of minimal area 8 square units. Thus the bounding rectangle of smallest area has 8 square units.

INPUT.
Input shall consist of several data sets. Each data set will be given in several lines. The first line of the data set will contain the value of N. This will be followed by N lines, each line containing the x and y coordinates of one point, separated by spaces. The value of N will not exceed 500. The coordinates x and y will be integers not exceeding 1000 in absolute value. Data for the next data set will immediately follow the data for the previous data set. An input value of N = 0 signifies the end of input.

SAMPLE INPUT
6
0 0
0 2
1 1
2 2
3 1
4 0
3
0 1
1 0
1 1
0

OUTPUT.
For each data set, print one line of output of the form “Data set N: A”, where N is the data set number, starting from 1, and A is the area of the bounding rectangle that is the smallest, given to four decimal places. Note that two sides of a bounding rectangle may meet at a point with non-integer coordinates.

OUTPUT FOR THE SAMPLE INPUT
Data set 1: 8.0000
Data set 2: 1.0000


(Acknowledgment: This problem was contributed by Dr. Pablo Manalastas, Ateneo de Manila University).

.

ACM ICPC Asia Manila 2009: Problem B

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-b.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem B: ‘Typhoon Ondoy’
Input file: b.in
Output file: stdout
Execution time limit: 10 seconds

On September 26, 2009, Typhoon Ondoy brought a month's worth of rainfall to Metro Manila and nearby areas in just a few hours, causing severe flooding which resulted in the loss of many lives and the displacement of hundreds of thousands of people.
Areas under Storm Signal No. 2 included: Aurora, Quirino, Nueva Vizcaya, Nueva Ecija, Pangasinan, Tarlac, Zambales, Pampanga, Bulacan, Rizal, Northern Quezon, and Polillo Island.
Under Storm Signal No. 1 were: Isabela, Mountain Province, Ifugao, Benguet, La Union, Ilocos Sur, the rest of Quezon, Laguna, Cavite, Batangas, Mindoro provinces, Lubang Island, Marinduque, Camarines Norte, Bataan, and Metro Manila.
The Philippine Atmospheric Geophysical and Astronomical Services Administration (PAG-ASA) has come up with a measure to classify typhoons based on wind speed (in kph):
Tropical depressions have wind speeds of 30 to 46 kph (inclusive).
Tropical storms have wind speeds between 47 kph and 89 kph (inclusive).
Typhoons have wind speeds between 90 kph and 183 kph (inclusive).
Super typhoons have wind speeds greater than 183 kph.

TASK: Given a file containing wind speeds (in integer format, ranging from 1 to 255) your task is to produce a computer program that will display the type of typhoon based on wind speed. If the wind speed is between 1 and 29 kph (inclusive) then display the message “No classification”.


SAMPLE INPUT

1 50 100 60 155 200 90 46

SAMPLE OUTPUT

Case 1: No classification
Case 2: Tropical storm
Case 3: Typhoon
Case 4: Tropical storm
Case 5: Typhoon
Case 6: Super typhoon
Case 7: Typhoon
Case 8: Tropical depression


(Acknowledgment: This problem was contributed by Dr. Rafael Saldaña, Ateneo de Manila University)

.

ACM ICPC Asia Manila 2009: Problem A

.
Link to blog post:
http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem A: ‘Time Lapse Camera’
Input file: a.in
Output file: stdout
Execution time limit: 30 seconds

Henry has a time lapse camera that can take a set of 3 images in one shot. The three images are taken by the camera at different time lapse. For example, if the first image is taken at 0.33 seconds after the shot, then the second image is automatically taken at 0.51 seconds and the third image is taken at 0.62 seconds after the shot. The time lapses of taking the images are not reliable but the spatial coordinate (x, y) between images remain the same due to high speed shutter.

One nice evening during a sport festival, Henry placed a grid net in front of camera and started shooting the movement of a ball. Once the images were developed, Henry measured and recorded the coordinates of the ball on each image. Now he wants to know the highest height that the ball had achieved in a set of 3 images.

You need to help Henry by writing a program to compute the approximation of height that the ball has achieved in each set of images by assuming that the movement of the ball forms a parabolic curve.

Input

A test case consists of the coordinate of 3 points where the ball was captured by the camera. Input consists of several test cases. Each coordinate will not exceed 500.0 in absolute value. The input is terminated by a zero on a line by itself.

Output

Approximation of highest height that the ball has achieved in each test case

Sample Input

20, 25
50, 25
35, 30
15, 17
12, 23
16, 11
15, 12
25, 20
35, 25
0

Sample Output

Test case 1: 30.00
Test case 2: 23.25
Test case 3: 27.04


(Acknowledgment: This problem was contributed by Dr. Kardi Teknomo, Ateneo de Manila University)

.

ACM ICPC Asia Manila 2009: Problem Set

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-set.html

2009 ACM ICPC Asia Manila Regional
October 22 – 23, 2009
Ateneo de Manila University, Philippines

PROBLEM SET

Letter Code / Title / Input File

A, 'Time Lapse Camera', a.in
B, 'Typhoon Ondoy', b.in
C, 'Minimal Bounding Rectangle', c.in
D, 'Composition of Polynomials', d.in
E, 'Been Rational', e.in
F, 'Ordered Pairs and Positive Integers', f.in
G, 'A eiH1 aNy 1', g.in
H, 'Maximum Value', h.in
I, 'U Fill Me Up', i.in
J, 'So Long Pal', j.in

.

2009 ACM ICPC Asia Manila Regional Onsite Contest: Final Standing

.
Link to blog post:
http://raffysaldana.blogspot.com/2009/10/2009-acm-icpc-asia-manila-regional.html

ACM International Collegiate Programming Contest (ICPC)
Asia Manila Regional Onsite Contest
October 22 - 23, 2009
Ateneo de Manila University, Philippines
Sponsored by IBM

FINAL STANDING

Numbers 1 to 20

Numbers 21 to 40

Numbers 41 to 55
SUMMARY

Number of Teams Participated: 55

Number of Countries/Territories: 4 (Hong Kong, Philippines, Singapore, Vietnam)

Number of Schools: 23

Number of Problems Given: 10

Number of Teams that Solved at least 1 Problem: 55 / 55 (100 %)

Number of Teams that Solved 10 /10 Problems: 6 / 55 (10.9 %)

Winners:

1. CHAMPION: University of the Philippines - Diliman (PHILIPPINES)
'Mga SOGO ni E.T.'

2. First Runner-Up: Ho Chi Minh City University of Science (VIETNAM)
'PASSION'

3. 2nd Runner-Up: National University of Singapore (SINGAPORE)
'NUSSOC1'

Top Ten Schools:

1. University of the Philippines - Diliman (PHILIPPINES)
2. Ho Chi Minh City University of Science (VIETNAM)
3. National University of Singapore (SINGAPORE)
4. Hong Kong University of Science and Technology (HONG KONG)
5. University of Hong Kong (HONG KONG)
6. Ateneo de Manila University (PHILIPPINES)
7. De La Salle University - Manila (PHILIPPINES)
8. University of the Philippines - Los Banos (PHILIPPINES)
9. Ateneo de Naga University (PHILIPPINES)
10. University of Immaculate Conception - Davao (UIC)

Participating Schools:

Asia Pacific College (APC)
Ateneo de Davao University (ADDU)
Ateneo de Manila University (ADMU)
Ateneo de Naga University (ADNU)
Ateneo de Zamboanga University (ADZU)
Cebu Institute of Technology (CIT)
De La Salle Canlubang (DLSC)
De La Salle University - Manila (DLSU)
Don Bosco Technical College (DBTC)
Emilio Aguinaldo College - Manila (EAC)
FEU East Asia College (FEUEAC)
Ho Chi Minh City University of Science (HCMCUS)
Hong Kong University of Science and Technology (HKUST)
National University of Singapore (NUS)
Technological Institute of the Philippines - Manila (TIP)
University of Asia and the Pacific (UA&P)
University of the Immaculate Conception - Davao (UIC)
University of Hong Kong (UHK)
University of the Philippines - Diliman (UPD)
University of the Philippines - Los Banos (UPLB)
University of Saint Louis - Tuguegarao (USLT)
University of San Jose - Recoletos (USJR)
Xavier University (XU)

Prepared by:

Dr. Rafael P. Saldaña
Contest Director
2009 ACM ICPC Asia Manila

Date: 23 October 2009
.

ACM ICPC Asia Manila 2009: Message from Dr. Rafael Saldaña, Contest Director

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/blog-post.html

ACM International Collegiate Programming Contest (ICPC)
Asia Manila Regional Onsite Contest
October 22 - 23, 2009
Ateneo de Manila University, Philippines
Sponsored by IBM

Website: http://www.math.admu.edu.ph/acm




MESSAGE

Mabuhay!

Welcome to the 2009 ACM International Collegiate Programming Contest, Asia Regional Manila hosted by Ateneo de Manila University.

The ACM ICPC is a prestigious event that aims to raise the awareness of the public about the important role of Information Technology in the development of our country and our society.

It’s objective of bringing together bright and talented young people from different countries to take part in a grueling friendly competition, like a mental Olympiad, is quite noble.

To all participants and coaches, I hope that you will take advantage of this opportunity to meet and interact with your fellow competitors from all over the Philippines and other countries in Asia.

I also hope that you will also enjoy your stay at the Ateneo de Manila University.

Finally, I would like to thank the Association for Computing Machinery (ACM) for giving Ateneo de Manila University another chance to host the prestigious ICPC event in Manila. I would also like to thank my co-organizers, judges, volunteers, and our sponsors for making the 2009 Asia Programming Contest-Manila a success.


(Sgd.) Rafael P. Saldaña, Ph.D.
Regional Contest Director
ACM ICPC Asia-Manila Site
Ateneo de Manila University
October 2009

.