TopCoder Algorithm

SRM144-BinaryCode.cs

using System.Text;

public class BinaryCode
{
    public string[] decode(string message)
    {
        int[] messageInts = new int[message.Length];
        {
            for (int i = 0; i < message.Length; i += 1)
                messageInts[i] = message[i] - '0';
        }
        return new string[]
                   {
                       IntArrayToString(DecodeAssumingFirst(messageInts, true)),
                       IntArrayToString(DecodeAssumingFirst(messageInts, false))
                   };
    }

    private string IntArrayToString(int[] array)
    {
        if (array == null) return "NONE";

        StringBuilder builder = new StringBuilder(array.Length);
        {
            for (int i = 0; i < array.Length; i++)
                builder.Append(array[i]);
        }
        return builder.ToString();
    }

    private int[] DecodeAssumingFirst(int[] message, bool firstZero)
    {
        if (message.Length < 1) return null;
        if (message.Length == 1)
        {
            if (firstZero && message[0] == 0 || !firstZero && message[0] == 1)
                return message;
            return null;
        }

        // message.Lengh > 1

        int[] result = new int[message.Length];
        result[0] = firstZero ? 0 : 1;
        result[1] = message[0] - result[0];
        if (result[1] != 0 && result[1] != 1)
            return null;


        for (int i = 2; i < message.Length; i += 1)
        {
            result[i] = message[i - 1] - result[i - 1] - result[i - 2];
            if (result[i] != 0 && result[i] != 1)
                return null;
        }

        if (message[message.Length - 1] != result[message.Length - 1] + result[message.Length - 2])
            return null;

        return result;
    }
}

SRM144-Lottery.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;

public class Lottery
{
    public string[] sortByOdds(string[] rulesStr)
    {
        List<Rule> rules = new List<Rule>(rulesStr.Length);
        {
            for (int i = 0; i < rulesStr.Length; i += 1)
                rules.Add(Rule.Parse(rulesStr[i]));
        }

        rules.Sort(delegate(Rule l, Rule r)
                       {
                           if (Math.Abs(l.LogNPossibleLotteries - r.LogNPossibleLotteries) < 1e-10)
                               return String.CompareOrdinal(l.Name, r.Name);
                           return Comparer<Double>.Default.Compare(l.LogNPossibleLotteries, r.LogNPossibleLotteries);
                       });

        string[] ruleNames = new string[rules.Count];
        {
            for (int i = 0; i < rules.Count; i += 1)
                ruleNames[i] = rules[i].Name;
        }

        return ruleNames;
    }

    internal class Rule
    {
        public Rule(string name, int nChoices, int nBlanks, bool sorted, bool unique)
        {
            Name = name;
            NChoices = nChoices;
            NBlanks = nBlanks;
            Sorted = sorted;
            Unique = unique;
            LogNPossibleLotteries = ComputeLogNPossibleLotteries(nChoices, nBlanks, sorted, unique);
        }

        private static double ComputeLogNPossibleLotteries(int nChoices, int nBlanks, bool sorted, bool unique)
        {
            if (sorted)
            {
                // sorted && uniqe
                if (unique) return Util.LogNCombinatory(nChoices, nBlanks);
                // sorted && !unique
                return Util.LogNCombinatory(nChoices + nBlanks - 1, nBlanks);
            }
            // !sorted && unique
            if (unique) return Util.LogNPermutation(nChoices, nBlanks);
            // !sorted && !unique
            return nBlanks*Math.Log(nChoices);
        }

        public readonly string Name;
        public readonly int NChoices;
        public readonly int NBlanks;
        public readonly bool Sorted;
        public readonly bool Unique;
        public readonly double LogNPossibleLotteries;

        public static Rule Parse(string s)
        {
            int colonPos = s.IndexOf(':');
            string name = s.Substring(0, colonPos);

            string[] tokens = s.Substring(colonPos + 1).Split(" ".ToCharArray(), StringSplitOptions.RemoveEmptyEntries);
            Debug.Assert(tokens.Length == 4);

            int nChoices = int.Parse(tokens[0]);

            int nBlanks = int.Parse(tokens[1]);

            bool sorted = tokens[2] == "T";

            bool unique = tokens[3] == "T";

            return new Rule(name, nChoices, nBlanks, sorted, unique);
        }
    }

