ACM ICPC Philippines 2008: Problem D

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem D: “Soil Investigation”
Input File: d.in

Introduction:

For a mining company to investigate the existence of a mineral (such as gold or oil), it needs to drill several holes on the area it suspects to have the precious mineral and get the soil samples. Based on the laboratory test of the soil samples on a hole, the company can decide the degree of existence of the precious mineral and the level of confidence (between 0 and 1) from that hole.

However, it is not advisable to drill the whole area due to high cost of drilling. To do the soil investigation in a more systematic way, the company decides to take aerial photograph of the whole site and divides them into cells of equally distance grid. By ignoring the remaining boundary, the cell size of the grid can be assumed as a square. Then, the company starts to drill on selected cells and approximates the degree of existence of the precious mineral based on smoothing average of the neighboring cells. A cell that does not have drilling hole will have zero confidence.

The smoothing procedure goes as the summation of a product between the level of confidence and the degree of existence of the center cell and one minus the product between the level of confidence of the center cell and average degree of existence over 4 neighbors (up, down, left and right).

The iteration formula is

(a^0)(i,j) = b(i,j)*c(i,j) + (1 - c(i,j))*((b(i - 1, j) + b(i+1,j) + b(i, j - 1) + b(i, j+1))/4)

Task: Write a program to compute the approximation of the degree of existence of a precious mineral on a certain cell of interest (current row, current column) given the grid size (number of cells in a row, number of cells in a column) and results of laboratory test at certain cell (test row, test column, degree of existence of the precious mineral, the level of confidence). The coordinate system is assumed to start at (1, 1) on the top left cell.Input: The format of an input test case is as follows:

Number of cells in a row, number of cells in a column

List of results of laboratory test at certain cell (test row, test column, degree of existence of the precious mineral, the level of confidence)

List of coordinates of the cell of interest (current row, current column)

The input is terminated by a zero on a line by itself.

Output: List of the approximation of the degree of existence of the precious mineral on the cell of interest for each test case

Sample Input

3, 5
1, 1, 10, 1
1, 5, 5, 0.7
2, 2, 20, 0.8
3, 5, 6, 0.5
1, 1
1, 4
2, 2
3, 4
0
5, 4
3, 2, 7, 1
4, 4, 5, 1
4, 2
4, 3
0

Sample Output

Case 1
1, 1: 10
1, 4: 1.3
2, 2: 16
3, 4: 1.5

Case 2
4, 2: 1.8
4, 3: 1.3

------------------------------------------------------

Problem Category: Moderate

Number of teams which solved the problem: 8 (out 39)

Success rate: 21 %

For more information, contact: computingsoc@gmail.com

.

ACM ICPC Philippines 2008: Problem C

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem C: “I came, I saw, I conquered!”
Input File: c.in

Introduction:

As early as the first century B.C., the Roman general Gaius Julius Caesar (100 B.C. – 44 B.C.) used a cipher shift to make the contents of certain messages understandable only for those he intended the message to reach. To describe this early form of cryptosystem – often termed the Caesar cipher – we shall make certain conventions to simplify the presentation. First, we shall write the original message, the plaintext, using only lower case letters, with no punctuation or spaces. Then to encrypt the plaintext, each lowercase letter, from a to w, is shifted to the letter three places forward in the alphabet, and the last three letters – namely x, y and z, are shifted to the first three letters, respectively. We use the uppercase letters for the resulting cyphertext. Consequently, a is encrypted as D, b as E, c as F ….. j as M….. m as P, y as B and z as C. In this example, the key (or cipher shift) equals 3.

If Caesar wanted to inform a senator in Rome of a recent victory, he might have sent the message “I came, I saw, I conquered!” Encryption of this message takes place as follows:

Message: I came, I saw, I conquered!
Plaintext: icameisawiconquered
Ciphertext: LFDPHLVDZLFRQTXHUHG

Upon receiving the ciphertext, as long as this senator knows the size and direction of the shift, he can reverse the process. Decryption then results by replacing each uppercase letter, from D to Z, in the ciphertext by the lowercase letter three places back in the alphabet, and A by x, B by y and C by z. After decrypting, one then inserts the appropriate spaces and punctuations in the plaintext. (Note that by removing spaces in the plaintext, the resulting absence of spaces in the ciphertext helps make the message more unintelligible. If one does not know the size and direction of the shift for decryption, the presence of spaces may suggest certain information about the structure of the original message.)

