I got the flu...
I spent some time at home (since last Friday), sick, and I decided to do some programming contest problems.
This will be the first of series of posts about problems and solutions of old (if I participate in an actual competition, then new as well) TopCoder problems.
SRM (SingleRound Match) 144 DIV2 (the 2nd division)
This competition was held on 30 April 2003. It was the oldest available in the TopCoder Arena (app, in which coders compete and practice on old tasks).
Official page for the competition
Here is the official page with statitics, winners and problem statements.
And here is the official "editorials" (summary of the best approaches to the problem's solutions).
Lets check out the tasks and my solutions...
Task: Time
Problem Statement 

Computers tend to store dates and times as single numbers which represent the number of seconds or milliseconds since a particular date. Your task in this problem is to write a method whatTime, which takes an int, seconds, representing the number of seconds since midnight on some day, and returns a string formatted as "<H>:<M>:<S>". Here, <H> represents the number of complete hours since midnight, <M> represents the number of complete minutes since the last complete hour ended, and <S> represents the number of seconds since the last complete minute ended. Each of <H>, <M>, and <S> should be an integer, with no extra leading 0's. Thus, if seconds is 0, you should return "0:0:0", while if seconds is 3661, you should return "1:1:1".  
Definition 



Constraints 

  seconds will be between 0 and 24*60*60  1 = 86399, 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; public class Time { public string whatTime(int seconds) { int hConst = 3600; int mConst = 60; int hours = seconds / hConst; seconds = seconds % hConst; int mins = seconds / mConst; seconds = seconds % mConst; return hours + ":" + mins + ":" + seconds; } }
Task: Binary Code
Problem Statement 

Let's say you have a binary string such as the following: 011100011 One way to encrypt this string is to add to each digit the sum of its adjacent digits. For example, the above string would become: 123210122 In particular, if P is the original string, and Q is the encrypted string, then Q[i] = P[i1] + P[i] + P[i+1] for all digit positions i. Characters off the left and right edges of the string are treated as zeroes. An encrypted string given to you in this format can be decoded as follows (using 123210122 as an example):
Now we repeat the process, assuming the opposite about P[0]:
Note that this algorithm produces at most two decodings for any given encrypted string. There can never be more than one possible way to decode a string once the first binary digit is set. Given a string message, containing the encrypted string, return a string[] with exactly two elements. The first element should contain the decrypted string assuming the first character is '0'; the second element should assume the first character is '1'. If one of the tests fails, return the string "NONE" in its place. For the above example, you should return {"011100011", "NONE"}. 

Definition 



Constraints 

  message will contain between 1 and 50 characters, inclusive.  
  Each character in message will be either '0', '1', '2', or '3'.  
Examples 

0)  


1)  


2)  


3)  


4)  