    internal static class Util
    {
        public static double LogNCombinatory(int n, int k)
        {
            if (k > n) return double.NegativeInfinity;

            double ans;
            {
                ans = LogNPermutation(n, k);
                for (int i = 1; i <= k; i += 1)
                    ans -= Math.Log(i);
            }

            return ans;
        }

        public static double LogNPermutation(int n, int k)
        {
            if (k > n) return double.NegativeInfinity;
            double ans;
            {
                ans = 0;
                for (int i = n - k + 1; i <= n; i += 1)
                    ans += Math.Log(i);
            }

            return ans;
        }
    }
}

SRM144-PenLift.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Drawing;

public class PenLift
{
    public int numTimes(string[] segmentsStr, int n)
    {
        if (segmentsStr.Length == 0)
            return 0;

        LinkedList<Segment> segments = ParseSegmentsStr(segmentsStr);
        MergeAndSplit(ref segments);

        ICollection<LinkedList<Point>> connctedVertices = ComputeConnetedVertices(segments);

        return computeNumTimes(n, connctedVertices, segments);
    }

    #region Segment data structure

    internal struct Segment
    {
        public readonly Point Start;
        public readonly Point End;

        public int X1
        {
            get { return Start.X; }
        }

        public int Y1
        {
            get { return Start.Y; }
        }

        public int X2
        {
            get { return End.X; }
        }

        public int Y2
        {
            get { return End.Y; }
        }

        public readonly SegmentOrientation Orientation;

        public enum SegmentOrientation
        {
            Horizontal,
            Vertical
        }

        public Segment(int x1, int y1, int x2, int y2)
        {
            Debug.Assert(x1 == x2 || y1 == y2);
            Orientation = x1 == x2 ? SegmentOrientation.Vertical : SegmentOrientation.Horizontal;

            Start = new Point(Math.Min(x1, x2), Math.Min(y1, y2));
            End = new Point(Math.Max(x1, x2), Math.Max(y1, y2));
        }

        public static Segment Parse(string s)
        {
            string[] tokens = s.Split(' ');
            return new Segment(int.Parse(tokens[0]), int.Parse(tokens[1]), int.Parse(tokens[2]), int.Parse(tokens[3]));
        }

        public static bool TestOverlap(Segment l, Segment r)
        {
            return
                l.Orientation == r.Orientation &&
                (
                    l.Orientation == SegmentOrientation.Horizontal &&
                    l.Y1 == r.Y1 &&
                    Math.Max(l.X2, r.X2) - Math.Min(l.X1, r.X1) <= (l.X2 - l.X1) + (r.X2 - r.X1)
                    ||
                    l.Orientation == SegmentOrientation.Vertical &&
                    l.X1 == r.X1 &&
                    Math.Max(l.Y2, r.Y2) - Math.Min(l.Y1, r.Y1) <= (l.Y2 - l.Y1) + (r.Y2 - r.Y1)
                );
        }

        public static Segment Overlap(Segment l, Segment r)
        {
            Debug.Assert(TestOverlap(l, r));
            return new Segment(
                Math.Min(l.X1, r.X1),
                Math.Min(l.Y1, r.Y1),
                Math.Max(l.X2, r.X2),
                Math.Max(l.Y2, r.Y2));
        }

        public static bool TestIntersect(Segment l, Segment r)
        {
            if (l.Orientation == r.Orientation) return false;

            Segment v, h;
            {
                if (l.Orientation == SegmentOrientation.Horizontal)
                {
                    h = l;
                    v = r;
                }
                else
                {
                    h = r;
                    v = l;
                }
            }

            return
                v.Y1 <= h.Y1 && h.Y1 <= v.Y2 &&
                h.X1 <= v.X1 && v.X1 <= h.X2 &&
                v.Start != h.Start && v.End != h.Start &&
                v.Start != h.End && v.End != h.End;
        }