Task:

Given the key (or cipher shift) and the message written in separate lines in the input file, write a computer program to encrypt the message using the Caesar cipher as described above.

The key (an integer) shall range from the number 0 to 25. The message can contain an array (or string) of alphanumeric and special characters of minimum length 1 and maximum length 50 chararacters. If the message does not contain a letter, or the message length is not within the required range the program should output the phrase ‘Message not valid’.

Sample Input

3
I came, I saw, I conquered!
2
I came, I saw, I conquered!
5
*14344&

Sample Output

Case 1: LFDPHLVDZLFRQTXHUHG
Case 2: KECOGKUCYKEQPSWGTGF
Case 3: Message not valid

-----------------------------------------------------------

Problem Category: Easy

Number of teams which solved the problem: 24 (out 39)

Success rate: 80 %

For more information, contact: computingsoc@gmail.com

.

ACM ICPC Philippines 2008: Problem B

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem B: “Balanced Parentheses”
Input File: b.in


Check if a sequence of parentheses is balanced or not. An open parenthesis should match with the nearest close parenthesis.

If balanced, output the sequence as is, otherwise, replace the unbalanced parentheses with square brackets.


Sample Input / Sample Output

(((()))) / Case 1: (((())))
((()))) / Case 2: ((()))]
((()(()) / Case 3: [[()(())
()())(() / Case 4: ()()][()

-------------------------------------------------------

Problem Category: Easy

Number of teams which solved this problem: 24 (out 39)

Success rate: 80 %

For more information, contact: computingsoc@gmail.com

.

ACM ICPC Philippines 2008: Problem A

.
2nd Philippine National Inter-Collegiate Programming Competition
(ACM Philippines 2008)
22 November 2008, Cebu City

Problem A: “Induction”
Input File: a.in

Introduction:

The following problem has appeared in several mathematical competitions before:

Show that any positive integer can be represented as a sum of one or more numbers of satisfying the following conditions

a) the numbers are of form (2^s)(3^r) where s and r are nonnegative integers, and

b) no summand is a factor of another summand.

The standard proof to the statement is as follows:

We prove the statement by induction.

Base Case:

If n = 1, then n = (2^0)*(3^0). If n = 2 then n = (2*)(3^0). If n = 3, then n = (2^0)*3

Inductive Step

We assume that the statement is true for all natural numbers less than n. We shall now prove that the statement is true for n.

Case 1: Assume that n is even.

Since n/2 is less than n, then n/2 has a representation that satisfies the conditions above. We just multiply the set of summands of n/2 by 2 and we use this as a representation for n.

Case 2: Assume that n is odd.

We find s such that 3^s is less than or equal to n which is less than or equal to 3^(s+1).

If n = 3^s , then we are already done.

If 3^s < m =" (n" m =" ((n" m =" <" n =" 2m">Task: Given a positive integer n, write a program that should output a set of numbers of the form: (2^s)(3^r) , (where s and r are nonnegative integers), satisfying the following conditions:

a) The sum of the numbers in the set is n.

b) No element in the set is a factor of another element in the set.

Sample Input / Sample Output

23 / Case 1: {8, 6, 9}

67 / Case 2: {16, 24, 27}

-----------------------------------------------------------------------------------

Problem Category: Moderate

Number of teams that have solved this problem: 8 (out of 39)

Success rate: 21%

For more information, contact: computingsoc@gmail.com
.

ACM ICPC Philippines 2008: Problems

.
Below is a list of programming problems given during the 2nd Philippine National Inter-Collegiate Programming Competition (ACM ICPC Philippines 2008) held on 22 November 2008 at the University of San Jose-Recoletos, Basak Campus, Cebu City:

Problem A: Induction
Problem B: Balanced Parenthesis
Problem C: I came, I saw, I conquered!
Problem D: Soil Investigation
Problem E: Stacking Matchsticks
Problem F: Smallest Sums

(Note: Individual links to these problems will be provided soon.)

Level of Difficulty (easy, moderate, difficult):

1. Easy: B, C, E

2. Moderate: A, D

3. Difficult: F

Number of Teams Who Have Solved Each Problem:

(Note: There were 39 teams who participated in the Contest.)

Problem A: 8 teams

Problem B: 24 teams

Problem C: 24 teams

Problem D: 8 teams

Problem E: 26 teams