5)  

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; public class BinaryCode { public string[] decode(string message) { short[] coded = new short[message.Length]; char[] digitChars = message.ToCharArray(); for (short i = 0; i < digitChars.Length; i ++) { coded[i] = Int16.Parse(Convert.ToString(digitChars[i])); } return new string[] { this.DecodeWithAssumption(0, coded), this.DecodeWithAssumption(1, coded) }; } private string DecodeWithAssumption(short first, short[] coded) { int length = coded.Length; short[] init = new short[length]; init[0] = first; for (short i = 1; i < coded.Length; i++) { // P(n) = Q(n  1)  P(n  2)  P(n  1); short digit = (short)(this.GetDigit(i  1, coded)  this.GetDigit(i  2, init)  this.GetDigit(i  1, init)); if (digit == 1  digit == 0) { init[i] = digit; } else { return "NONE"; } } for (short i = 0; i < init.Length; i++) { // Q(n) = P(n  1) + P(n) + P(n + 1); short checkValue = (short)(this.GetDigit(i  1, init) + this.GetDigit(i, init) + this.GetDigit(i + 1, init)); if (checkValue != coded[i]) { return "NONE"; } } return String.Join("", Array.ConvertAll<short, string>(init, Convert.ToString)); } private short GetDigit(int index, short[] arr) { if (index < 0  index >= arr.Length) { return 0; } else { return arr[index]; } } }
Task: Power Outage
Problem Statement 

You work for an electric company, and the power goes out in a rather large apartment complex with a lot of irate tenants. You isolate the problem to a network of sewers underneath the complex with a stepup transformer at every junction in the maze of ducts. Before the power can be restored, every transformer must be checked for proper operation and fixed if necessary. To make things worse, the sewer ducts are arranged as a tree with the root of the tree at the entrance to the network of sewers. This means that in order to get from one transformer to the next, there will be a lot of backtracking through the long and claustrophobic ducts because there are no shortcuts between junctions. Furthermore, it's a Sunday; you only have one available technician on duty to search the sewer network for the bad transformers. Your supervisor wants to know how quickly you can get the power back on; he's so impatient that he wants the power back on the moment the technician okays the last transformer, without even waiting for the technician to exit the sewers first. You will be given three int[]'s: fromJunction, toJunction, and ductLength that represents each sewer duct. Duct i starts at junction (fromJunction[i]) and leads to junction (toJunction[i]). ductlength[i] represents the amount of minutes it takes for the technician to traverse the duct connecting fromJunction[i] and toJunction[i]. Consider the amount of time it takes for your technician to check/repair the transformer to be instantaneous. Your technician will start at junction 0 which is the root of the sewer system. Your goal is to calculate the minimum number of minutes it will take for your technician to check all of the transformers. You will return an int that represents this minimum number of minutes. 

Definition 



Constraints 

  fromJunction will contain between 1 and 50 elements, inclusive.  
  toJunction will contain between 1 and 50 elements, inclusive.  
  ductLength will contain between 1 and 50 elements, inclusive.  
  toJunction, fromJunction, and ductLength must all contain the same number of elements.  
  Every element of fromJunction will be between 0 and 49 inclusive.  
  Every element of toJunction will be between 1 and 49 inclusive.  
  fromJunction[i] will be less than toJunction[i] for all valid values of i.  
  Every (fromJunction[i],toJunction[i]) pair will be unique for all valid values of i.  
  Every element of ductlength will be between 1 and 2000000 inclusive.  
  The graph represented by the set of edges (fromJunction[i],toJunction[i]) will never contain a loop, and all junctions can be reached from junction 0.  
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; public class PowerOutage { public int estimateTimeOut(int[] fromJunction, int[] toJunction, int[] ductLength) { int fullTime = 0; foreach (int timeSpan in ductLength) { fullTime += timeSpan * 2; } return fullTime  this.GetBiggestTimeSpanFrom(0, fromJunction, toJunction, ductLength); } private int GetBiggestTimeSpanFrom(int start, int[] fromJunction, int[] toJunction, int[] ductLength) { int duration = 0; for (int i = 0; i < toJunction.Length; i++) { if (fromJunction[i] == start) { duration = Math.Max(duration, ductLength[i] + this.GetBiggestTimeSpanFrom(toJunction[i], fromJunction, toJunction, ductLength)); } } return duration; } }
Summary
As you can see my solutions are written in C#. You probably are wondering why do I always explicitly specify the type of all variables?
Well, in the TopCoder arena only .NET 2.0 is supported and with this only an old C# spec as well. So no vars, no LINQ. Unfortunately.
Without too much to say about the first problem, BinaryCode was pretty fun one and PowerOutage was pretty hard (of course for me) to grasp.
BinaryCode gets straight forward once you come up with the 2 formulas (in comments, check the solution).
PowerOutage needs careful examination of the problem statement and really the hard thing about it, is to find out that:
2 * (the sum of all distances)  (the longest distance)
is actually what you need to calculate. From here the harder task is to calculate the longest path. I have written a very elegant solution to this problem (check the recursive method), but the idea was from a contestant with nickname KodeFuPanda. If you ever read this  You Rock!
I hope this was interesting and fun for you guys. Ð”Ð¾ ÑÐºÐ¾Ñ€Ð¾! ("see you soon" in Bulgarian)