        public static List<Segment> Intersect(Segment l, Segment r)
        {
            Debug.Assert(TestIntersect(l, r));

            Segment v, h;
            {
                if (l.Orientation == SegmentOrientation.Horizontal)
                {
                    h = l;
                    v = r;
                }
                else
                {
                    h = r;
                    v = l;
                }
            }

            int xi = v.X1;
            int yi = h.Y1;

            List<Segment> result = new List<Segment>(4);
            {
                if (h.X1 != xi)
                    result.Add(new Segment(h.X1, h.Y1, xi, h.Y1));
                if (h.X2 != xi)
                    result.Add(new Segment(xi, h.Y1, h.X2, h.Y1));
                if (v.Y1 != yi)
                    result.Add(new Segment(v.X1, v.Y1, v.X1, yi));
                if (v.Y2 != yi)
                    result.Add(new Segment(v.X1, yi, v.X1, v.Y2));
            }

            return result;
        }
    }

    #endregion

    #region Parse

    private LinkedList<Segment> ParseSegmentsStr(IEnumerable<string> segmentsStr)
    {
        LinkedList<Segment> segments = new LinkedList<Segment>();
        foreach (string str in segmentsStr)
            segments.AddLast(Segment.Parse(str));
        return segments;
    }

    #endregion

    #region Merge overlapped and split intersected

    private void MergeAndSplit(ref LinkedList<Segment> segments)
    {
        bool toSplit = false;
        // MUST merge before split!
        do
        {
            LinkedList<Segment> result = new LinkedList<Segment>();

            while (segments.Count != 0)
            {
                Segment seg = segments.First.Value;
                segments.RemoveFirst();

                LinkedListNode<Segment> p = segments.First;
                bool newSegment = false;

                while (p != null && !newSegment)
                {
                    if (!toSplit && Segment.TestOverlap(seg, p.Value))
                    {
                        Segment newSeg = Segment.Overlap(seg, p.Value);
                        p.Value = newSeg;
                        newSegment = true;
                    }
                    else if (toSplit && Segment.TestIntersect(seg, p.Value))
                    {
                        List<Segment> newSegs = Segment.Intersect(seg, p.Value);
                        segments.Remove(p);
                        foreach (Segment newSeg in newSegs)
                            segments.AddFirst(newSeg);
                        newSegment = true;
                    }
                    else
                        p = p.Next;
                }

                if (!newSegment)
                    result.AddLast(seg);
            }

            segments = result;

            toSplit = !toSplit;
        } while (toSplit);
    }

    #endregion

    #region Find connected vertices

    internal class PointDisJointSets
    {
        private readonly Dictionary<Point, Point> _parent = new Dictionary<Point, Point>();
        private readonly Dictionary<Point, int> _rank = new Dictionary<Point, int>();

        public ICollection<Point> Points
        {
            get { return _parent.Keys; }
        }

        public void Add(Point point)
        {
            if (_parent.ContainsKey(point)) return;
            _parent[point] = point;
            _rank[point] = 0;
        }

        public Point FindRoot(Point point)
        {
            Point parent = _parent[point];
            if (parent.Equals(point))
                return point;

            Point root = FindRoot(parent);
            _parent[point] = root;
            return root;
        }

        public void Union(Point point1, Point point2)
        {
            Add(point1);
            Add(point2);
            Point root1 = FindRoot(point1);
            Point root2 = FindRoot(point2);
            if (root1.Equals(root2))
                return;

            int rank1 = _rank[root1];
            int rank2 = _rank[root2];
            if (rank1 < rank2)
                _parent[root1] = root2;
            else if (rank2 < rank1)
                _parent[root2] = root1;
            else
            {
                _parent[root1] = root2;
                _rank[root2] += 1;
            }
        }
    }

    private ICollection<LinkedList<Point>> ComputeConnetedVertices(IEnumerable<Segment> segments)
    {
        PointDisJointSets ds = new PointDisJointSets();
        foreach (Segment seg in segments)
            ds.Union(seg.Start, seg.End);

        Dictionary<Point, LinkedList<Point>> rootToPoint = new Dictionary<Point, LinkedList<Point>>();

        foreach (Point point in new List<Point>(ds.Points))
        {
            Point root = ds.FindRoot(point);
            if (!rootToPoint.ContainsKey(root))
                rootToPoint[root] = new LinkedList<Point>();
            rootToPoint[root].AddLast(point);
        }

        return rootToPoint.Values;
    }

    #endregion

    #region Compute times of pen-lift using Eulerian path theroems