Problem F: 3 teams

.

Problem Set: 1st Philippine National Olympiad in Informatics (PNOI 2008)

1st Philippine National Olympiad in Informatics (PNOI)
15 March 2008, Ateneo de Manila University, Philippines

Organized by

Grid and High Performance Computing Group,
School of Science and Engineering,
Ateneo de Manila University (ADMU)

in cooperation with the
Computing Society of the Philippines (CSP)

Hosted by

Department of Information Systems and Computer Science (DISCS)
Ateneo de Manila University



PROBLEM SET



Directions: (TO THE CONTESTANTS)

Do not open this problem set UNLESS you are given the signal by the Contest Director to do so.

NOTES are not allowed during the contest.

This is a three-hour programming contest and there are SIX problems to be solved. Budget your time so that you will be able to solve as many problems as you can.



(Sgd.) Rafael P. Saldaña, Ph.D.
Contest Director
PNOI 2008

----------------------------------------------------------------------------

Problem A: A Simple Task
Problem B: Rina's Triangles
Problem C: Checking Collinearity
Problem D: How Many Groups?
Problem E: Text Messages
Problem F: Shopping Spree




----------------------------------------------------
Problem A: A Simple Task
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
----------------------------------------------------

Given a positive integer n, find the odd integer o and the non-negative integer p such that n = o2p.

Example:

For n = 24, o = 3 and p = 3.

Task: Write a program which for each data set:

* reads a positive integer n,
* computes the odd integer o and the non-negative integer p such that n=o*2^p,
* writes the result.

Input

The first line of the input contains exactly one positive integer d equal to the number of data sets, where 1 ≤ d ≤ 20. The data sets follow. Each data set consists of exactly one line containing exactly one integer n, where 1 ≤ n ≤ 2147483647.

Output

The output should consists of exactly d lines, one line for each data set. Line i, 1 ≤ i ≤ d, corresponds to the i-th input and should contain the remark “Set i:” and the two integers o and p separated by a single space such that n = o*2^p.

Sample Input

2
24
36

Output for Sample Input

Set 1: 3 3
Set 2: 9 2










---------------------------------------------------
Problem B: Rina's Triangles
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

Given four integers, all positive or zero, Rina's Triangle is formed by using these four integers as the base of the triangle, and computing each remaining value in the triangle as the absolute difference of the two values immediately below it. For example, given 89, 78, 12, 13 we can construct Rina's Triangle as follows:

10
55 65
11 66 1
89 78 12 13

We say that a sequence of four positive integers is acceptable if no integer appears more than once in the Rina's Triangle it generates. So the sequence of four integers given above is acceptable.

Create a program that determines whether a sequence of four integers (all positive or zero) is acceptable or not.

Input. The first line of input will contain the number N of data sets (N will not exceed 20). This is followed by N lines, representing the N data sets. Each line contains four integers, all between zero and 65000 inclusive, belonging to the data set.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print “acceptable” or “not acceptable”, depending on the data set.

Sample Input

2
89 78 12 13
13 1 28 85

Output for Sample Input

Set 1: acceptable
Set 2: not acceptable








------------------------------------------------------
Problem C: Checking Collinearity
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
-------------------------------------------------------
The problem consists of several data sets. Each data set contains three (3) or more points on the Cartesian Plane. Your job is to determine if the points are collinear – that is, if they fall on a straight line, and if so, to determine the equation of the line passing through those points.

Example 1. Given the four points (0, 1), (1, 3), (2, 5), and (3, 7), we see that the line with equation 2x-y+1=0 passes through all the four points.

Example 2. Given the three points (5, 0), (5, 2), and (5, 7), we see that the line with equation x-5=0 passes through all the three points.

Example 3. Given the three points (1, 3), (2, 5), and (4, 8), we see that the three points are not collinear.

Input. Input will consist of at most 20 data sets. Each data set will start with a line containing the value of N, the number of points (N ≤ 100). This is followed by N lines, with each line containing the x and y coordinates of one point. The x and y coordinates will be given as integers, and x will not exceed 256 in absolute value. All points will be distinct. The first data set is immediately followed by one line containing the value of N for the next data set, and this is followed by N lines of x and y coordinates for that data set. A value of N = 0 indicates the end of input data, and input processing must stop.

Ouput. For each data set, print “Set K: “, where K is the data set number, starting from 1. Then print one of the following answers:

