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 diegame 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 



Constraints 

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

0)  


1)  


2)  

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 



Notes 

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

  width and height will be between 1 and 1000 inclusive.  
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 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 wellknown 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 



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)  


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; 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:
 Get the fastest couple on the left side;
 Return the fastest element back on the right side;
 Get the slowest (with highest sum, also) couple on the left side;
 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)