As promised...
I am posting the problems and solutions of the SRM 145, held on 6th May 2003.
Official Pages
Here is the the official page of the match in TopCoder's Archive.
Here is the editorial page.
And now the problem statements and my solutions...
Task: Dither Counter
Problem Statement 

Sometimes when computer programs have a limited number of colors to use, they use a technique called dithering. Dithering is when you use a pattern made up of different colors such that when the colors are viewed together, they appear like another color. For example, you can use a checkerboard pattern of black and white pixels to achieve the illusion of gray. You are writing a program to determine how much of the screen is covered by a certain dithered color. Given a computer screen where each pixel has a certain color, and a list of all the solid colors that make up the dithered color, return the number of pixels on the screen that are used to make up the dithered color. Each pixel will be represented by a character in screen. Each character in screen and in dithered will be an uppercase letter ('A''Z') representing a color. Assume that any pixel which is a color contained in dithered is part of the dithered color. 

Definition 



Constraints 

  dithered will contain between 2 and 26 upper case letters ('A''Z'), inclusive.  
  There will be no repeated characters in dithered.  
  screen will have between 1 and 50 elements, inclusive.  
  Each element of screen will contain between 1 and 50 upper case letters ('A''Z'), inclusive.  
  All elements of screen will contain the same number of characters.  
Examples 

0)  


1)  


2)  


3)  


4)  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Solution
using System; class ImageDithering { public int count(string dithered, string[] screen) { string allPixels = String.Join("", screen); int count = 0; char[] types = dithered.ToCharArray(); foreach (char type in types) { foreach (char pixel in allPixels) { if (pixel == type) { count++; } } } return count; } }
Task: Exercise Machine
Problem Statement 

You are writing firmware for an exercise machine. Each second, a routine in your firmware is called which decides whether it should display the percentage of the workout completed. The display does not have any ability to show decimal points, so the routine should only display a percentage if the second it is called results in a whole percentage of the total workout. Given a string time representing how long the workout lasts, in the format "hours:minutes:seconds", return the number of times a percentage will be displayed by the routine. The machine should never display 0% or 100%. 

Definition 



Constraints 

  time will be a string formatted as "HH:MM:SS", HH = hours, MM = minutes, SS = seconds.  
  The hours portion of time will be an integer with exactly two digits, with a value between 00 and 23, inclusive.  
  The minutes portion of time will be an integer with exactly two digits, with a value between 00 and 59, inclusive.  
  The seconds portion of time will be an integer with exactly two digits, with a value between 00 and 59, inclusive  
  time will not be "00:00:00".  
Examples 

0)  


1)  


2)  


3)  


4)  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Solution
using System; class ExerciseMachine { public int getPercentages(string time) { int[] parts = new int[3]; int count = 0; string buffer = ""; foreach (char symbol in time) { if (symbol == ':') { parts[count] = Int16.Parse(buffer); buffer = ""; count++; } else { buffer += new string(symbol, 1); } } parts[count] = Int16.Parse(buffer); int seconds = parts[0] * 3600 + parts[1] * 60 + parts[2]; count = 0; for (int i = 1; i < 100; i++) { if (((i * seconds) % 100) == 0) { count++; } } return count; } }
Task: Vending Machine
Problem Statement 

Note that in the following problem statement, all quotes and angle brackets are for clarity A certain vending machine delves out its goods from a rotating cylinder, which can rotate around in both clockwise and counterclockwise directions. The cylinder has a number of shelves on it, and each shelf is divided into a number of columns. On the front of the machine, there is a panel of doors that extends the entire height of the column. There is one door for each shelf, which is the width of one column. When a purchase is made, the user uses two buttons to rotate the cylinder so their purchase is located at a door. They make their purchase by sliding the appropriate door open, and removing the item (there can only be one item per column on a particular shelf). The cylinder can rotate in a complete circle, and so there are always two ways to get from a particular column to another column. Because the vending machine company wants to sell the most expensive items possible, and the machine can only show one column at a time, the machine will always try to put forth the most expensive column available. The price of a column is calculated by adding up all the prices of the remaining items in that column. The most expensive column is defined to be the one with the maximum price. If 5 minutes have elapsed since the last purchase was made, the machine rotates the cylinder to the most expensive column. If, however, another purchase has been made before the 5 minutes are up, the rotation does not occur, and the 5 minute timer is reset. Recently, some machines' rotating motors have been failing early, and the company wants to see if it is because the machines rotate to show their expensive column too often. To determine this, they have hired you to simulate purchases and see how long the motor is running. You will be given the prices of all the items in the vending machine in a string[]. Each element of prices will be a singlespace separated list of integers, which are the prices (in cents) of the items. The Nth integer in the Mth element of prices represents the price of the Nth column in the Mth shelf in the cylinder. You will also be given a string[] purchases. Each element in purchases will be in the format: In the simulation, the motor needs to run for 1 second in order to rotate to an adjacent column. When the machine is turned on, column 0 is facing out, and it immediately rotates to the most expensive column, even if the first purchase is at time 0. The machine also rotates to the most expensive column at the end of the simulation, after the last purchase. Note that when an item is purchased, its price is no longer used in calculating the price of the column it is in. When the machine rotates to the most expensive column, or when a user rotates the cylinder, the rotation is in the direction which takes the least amount of time. For example, in a 4column cylinder, if column 0 is displayed, and the cylinder is rotated to column 3, it can be rotated backwards, which takes 1 second, versus rotating forwards which takes 3 seconds. If a user tries to purchase an item that was already purchased, this is an incorrect simulation, and your method should return 1. Otherwise, your method should return how long the motor was running, in seconds. 