Ax+By+C=0
Not collinear

depending on the solution to the data set. The coefficients A, B, and C must must have no common factors, and A ≥ 0. If A is 1, just print x. If A is -1, just print -x. Similarly for B and y. If A or B or C is zero, just omit the x-term or the y-term or the constant term. If either B or C is negative, say A=2, B=-3, C=-5, then do not print the + sign before the – sign; print the answer simply as 2x-3y-5=0; do not print as 2x+-3y+-5=0.

Sample Input

40 11 32 53 7
35 05 25 73
1 32 54 8
0

Output for Sample Input

Set 1: 2x-y+1=0
Set 2: x-5=0
Set 3: Not collinear


-------------------------------------------------------
Problem D: How Many Groups?
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
-------------------------------------------------------

We have a collection of M persons { 1, 2, 3, . . . , M }, and we want to divide these M persons into groups. A person will be placed in a group if he “knows” at least one person in that group. For example, if we have 10 persons { 1, 2, 3, . . . , 10 }, and if the following pairs know each other: 1 and 3, 3 and 4, 3 and 5, 5 and 6, 5 and 7, 2 and 8, 2 and 9, and 8 and 10, then we can put 1, 3, 4, 5, 6, 7 in one group, and 2, 8, 9, 10 in another. Each person in the first group knows at least one person in that group. Each person in the second group knows at least one person in the second group. However, no one in the first group knows anyone in the second group, and vice-versa.

Your problem is to write a program that determines the number of groups into which you can divide M persons.

Input. Input will consist of at most 20 data sets. Each data set will consist of several lines. The first line will contain the values of M and P, where M is the number of persons, and P is the number of pairs that know each other. Here M will not exceed 200 people, and P will not exceed 100 pairs. This is followed by P lines, each line containing a pair of numbers x and y, separated by space, which means that x and y know each other. The values of x and y will be between 1 and M inclusive. The values of x and y will never be equal. Also, no pairs will be repeated. Data lines for the next data set will immediately follow the data lines for the previous data set. A data set with M = 0 and P = 0 will indicate the end of input, and input processing should stop.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print the number of groups into which the M persons can be divided.

Sample Input

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

Output for Sample Input

Set 1: 2
Set 2: 8
Set 3: 10
Set 4: 6






---------------------------------------------------
Problem E: Text Messages
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

On most mobile phones the numeric keys must be repeatedly pressed to produce letters for text messages. A common keypad layout looks like this:

