TopCoder SRM 146 DIV2 problems and solutions

Back in the gym...

I had my first workout today, but I still have work to post from my week of sickness/coding.

I started to work my way up from the first available SRM in the Arena. (only 10 years worth of competitions ahead)

This is the third set of problems I have solved.

Official Pages

Here is the official page of the competition.

And this is the editorial page.

Lets check 'em solutions out...

Task: Yahtzee

Problem Statement
    

This task is about the scoring in the first phase of the die-game Yahtzee, where five dice are used. The score is determined by the values on the upward die faces after a roll. The player gets to choose a value, and all dice that show the chosen value are considered active. The score is simply the sum of values on active dice.

Say, for instance, that a player ends up with the die faces showing 2, 2, 3, 5 and 4. Choosing the value two makes the dice showing 2 active and yields a score of 2 + 2 = 4, while choosing 5 makes the one die showing 5 active, yielding a score of 5.

Your method will take as input a int[] toss, where each element represents the upward face of a die, and return the maximum possible score with these values.

Definition
    
Class: YahtzeeScore
Method: maxPoints
Parameters: int[]
Returns: int
Method signature: int maxPoints(int[] toss)
(be sure your method is public)
    
 

Constraints
- toss will contain exactly 5 elements.
- Each element of toss will be between 1 and 6, inclusive.

Examples
0)  
     
{ 2, 2, 3, 5, 4 }
 
Returns: 5
The example from the text.
1)  
     
{ 6, 4, 1, 1, 3 }
 
Returns: 6
Selecting 1 as active yields 1 + 1 = 2, selecting 3 yields 3, selecting 4 yields 4 and selecting 6 yields 6, which is the maximum number of points.
2)  
     
{ 5, 3, 5, 3, 3 }
 
Returns: 10
 

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 YahtzeeScore
{
    public int maxPoints(int[] toss)
    {
        int[] faces = new int[6];
        int highest = 0, face, index;
        for (int i = 0; i < 5; i++)
        {
            face = toss[i];
            index = face - 1;
            faces[index] += face;
            if (faces[index] > highest)
            {
                highest = faces[index];
            }
        }
        return highest;
    }
}

Task: Rectengular Grid

Problem Statement
    

Given the width and height of a rectangular grid, return the total number of rectangles (NOT counting squares) that can be found on this grid.

For example, width = 3, height = 3 (see diagram below):

 __ __ __
|__|__|__|
|__|__|__|
|__|__|__|

In this grid, there are 4 2x3 rectangles, 6 1x3 rectangles and 12 1x2 rectangles. Thus there is a total of 4 + 6 + 12 = 22 rectangles. Note we don't count 1x1, 2x2 and 3x3 rectangles because they are squares.

Definition
    
Class: RectangularGrid
Method: countRectangles
Parameters: int, int
Returns: long
Method signature: long countRectangles(int width, int height)
(be sure your method is public)
    
 

Notes
- rectangles with equals sides (squares) should not be counted.

Constraints
- width and height will be between 1 and 1000 inclusive.

Examples
0)  
     
3
 
3
 
Returns: 22
See above
1)  
     
5
 
2
 
Returns: 31
 
 __ __ __ __ __
|__|__|__|__|__|
|__|__|__|__|__|

In this grid, there is one 2x5 rectangle, 2 2x4 rectangles, 2 1x5 rectangles, 3 2x3 rectangles, 4 1x4 rectangles, 6 1x3 rectangles and 13 1x2 rectangles. Thus there is a total of 1 + 2 + 2 + 3 + 4 + 6 + 13 = 31 rectangles.
2)  
     
10
 
10
 
Returns: 2640
 
3)  
     
1
 
1
 
Returns: 0
 
4)  
     
592
 
964
 
Returns: 81508708664
 

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 RectangularGrid
{
    public long countRectangles(int width, int height)
    {
        long result = 0;
        for (int i = 1; i <= width; i++)
        {
            for (int j = 1; j <= height; j++)
            {
                if (i != j)
                {
                    result += (width - i + 1) * (height - j + 1);
                }
            }
        }
        return result;
    }
}

Task: Bridge Crossing

Problem Statement
    

A well-known riddle goes like this: Four people are crossing an old bridge. The bridge cannot hold more than two people at once. It is dark, so they can't walk without a flashlight, and they only have one flashlight! Furthermore, the time needed to cross the bridge varies among the people in the group. For instance, let's say that the people take 1, 2, 5 and 10 minutes to cross the bridge. When people walk together, they always walk at the speed of the slowest person. It is impossible to toss the flashlight across the bridge, so one person always has to go back with the flashlight to the others. What is the minimum amount of time needed to get all the people across the bridge?

