TopCoder HS Competition at Purdue
05-14-2007
Purdue Computer Science will host the first-ever international TopCoder high school tournament on Saturday, May 19. This event will commence with registration and a reception on Friday, May 18. Fifty top high school participants from around the world will then compete in the Lawson Computer Science Building on Saturday beginning at 9:30 a.m. The Semifinal round will take place at 10:00 a.m., and the Championship round will start at 2:30 p.m. An awards ceremony will be held in the Purdue Memorial Union Saturday evening.
Spectators may join the action at the Lawson Computer Science Building between 9:00 a.m. and 4:30 p.m. Online viewing is also available at http://www.topcoder.com.
Purdue CS is proud to host the TopCoder competition with generous help from The Motorola Foundation. CS will sponsor the hospitality area in the Lawson Commons during the competition. Participants can stop by for refreshments and computing handouts. There will also be CS faculty and staff on hand to answer questions for students interested in pursuing a computer science career.
Below are the three problems used at a recent competition. Contestants have 85 minutes to solve all three problems (programming in C, C++, Java, VB.NET, or C#). This "coding period" is followed by a 10 minute "challenge period", during which all source code is revealed and the participants try to find data sets that break their competitor's programs. (The problem statements below are abbreviated. Full problem statements also include formal definitions, constraints, and examples.)
Advertising Agency
You are working in an advertising agency. There are 100 billboards owned by your agency, numbered from 1 to 100.
Your clients send you requests, one after another. Each request is the number of the billboard on which the client would like to place his advertisement.
Initially all billboards are empty. Each time you receive a request, you act as follows. If the corresponding billboard is empty, you satisfy the request and occupy the billboard with the client's advertisement. If the corresponding billboard is occupied, you reject the request.
You are given a int[ ]requests containing the requests in the order you receive them. Return the number of rejected requests.
Digram Analysis
A word is a maximal continuous sequence of letters ('a'-'z'). Words are separated by spaces.
A digram is a string of length two. A word is said to contain digram "xy" if it contains an 'x'" immediately followed by 'y'. For example, the word "coder" contains digram "od" but doesn't contain digram "oe".
Consider text that consists of one or more words. The most frequent digram in text is the one that is contained in maximal number of words.
Given a piece of text, the most frequent digram is defined as the one that occurs in the greatest number of words. You are given a String[ ] chunks. Concatenate all elements of chunks to produce one long String of text. Return the most frequent digram in this text. If there are multiple possible answers, return the one among them that comes earliest alphabetically.
More Black
You are given a rectangular board containing m x n squares. Some squares on it are missing.
You must color the existing squares white or black, so that the number of black squares is maximized, and no two existing squares of the same color have a common side.
You are given the board as a String[ ] board, where the j-th character of the i-th element represents the square at row i, column j. Missing squares are denoted by '.' (dot) and existing squares are denoted by '#' (sharp). Return a String[ ] in the same format, where all '#' characters are replaced with lowercase 'w' for white squares and 'b' for black squares. If there are multiple solutions, return the one among them that comes first lexicographically. That is, you must minimize the first string, if there are still several solutions, minimize the second one, and so on.