[1 ] [2 abc] [3 def ]
[4 ghi ] [5 jkl ] [6 mno ]
[7 pqrs] [8 tuv] [9 wxyz]
[* ] [0 _ ] [ # ]

Furthermore, most phones will have a circular navi-key with which you can produce the navigation actions UP, DOWN, LEFT, RIGHT, and this navi-key is used to separate key presses for two letters on the same key. For example, to spell “cat” on this keypad, press [2] three times to produce “c”, then press RIGHT, then press [2] once to produce “a”, then press [8] once to produce “t”. Thus we need a total of six key presses to spell “cat”. Note that the character “_” on the [0] key stands for SPACE, and to generate SPACE, we need only press [0] once.

Create a computer program that counts the number of key presses needed to produce a text message. Assume that your phone can only produce lower-case letters and SPACE, and that we only need to send text messages containing lower-case letters and SPACE.

Input. Input will consist of at most 20 data sets. The first line of input will contain the value of N, the number of data sets. This will be followed by N lines, with each line containing one data set, namely the text message to send. The length of the message will not exceed 160 characters, including blanks. There will be exactly one blank character between words.

Output. For each data set, print “Set K:”, where K is the data set number, starting from 1. Then print the number of key presses needed to produce the given text message.

Sample Input

2
i love you
cab money

Output for Sample Input

Set 1: 24
Set 2: 22







---------------------------------------------------
Problem F: Shopping Spree
Input: C stdin, or Java System.in
Output: C stdout, or Java System.out
Execution Time Limit: 1 second
---------------------------------------------------

You have received a local pass from the grocery store for a one day shopping bonanza. At the start of the day, you are given a pushcart of capacity M and can get all the items you want as long as it can fit into the pushcart.

As a programmer and expert shopper you want to maximize the total value of the items that you have bought by designing a simple program to identify what items you will buy.

Input. The first line contains an integer X, indicating the number of one-day shopping spree occasions you won; X is also the number of data sets. The first line of each data set contains two integers N and M indicating the number of various items available in the shop and the capacity of the pushcart respectively. The next N lines will contain the name of the item n[i] as a 20 character alphanumeric string, and a pair of integers indicating the cost c[i] and size s[i] of each item. The sizes will be given in ascending order.

Output. For each data set, will print the data set number, starting from 1, the name and number of each item bought, and the total value of the shopping purchase, as shown in the sample below. Items should be arranged in ascending lexicographical (alphabetical) order.

Sample Input
1
5 17
A 4 3
B 5 4
C 10 7
D 11 8
E 13 9

Output for Sample Input
Set 1: A–1, B-0, C–2, D–0, E–0, Total PHP24


Copyright, 2008. Computing Society of the Philippines, Ateneo de Manila University, and Philippine National Olympiad in Informatics Committee (c/o Dr. Rafael Saldaña).

A Commentary on Problems Given During the ACM ICPC Philippines 2007

Last October 20, 2007 I directed the First Philippine National Inter-Collegiate Programming Competitition (ACM ICPC Philippines 2007). This contest is affiliated with the ACM ICPC Asia-Singapore Regional Site. I spearheaded the organization of the contest in my capacity as the ACM ICPC Philippines Representative and on behalf of the Computing Society of the Philippines. The contest was hosted by De La Salle Canlubang. ACM stands for Association for Computing Machinery.

The following is the composition of the ACM ICPC Philippines 2007 Board of Judges:

Dr. Rafael Saldaña (Ateneo de Manila University) - Chair
Dr. Henry Adorna (University of the Philippines -Diliman) - Member
Dr. Eliezer Albacea (University of the Philippines -Los Baños) - Member
Dr. Jaime Caro (University of the Philippines-Diliman)- Member
Dr. Caslon Chua (De La Salle University - Manila) -Member
Dr. Nelson Marcos (De La Salle University - Manila) -Member
Dr. Raymond Todd Melton (Ateneo de Manila University)- Member

The Board of Judges prepared six (6) problems to be solved by the contestants in three (3) hours. The problems ranged from 'easy' to 'difficult'. They are standard problems in computer science.

The following are the problems given during the ACM ICPC Philippines 2007:

1. Problem A: Forward and Backward
2. Problem B: Counting Corners
3. Problem C: "NBN"
4. Problem D: Longest Common Subsequence
5. Problem E: Factor Factory
6. Problem F: Full Binary Search Tree

The easiest among the six problems is Problem A (Forward and Backward) while the most difficult is Problem E (Factor Factory). Out of 50 teams that participated in the competition, 35 teams were able to solve Problem A while 15 teams did not. No team was able to solve Problem E.

I was the one who gave Problem A. I gave this problem to ensure that most teams will go home with a balloon after the contest. (Note: A trademark of ACM programming contests is the giving of color-coded balloons to teams that have solved a problem. For example, if one team was able to solve 6 problems then that team will receive 6 balloons).

Problem A deals with palindromes. As explained in the problem formulation, a palindrome is a "word, phrase, number or other sequence of units that has the property of reading the same in either direction." For example, the word tenet and the number 123321 are palindromes. A number that is a palindrome is called a palindromic number. [ Note: I made several blog entries on palindromes in my blog last August 2007 :) . I got fascinated with palindromes when I found out that my phone number is a palindromic number. See http://raffysaldana.blogspot.com/2007/08/palindromes-and-palindromic-numbers.html]

The solution to Problem A involves comparing the first element of a string with the last element, the second element with the second to the last element, etc. until there are (N/2) comparisons done, where N (an integer) is the size of the given string. If all comparisons are successful then the given string is a palindrome.

The solution to Problem A is quite trivial. This makes me wonder why 15 out of 50 teams who joined the competition were not able to solve it.

What are the factors why a team gets zero in an ACM programming competition?

Here are my guesses:

1. Lack of preparation/experience/team work
2. Nervousness
3. Not reading the problem formulation carefully
4. Not fit for competition

I would like to encourage schools (offering bachelors' degree in computer science, computer engineering, information science, information technology, or related courses) to join ACM programming contests such as the Philippine National Inter-Collegiate Programming Competition to benchmark their students' aptitude in computer programming and problem solving.

Dr. Rafael P. Saldaña
Director
ACM ICPC Philippines
10/30/07