In this instance, the answer is 17. Person number 1 and 2 cross the bridge together, spending 2 minutes. Then person 1 goes back with the flashlight, spending an additional one minute. Then person 3 and 4 cross the bridge together, spending 10 minutes. Person 2 goes back with the flashlight (2 min), and person 1 and 2 cross the bridge together (2 min). This yields a total of 2+1+10+2+2 = 17 minutes spent.

You want to create a computer program to help you solve new instances of this problem. Given an int[] times, where the elements represent the time each person spends on a crossing, your program should return the minimum possible amount of time spent crossing the bridge.

Definition
    
Class: BridgeCrossing
Method: minTime
Parameters: int[]
Returns: int
Method signature: int minTime(int[] times)
(be sure your method is public)
    
 

Notes
- In an optimal solution, exactly two people will be sent across the bridge with the flashlight each time (if possible), and exactly one person will be sent back with the flashlight each time. In other words, in an optimal solution, you will never send more than one person back from the far side at a time, and you will never send less than two people across to the far side each time (when possible).

Constraints
- times will have between 1 and 6 elements, inclusive.
- Each element of times will be between 1 and 100, inclusive.

Examples
0)  
     
{ 1, 2, 5, 10 }
 
Returns: 17
The example from the text.
1)  
     
{ 1, 2, 3, 4, 5 }
 
Returns: 16
One solution is: 1 and 2 cross together (2min), 1 goes back (1min), 4 and 5 cross together (5min), 2 goes back (2min), 1 and 3 cross together (3min), 1 goes back (1min), 1 and 2 cross together (2min). This yields a total of 2 + 1 + 5 + 2 + 3 + 1 + 2 = 16 minutes spent.
2)  
     
{ 100 }
 
Returns: 100
Only one person crosses the bridge once.
3)  
     
{ 1, 2, 3, 50, 99, 100 }
 
Returns: 162
 

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.Collections.Generic;
class BridgeCrossing
{
    public int minTime(int[] times)
    {
        Array.Sort(times);
        if (times.Length == 1)
        {
            return times[0];
        }
        else if (times.Length == 2)
        {
            return Math.Max(times[0], times[1]);
        }

        List<int> right = new List<int>(times);
        List<int> left = new List<int>();

        int time = 0;
        bool moveLeft = true;
        // -1 0 1
        int probeStage = 1;
        while (right.Count > 0)
        {
            if (moveLeft)
            {
                int first, second;
                switch (probeStage)
                {
                    case 1:
                        first = right[0];
                        second = right[1];
                        left.Insert(0, first);
                        left.Insert(1, second);
                        right.RemoveRange(0, 2);
                        time += second;
                        probeStage = -1;
                        break;
                    case 0:
                        int lastIndex = right.Count - 1;
                        first = right[lastIndex - 1];
                        second = right[lastIndex];
                        left.Add(first);
                        left.Add(second);
                        right.RemoveRange(lastIndex - 1, 2);
                        time += second;
                        break;
                }
                moveLeft = false;
            }
            else
            {
                int firstLeft = left[0];
                int firstRight = right[0];
                left.RemoveAt(0);
                int index = 1;
                if (firstLeft < firstRight)
                {
                    index = 0;
                }
                right.Insert(index, firstLeft);
                probeStage++;
                moveLeft = true;
                time += firstLeft;
            }
        }
        return time;
    }
}

Summary

I am particularly proud of my solution to the Rectangular Grid problem. What I am doing there is:

  • Iterate through all possible rectangles which are not square (i ≠ j) and can be contained into the main rectangle.
  • calculate the number of times this shapes can be placed within the main rectangle.

Analytically, I managed to derive to calculate their number:

    (x - x0 + 1) * (y - y0 + 1) for every inner rectangle.

I think the solution was quite elegant and compact.

Bridge Crossing wasn't very hard to see through (luck maybe). The algorithm is consistent of the repetition of this complex action:

  1. Get the fastest couple on the left side;
  2. Return the fastest element back on the right side;
  3. Get the slowest (with highest sum, also) couple on the left side;
  4. Return the second element passed in step 1. back on the right.

​​This is repeated until all elements are on the left side.

For ease I am sorting the elements at the beginning and then always insert at sorted positions the elements I am moving.

I hope my solutions (and bragging) would be of assistance to you, dear reader.

Довиждане! ("See you!" in Bulgarian)