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

"BW"

{"AAAAAAAA",
 "ABWBWBWA",
 "AWBWBWBA",
 "ABWBWBWA",
 "AWBWBWBA",
 "AAAAAAAA"}

Returns: 24

"BW"

{"BBBBBBBB",
 "BBWBWBWB",
 "BWBWBWBB",
 "BBWBWBWB",
 "BWBWBWBB",
 "BBBBBBBB"}

Returns: 48

"ACEGIKMOQSUWY"

{"ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX",
 "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWX"}

Returns: 150

"CA"

{"BBBBBBB",
 "BBBBBBB",
 "BBBBBBB"}

Returns: 0

"DCBA"

{"ACBD"}

Returns: 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

"00:30:00"

Returns: 99

"00:28:00"

Returns: 19

"23:59:59"

Returns: 0

"00:14:10"

Returns: 49

"00:19:16"

Returns: 3

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

{"100 100 100"}

{"0,0:0", "0,2:5", "0,1:10"}

Returns: 4

 
+-----+-----+-----+
| 100 | 100 | 100 |
+*****+-----+-----+

+-----+-----+-----+
|  0  | 100 | 100 |
+*****+-----+-----+

+-----+-----+-----+
|  0  | 100 | 100 |
+-----+*****+-----+

+-----+-----+-----+
|  0  | 100 |  0  |
+-----+*****+-----+

{"100 200 300 400 500 600"}

{"0,2:0", "0,3:5", "0,1:10", "0,4:15"}

Returns: 17

+-----+-----+-----+-----+-----+-----+
| 100 |  0  |  0  |  0  |  0  | 600 |
+-----+-----+-----+-----+-----+*****+

{"100 200 300 400 500 600"}

{"0,2:0", "0,3:4", "0,1:8", "0,4:12"}

Returns: 11

{"100 100 100"}

{"0,0:10", "0,0:11"}

Returns: -1

{"100 200 300",
 "600 500 400"}

{"0,0:0", "1,1:10", "1,2:20",
 "0,1:21", "1,0:22", "0,2:35"}

Returns: 6

purchase 1:
+-----+-----+-----+
| 100 | 200 | 300 |
+-----+-----+-----+
| 600 | 500 | 400 |
+*****+-----+-----+

purchase 2:
+-----+-----+-----+
|  0  | 200 | 300 |
+-----+-----+-----+
| 600 | 500 | 400 |
+-----+*****+-----+

purchase 3:
+-----+-----+-----+
|  0  | 200 | 300 |
+-----+-----+-----+
| 600 |  0  | 400 |
+-----+-----+*****+

purchase 4:
+-----+-----+-----+
|  0  | 200 | 300 |
+-----+-----+-----+
| 600 |  0  |  0  |
+-----+-----+*****+

purchase 5:
+-----+-----+-----+
|  0  |  0  | 300 |
+-----+-----+-----+
| 600 |  0  |  0  |
+-----+*****+-----+

purchase 6:
+-----+-----+-----+
|  0  |  0  | 300 |
+-----+-----+-----+
|  0  |  0  |  0  |
+-----+-----+*****+

final:
+-----+-----+-----+
|  0  |  0  |  0  |
+-----+-----+-----+
|  0  |  0  |  0  |
+*****+-----+-----+

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 whole-number percentage values (1-99).

The third task had too many sub-tasks 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)