    private int computeNumTimes(int n, ICollection<LinkedList<Point>> connctedVertices, LinkedList<Segment> segments)
    {
        if (n%2 == 0)
            return connctedVertices.Count - 1;

        Dictionary<Point, int> pointsToCounts = CountPoints(segments);
        int ans = -1;
        foreach (LinkedList<Point> points in connctedVertices)
        {
            int oddCount = CountVertexWithOddDegree(points, pointsToCounts);
            if (oddCount == 0)
                ans += 1;
            else
                ans += oddCount/2;
        }
        return ans;
    }

    private static int CountVertexWithOddDegree(IEnumerable<Point> points, Dictionary<Point, int> pointsToCounts)
    {
        int oddCount = 0;
        foreach (Point point in points)
            if (pointsToCounts[point]%2 == 1)
                oddCount += 1;
        return oddCount;
    }

    private Dictionary<Point, int> CountPoints(IEnumerable<Segment> segments)
    {
        Dictionary<Point, int> answer = new Dictionary<Point, int>();
        foreach (Segment seg in segments)
        {
            if (answer.ContainsKey(seg.Start))
                answer[seg.Start] += 1;
            else
                answer[seg.Start] = 1;

            if (answer.ContainsKey(seg.End))
                answer[seg.End] += 1;
            else
                answer[seg.End] = 1;
        }

        return answer;
    }
    
    #endregion
}

SRM561-FoxAndTouristFamilies.cs

using System.Collections.Generic;
using System.Diagnostics;
using TopCoder.Srm561;

public class FoxAndTouristFamilies
{
    public double expectedLength(int[] A, int[] B, int[] f)
    {
        DAG dag = new DAG(A, B);

        double[,] edgeProb = new double[dag.NNodes,dag.NNodes];
        for (int i = 0; i < A.Length; i += 1)
            edgeProb[A[i], B[i]] = edgeProb[B[i], A[i]] = 1;

        foreach (int n in f)
            foreach (DAG.Edge edge in dag.FloodFillFrom(n))
            {
                double p = dag.ConnectedComponentSize(edge.Node2, edge.Node1)/(dag.NNodes - 1.0);
                edgeProb[edge.Node1, edge.Node2] *= p;
                edgeProb[edge.Node2, edge.Node1] *= p;
            }

        double ans = 0;
        for (int i = 0; i < A.Length; i += 1)
            ans += edgeProb[A[i], B[i]];
        return ans;
    }
}

namespace TopCoder.Srm561
{
    internal class DAG
    {
        public class Edge
        {
            private readonly int _node1;
            private readonly int _node2;

            public Edge(int node1, int node2)
            {
                _node1 = node1;
                _node2 = node2;
            }

            public int Node1
            {
                get { return _node1; }
            }

            public int Node2
            {
                get { return _node2; }
            }

            public override string ToString()
            {
                return string.Format("({0}~{1})", Node1, Node2);
            }
        }

        // We should use Dictionary<int, HashSet<int>>, but since topcoder is still on .NET 2.0...
        private readonly Dictionary<int, Dictionary<int, bool>> _neighbors;

        private readonly int[,] _connCompSize;
        private readonly bool[,] _connCompSizeFlag;

        public int NNodes
        {
            get { return _neighbors.Count; }
        }

        public ICollection<int> NeighborsOf(int node)
        {
            Debug.Assert(node < NNodes);
            return _neighbors[node].Keys;
        }

        public DAG(int[] A, int[] B)
        {
            _neighbors = new Dictionary<int, Dictionary<int, bool>>();
            for (int i = 0; i < A.Length; i += 1)
            {
                if (!_neighbors.ContainsKey(A[i]))
                    _neighbors[A[i]] = new Dictionary<int, bool>();
                if (!_neighbors.ContainsKey(B[i]))
                    _neighbors[B[i]] = new Dictionary<int, bool>();

                _neighbors[A[i]][B[i]] = true;
                _neighbors[B[i]][A[i]] = true;
            }

            _connCompSize = new int[NNodes,NNodes];
            _connCompSizeFlag = new bool[NNodes,NNodes];
        }