Definition 



Notes 

  When rotating to the most expensive column, if two columns have the same price, rotate to the one with the lowest column number (see example 0).  
  If two purchases are less than 5 minutes apart, the machine does not perform a rotation to the most expensive column between the purchases. If two purchases are 5 or more minutes apart, the machine rotates to the most expensive column between the two purchases.  
Constraints 

  prices will have between 1 and 50 elements, inclusive.  
  Each element of prices will have between 5 and 50 characters, is a singlespace separated list of integers, and has no leading or trailing spaces.  
  Each element of prices will have the same number of integers in it.  
  Each element of prices will have at least 3 integers in it.  
  Each integer in prices will be between 1 and 10000, inclusive, and will not contain leading 0's.  
  purchases will have between 1 and 50 elements, inclusive.  
  Each element of purchases will be in the format "<shelf>,<column>:<time>" (angle brackets and quotes are for clarity only), where <shelf>, <column>, and <time> are all integers.  
  In each element of purchases, <shelf> will be between 0 and M  1, inclusive, where M is the number of elements in prices.  
  In each element of purchases, <column> will be between 0 and N  1, inclusive, where N is the number of integers in each element of prices.  
  In each element of purchases, <time> will be between 0 and 1000, inclusive.  
  In each element of purchases, <shelf>, <column>, and <time> will not contain extra leading 0's.  
  purchases will be sorted in strictly ascending order by <time>. This means that each purchase must occur later than all previous ones.  
Examples 

0)  


1)  


2)  


3)  


4)  

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved.
Solution
using System; using System.Text.RegularExpressions; class VendingMachine { struct Purchase { public int Row; public int Col; public int Minute; } public int motorUse(string[] prices, string[] purchases) { int[,] dPrices = this.ParsePrices(prices); Purchase[] dPurchases = this.ParsePurchases(purchases); int col = 0; int result = 0; result += this.GotoHighest(ref col, dPrices); // Algorithm for (int i = 0; i < dPurchases.Length; i++) { int purchaseMotorCost = this.MakePurchase(dPurchases[i], ref col, ref dPrices); // already empty if (purchaseMotorCost == 1) return 1; result += purchaseMotorCost; if ( ((i + 1) == dPurchases.Length )  ((dPurchases[i + 1].Minute  dPurchases[i].Minute) >= 5) ) { result += this.GotoHighest(ref col, dPrices); } } return result; } private int GotoHighest(ref int col,int[,] dPrices) { int highestCol = 0; int highestPrice = 0; int rowsCount = dPrices.GetLength(0); int colsCount = dPrices.GetLength(1); for (int i = 0; i < colsCount; i++) { int currentColPrice = 0; for (int j = 0; j < rowsCount; j++) { currentColPrice += dPrices[j, i]; } if (currentColPrice > highestPrice) { highestCol = i; highestPrice = currentColPrice; } } int distance = this.CalculateClosestDistance(col, highestCol, colsCount); col = highestCol; return distance; } private int MakePurchase(Purchase purchase, ref int col, ref int[,] dPrices) { int colsCount = dPrices.GetLength(1); if (dPrices[purchase.Row, purchase.Col] == 0) return 1; dPrices[purchase.Row, purchase.Col] = 0; int distance = this.CalculateClosestDistance(col, purchase.Col, colsCount); col = purchase.Col; return distance; } private int CalculateClosestDistance(int current, int destination, int last) { return Math.Min( Math.Min(Math.Abs(current  destination), last  current + destination), current + (last  destination) ); } private int[,] ParsePrices(string[] prices) { Regex regex = new Regex("\\s"); int colCount = regex.Split(prices[0]).Length; int[,] result = new int[prices.Length, colCount]; for (int i = 0; i < prices.Length; i++) { string[] items = regex.Split(prices[i]); for (int j = 0; j < items.Length; j++) { result[i, j] = Int32.Parse(items[j]); } } return result; } // "x,y:n" private Purchase[] ParsePurchases(string[] purchases) { Purchase[] result = new Purchase[purchases.Length]; for (int i = 0; i < purchases.Length; i++) { string[] data = Regex.Split(purchases[i], ",:"); result[i] = new Purchase(); result[i].Row = Int32.Parse(data[0]); result[i].Col = Int32.Parse(data[1]); result[i].Minute = Int32.Parse(data[2]); } return result; } }
Summary
The first one is solved in m(the size of the screen) * n(the size of the dither), could it be solved in less operations (smaller complexity)?
The second task has an interesting solution (which solves it in linear time). I got to it analytically, finally deriving the equation:
((percentageâ€‹ * seconds) % 100) = 0
And instead iterating through all the seconds (which also would be in linear time if you think about it), I iterate though the wholenumber percentage values (199).
The third task had too many subtasks that needed to be solved, starting from the parsing of the input data. But the distilled algorithm is in the public method alone.
Until my next post. Ð§Ð°Ð¾! ("Bye" in Bulgarian)