        /// <returns>
        /// Number of nodes in the connected component which node1 belongs to,
        /// if edge (<para>node1</para>,<para>node2</para>) were removed.
        /// </returns>
        public int ConnectedComponentSize(int node1, int node2)
        {
            Debug.Assert(node1 < NNodes && node2 < NNodes &&
                         NeighborsOf(node1).Contains(node2) &&
                         NeighborsOf(node2).Contains(node1));

            if (_connCompSizeFlag[node1, node2]) return _connCompSize[node1, node2];


            if (NeighborsOf(node1).Count == 1)
                _connCompSize[node1, node2] = 1;
            else
            {
                foreach (int n in NeighborsOf(node1))
                    if (n != node2)
                        _connCompSize[node1, node2] += ConnectedComponentSize(n, node1);
                _connCompSize[node1, node2] += 1; // count node1 itself
            }

            _connCompSizeFlag[node1, node2] = true;
            return _connCompSize[node1, node2];
        }

        public IEnumerable<Edge> FloodFillFrom(int node)
        {
            Debug.Assert(node < NNodes);

            bool[] flags = new bool[NNodes];

            Queue<int> queue = new Queue<int>();
            flags[node] = true;
            queue.Enqueue(node);

            while (queue.Count > 0)
            {
                int n = queue.Dequeue();
                foreach (int nbr in NeighborsOf(n))
                    if (!flags[nbr])
                    {
                        flags[nbr] = true;
                        queue.Enqueue(nbr);
                        yield return new Edge(n, nbr);
                    }
            }
        }
    }
}

SRM561-FoxAndVacation.cs

using System;

public class FoxAndVacation
{
    // Good old 0-1 backpack problem
    public int maxCities(int total, int[] d)
    {
        if (d.Length == 0) return 0;

        int[,] nCities = new int[51,50];

        for (int t = 1; t <= total; t += 1)
        {
            nCities[t, 0] = t >= d[0] ? 1 : 0;
            for (int j = 1; j <= d.Length - 1; j += 1)
            {
                int c = t >= d[j] ? nCities[t - d[j], j - 1] + 1 : 0;
                nCities[t, j] = Math.Max(c, nCities[t, j - 1]);
            }
        }

        return nCities[total, d.Length - 1];
    }
}

SRM561-ICPCBalloons.cs

using System;
using System.Collections.Generic;

public class ICPCBalloons
{
    public int minRepaintings(int[] colorCount, string colorSizeStr, int[] probMaxAccepted)
    {
        const uint SIZE_M = 0U;
        const uint SIZE_L = 1U;

        #region Prep

        int[][] sizeColorCounts = new int[2][];
        int[] sizeCountSum = new int[2];
        {
            List<int> MColorCounts = new List<int>(colorCount.Length);
            List<int> LColorCounts = new List<int>(colorCount.Length);

            for (int i = 0; i < colorCount.Length; i += 1)
                switch (colorSizeStr[i])
                {
                    case 'M':
                        MColorCounts.Add(colorCount[i]);
                        sizeCountSum[SIZE_M] += colorCount[i];
                        break;
                    case 'L':
                        LColorCounts.Add(colorCount[i]);
                        sizeCountSum[SIZE_L] += colorCount[i];
                        break;
                }

            // Sorting enables us to be greedy in the assignment of colors to problems. Same below.
            MColorCounts.Sort(Descending);
            sizeColorCounts[SIZE_M] = MColorCounts.ToArray();

            LColorCounts.Sort(Descending);
            sizeColorCounts[SIZE_L] = LColorCounts.ToArray();
        }

        #endregion

        #region Search

        int ans = int.MaxValue;

        // Enumerate all possible assignments of balloon sizes (M or L) to problems
        // There're at most 2^15 different assignment, which is acceptable
        for (uint probSizeAssign = 0; probSizeAssign < 1U << probMaxAccepted.Length; probSizeAssign += 1)
        {
            int[][] currSizeColorCounts = new int[2][];
            {
                int[] currSizeCountSum = new int[2];
                List<int> MColorCounts = new List<int>(probMaxAccepted.Length);
                List<int> LColorCounts = new List<int>(probMaxAccepted.Length);

                for (int i = 0; i < probMaxAccepted.Length; i += 1)
                    switch ((probSizeAssign >> i) & 1U)
                    {
                        case SIZE_M:
                            MColorCounts.Add(probMaxAccepted[i]);
                            currSizeCountSum[SIZE_M] += probMaxAccepted[i];
                            break;
                        case SIZE_L:
                            LColorCounts.Add(probMaxAccepted[i]);
                            currSizeCountSum[SIZE_L] += probMaxAccepted[i];
                            break;
                    }

                // This assignments of balloon sizes is impossible, not enough balloons of either size 
                if (currSizeCountSum[SIZE_L] > sizeCountSum[SIZE_L] || currSizeCountSum[SIZE_M] > sizeCountSum[SIZE_M])
                    continue;

                MColorCounts.Sort(Descending);
                currSizeColorCounts[SIZE_M] = MColorCounts.ToArray();

                LColorCounts.Sort(Descending);
                currSizeColorCounts[SIZE_L] = LColorCounts.ToArray();
            }

            // Greedily pick colors and paint balloons when necessary
            // Since both sizeColorCounts[ml] and currSizeColorCounts[ml] are sorted in descending order,
            // to minimize the number of balloons to repaint,
            // the colors of currSizeColorCounts[ml][i] and sizeColorCounts[ml][i] can be the same
            int currAns = 0;
            for (int ml = 0; ml <= 1; ml += 1)
            {
                for (int i = 0; i < Math.Min(sizeColorCounts[ml].Length, currSizeColorCounts[ml].Length); i += 1)
                    if (sizeColorCounts[ml][i] < currSizeColorCounts[ml][i])
                        currAns += currSizeColorCounts[ml][i] - sizeColorCounts[ml][i];
                for (int i = sizeColorCounts[ml].Length; i < currSizeColorCounts[ml].Length; i += 1)
                    // This is as if sizeColorCounts[ml][i] == 0
                    currAns += currSizeColorCounts[ml][i];
            }

            ans = Math.Min(ans, currAns);
        }

        #endregion

        return ans == int.MaxValue ? -1 : ans;
    }

    private int Descending(int l, int r)
    {
        return r.CompareTo(l);
    }
}

SRM562-PastingPaintingDivTwo.cs

public class PastingPaintingDivTwo
{
    public long countColors(string[] clipboard, int T)
    {
        int nRow = clipboard.Length;
        if (nRow == 0) return 0;

        int nCol = clipboard[0].Length;
        if (nCol == 0) return 0;

        long ans = 0;

        // (r0,c0) enumerates pixels in the first row and the first column
        for (int r0 = 0; r0 < nRow; r0 += 1)
        {
            for (int c0 = 0; c0 < (r0 == 0 ? nCol : 1); c0 += 1)
            {
                // Each diagnal is seen as an one dimensional line,
                // in which the pixels are indexed by i in the inner loop
                // r and c in the inner loop enumerates pixels on the diagnal line starting with (r0,c0)
                // Each 'B' in clipboard corresponds to a segment in the diagnal line,
                // and the problem becomes how many pixels these segments cover

                // Start & end index of the segment that potentially overlaps subsequent segments
                // -1 means we haven't encountered any segments on this diagnal line
                int segStart = -1, segEnd = -1;

                // i, r, c are explained as above
                for (int i = 0, r = r0, c = c0; r < nRow && c < nCol; i += 1, r += 1, c += 1)
                {
                    if (clipboard[r][c] == 'B')
                    {
                        int currSegStart = i, currSegEnd = i + T - 1;
                        if (segStart == -1) // The first segment we see on the diagnal line
                        {
                            segStart = currSegStart;
                            segEnd = currSegEnd;
                        }
                        else if (currSegStart <= segEnd) // The new segment overlaps with the one we have, merge them
                        {
                            if (currSegEnd > segEnd)
                                segEnd = currSegEnd;
                        }
                        else // The new segment doesn't overlap with the one we have...
                        {
                            // Count how many pixels are covered...
                            // (note that future segments won't overlap with this one, so we can abandon it now)
                            ans += segEnd - segStart + 1;

                            // .. and replace it with the new segment
                            segStart = currSegStart;
                            segEnd = currSegEnd;
                        }
                    }
                }

                // Handle the last uncounted segment
                if (segStart != -1)
                    ans += segEnd - segStart + 1;
            }
        }

        return ans;
    }
}