5
\$\begingroup\$

Problem statement

The city of Gridland is represented as an n X m matrix where the rows are numbered from 1 to n and the columns are numbered from 1 to m.

Gridland has a network of train tracks that always run in straight horizontal lines along a row. In other words, the start and end points of a train track are (r, c1) and (r, c2), where r represents the row number, c1 represents the starting column, and c2 represents the ending column of the train track.

The mayor of Gridland is surveying the city to determine the number of locations where lampposts can be placed. A lamppost can be placed in any cell that is not occupied by a train track.

Given a map of Gridland and its k train tracks, find and print the number of cells where the mayor can place lampposts.

Note: A train track may (or may not) overlap other train tracks within the same row.

Input Format

The first line contains three space-separated integers describing the respective values of n(the number of rows), m (the number of columns), and k (the number of train tracks).

Each line i of the k subsequent lines contains three space-separated integers describing the respective values of r, c1, and c2 that define a train track.

Constraints

• 1 ≤ n, m ≤ 109

• 0 ≤ k ≤ 1000

• 1 ≤ r ≤ n

• 1 ≤ c1 ≤ c2 ≤ m

Output Format

Print a single integer denoting the number of cells where the mayor can install lampposts.

Sample Input

4 4 3

2 2 3

3 1 4

4 4 4

Sample Output

9

Explanation

enter image description here

In the diagram above, the yellow cells denote the first train track, green denotes the second, and blue denotes the third. Lampposts can be placed in any of the nine red cells, so we print 9 as our answer.

My introduction of algorithm

The Gridland Metro is the medium level algorithm in the contest of Hackerrank World CodeSprint 7 in Sept. 2016. I did manage to solve the algorithm in the contest but I spend too many hours, problems are related to runtime error and timeout, the test cases I used in the code does not help to figure out the issue. Since n,m and k are with large value and I did not have good techniques to work on simulation of large test cases, I examined the code and remembered the coding guideline phrase "express the intent", and then change a for loop to one statement to get distinct rows with train tracks first, in the function CalculateNumberOfCellsTakenByTrainTracks, first statement:var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray().

Today I spent near 2 hours to review the C# algorithm, and put together the readable code, I have to relearn the algorithm and also write code with less smells, with some instructional notes.

The code passes all test cases on hackerrank.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GridlandMetro
{
    /*
     * problem statement:
     * https://www.hackerrank.com/contests/world-codesprint-7/challenges/gridland-metro
     */
    public class MyComparer : IComparer<Tuple<int, int>>
    {
        public int Compare(Tuple<int, int> x, Tuple<int, int> y)
        {
            return (x.Item1 - y.Item1);
        }
    }

    class Program
    {                    
        static void Main(string[] args)
        {
            //RunSampleTestcase(); 
            //RunSampleTestcase2();
            ProcessInput();
        }

        /*
         * Sample test case in the problem statement. 
         * The result should be 9 since 
         * 7 cells are taken by 3 train tracks.
         */
        private static void RunSampleTestcase()
        {          
            int k = 3;
            int rows = 4; 
            int columns = 4; 

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTrackColumns = new List<Tuple<int, int>>();

            var trainTracks = new int[3, 3]{
                {2,2,3},
                {3,1,4}, 
                {4,4,4}
            };

            for (int i = 0; i < k; i++)
            {
                int row = trainTracks[i, 0];
                int startColumn = trainTracks[i, 1];
                int endColumn   = trainTracks[i, 2];

                rowsOfTrainTracks.Add(row);
                trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
            long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
            Debug.Assert(cellsForLampposts == 9); 
        }

        /*
         * Test case: 
         * Row No 2: 4 train tracks, 8 cells are taken by 4 train tracks.
         * 1 - 4 reserved for train track - merge two of [1,4],[2,3] 
         * 6 - 7 train track
         * 9 - 9 train track
         */
        private static void RunSampleTestcase2()
        {
            int k = 5;  // 5 train tracks

            int rows = 2;
            int columns = 10; 

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTrackColumns = new List<Tuple<int, int>>();

            var trainTracks = new int[5, 3]{
                {2,8,9},
                {2,2,3},
                {1,1,4}, 
                {2,1,4},
                {2,6,7}
            };

            for (int i = 0; i < k; i++)
            {
                int row = trainTracks[i, 0];
                int startColumn = trainTracks[i, 1];
                int endColumn = trainTracks[i, 2];

                rowsOfTrainTracks.Add(row);
                trainTrackColumns.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long cellNumberTakenByTrainTracks = CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTrackColumns);
            long cellsForLampposts = rows * columns - cellNumberTakenByTrainTracks;
            Debug.Assert(cellsForLampposts == 8);
        }

        public static void ProcessInput()
        {
            string[] summaryRow = Console.ReadLine().Split(' ');
            int rowNumber = Convert.ToInt32(summaryRow[0]);
            int columnNumber = Convert.ToInt32(summaryRow[1]);
            int k = Convert.ToInt32(summaryRow[2]);

            var map = new int[k];
            var rowsOfTrainTracks = new List<int>();
            var trainTracks = new List<Tuple<int, int>>();

            for (int i = 0; i < k; i++)
            {
                var rowData = Console.ReadLine().Split(' ');

                int rowNo = Convert.ToInt32(rowData[0]);
                int startColumn = Convert.ToInt32(rowData[1]);
                int endColumn = Convert.ToInt32(rowData[2]);

                rowsOfTrainTracks.Add(rowNo);
                trainTracks.Add(new Tuple<int, int>(startColumn, endColumn));
            }

            long sum = rowNumber;
            sum *= columnNumber;

            Console.WriteLine(sum - CalculateNumberOfCellsTakenByTrainTracks(rowsOfTrainTracks, trainTracks));
        }

        /*
         * requirement:
         * 1. Lampposts can not be placed on a train track
         * 2. Train track is always on horizontal row, and train tracks may overlap other train tracks
         * within the same row
         * 3. Calculate the number of cells where the mayor can place lampposts
         * 
         * Design: 
         * merge intervals for each row - it is classical problem of Leetcode 56: Merge Intervals
         * 
         * @rowsOfTrainTracks - row number for each train track
         * @trainTracks - train track's start column and end column 
         * 
         * train tracks row information: rowsOfTrainTracks
         * and each train track's columns information are stored in trainTracks respectively
         * 
         */
        public static long CalculateNumberOfCellsTakenByTrainTracks(
            IList<int>             rowsOfTrainTracks,
            IList<Tuple<int, int>> trainTracks
            )
        {
            var distinctRowsOfTrainTracks = rowsOfTrainTracks.Distinct().ToArray();
            Array.Sort(distinctRowsOfTrainTracks);            

            long sum = 0;
            var trainTracksRows = rowsOfTrainTracks.ToArray();

            foreach (int row in distinctRowsOfTrainTracks)
            {
                var numberOfTrainTracks = rowsOfTrainTracks.Count(a => a == row);                

                int index = 0;
                int start = 0;

                var trainTracksOnSameRow = new List<Tuple<int, int>>();
                while (index < numberOfTrainTracks)
                {
                    int rowIndex = Array.IndexOf(trainTracksRows, row, start);
                    var trainTrack = trainTracks[rowIndex];
                    trainTracksOnSameRow.Add(trainTrack);

                    start = rowIndex + 1;
                    index++;
                }

                sum += SumCellsTakenByTrainTracksForSameRow(trainTracksOnSameRow);                
            }

            return sum;
        }

        /*
         * train tracks on same row
         * - merge intervals - train track stands for one interval
         * - sort train tracks by start column
         * - the array is based on start index 1 not 0
         * Add all cells taken by train tracks on the same row. 
         */
        private static long SumCellsTakenByTrainTracksForSameRow(IList<Tuple<int, int>> trainTrackOnSameRow)
        {
            var trainTracks = trainTrackOnSameRow.ToArray();
            IComparer<Tuple<int, int>> myComparer = new MyComparer();
            Array.Sort(trainTracks, myComparer);             

            var previous = trainTracks[0];
            long cellsTakensByTrainTracks = 0;
            for (int i = 1; i < trainTracks.Length; i++)
            {
                var current = trainTracks[i];

                // no overlap 
                if (previous.Item2 < current.Item1)
                {
                    cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;
                    previous = current;
                }

                // reset the previous 
                int start = previous.Item1;
                int end   = Math.Max(previous.Item2, current.Item2);

                previous = new Tuple<int, int>(start, end);
            }

            // edge case: Last one
            cellsTakensByTrainTracks += previous.Item2 - previous.Item1 + 1;

            return cellsTakensByTrainTracks;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ The solution of the algorithm is also available on hackerrank, the link: hackerrank.com/contests/world-codesprint-7/challenges/…. I did not write any analysis in my algorithm. Based on editorial notes, time complexity is O(k*k), and it is the algorithm of sorting, greedy and line sweep. \$\endgroup\$ – Jianmin Chen Mar 4 '17 at 19:40
1
\$\begingroup\$

Easier way to group tracks in the same row

Your code works correctly, but it is quite complex because of the way you gather all of the same tracks in the same row into an array. Your method is to:

  1. Create an array of the distinct row numbers.
  2. Sort the array of distinct row numbers.
  3. For each distinct row, count the number of tracks on that row.
  4. For each distinct row, gather the tracks that are on that row into an array.
  5. For each distinct row, process the array of tracks on that row in a separate function.

Rather than do all of the above, you could just treat each track as a tuple of 3 integers: row, start column, and end column. Then you could sort the list of tuples by row followed by start column (i.e. the default sort order for a tuple). This leaves you with a list of tracks where all the tracks on the same row are adjacent to each other.

From there it is a simple matter to do the same thing that you did for each row.

Rewrite

Here is a rewrite of your program using the tuple sorting mentioned above. I removed the test cases and long comments, for brevity:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace GridlandMetro
{
    /*
     * problem statement:
     * https://www.hackerrank.com/contests/world-codesprint-7/challenges/gridland-metro
     */
    class Program
    {
        static void Main(string[] args)
        {
            ProcessInput();
        }

        public static void ProcessInput()
        {
            string[] summaryRow = Console.ReadLine().Split(' ');
            int rowNumber = Convert.ToInt32(summaryRow[0]);
            int columnNumber = Convert.ToInt32(summaryRow[1]);
            int k = Convert.ToInt32(summaryRow[2]);

            var tracks = new List<Tuple<int, int, int>>();

            for (int i = 0; i < k; i++)
            {
                var rowData = Console.ReadLine().Split(' ');

                int row      = Convert.ToInt32(rowData[0]);
                int colStart = Convert.ToInt32(rowData[1]);
                int colEnd   = Convert.ToInt32(rowData[2]);

                tracks.Add(new Tuple<int, int, int>(row, colStart, colEnd));
            }
            tracks.Sort();

            long sum = (long) rowNumber * columnNumber;

            Console.WriteLine(sum -
                    CalculateNumberOfCellsTakenByTrainTracks(tracks));
        }

        public static long CalculateNumberOfCellsTakenByTrainTracks(
            IList<Tuple<int, int, int>> tracks
            )
        {
            // Set currentColEnd to -1 so that this track's length is 0.
            int  currentRow        = -1;
            int  currentColStart   = 0;
            int  currentColEnd     = -1;
            long cellsTakenByTrack = 0;

            foreach (var track in tracks)
            {
                int row      = track.Item1;
                int colStart = track.Item2;
                int colEnd   = track.Item3;

                if (row != currentRow || colStart > currentColEnd)
                {
                    // No overlap with current track.
                    // First add length of current track to total.
                    cellsTakenByTrack += (currentColEnd - currentColStart + 1);
                    // Now set current track to this track.
                    currentRow      = row;
                    currentColStart = colStart;
                    currentColEnd   = colEnd;
                }
                else if (colEnd > currentColEnd)
                {
                    // Extend current track.
                    currentColEnd = colEnd;
                }
            }

            cellsTakenByTrack += (currentColEnd - currentColStart + 1);
            return cellsTakenByTrack;
        }
    }
}
\$\endgroup\$
  • \$\begingroup\$ I will have to further investigate your idea. I will run the code against hackerrank and see if there is not any issue related to timeout. \$\endgroup\$ – Jianmin Chen Mar 8 '17 at 5:16
  • \$\begingroup\$ Your code works perfect on hackerrank. It seems like tracks variable defined by "var tracks = new List<Tuple<int,int,int>>();" can be sorted once, and row will be sorted and then same row, multiple tracks will be sorted by column start. Or it does not matter for your code same row tracks should be sorted by start column? \$\endgroup\$ – Jianmin Chen Mar 8 '17 at 5:54
  • 1
    \$\begingroup\$ @JianminChen When a tuple is sorted, by default it sorts on the first element, then the next one, then the next one etc. So in this case, it sorts by ascending order of row, then by ascending order of column start, then by ascending order of column end. The solution requires that the list be sorted by row then column start. The ordering of column end doesn't matter. That is why I put the row in Item1 and the column start in Item2. \$\endgroup\$ – JS1 Mar 8 '17 at 6:24
  • \$\begingroup\$ do you by any chance know where to find IList.Sort Tuple<int,int,int> source code implemented in C#? I tried to google and found something to read, help myself by doing a small study on this feature. \$\endgroup\$ – Jianmin Chen Mar 8 '17 at 6:57
  • 1
    \$\begingroup\$ @JianminChen I don't know where the source code is located, but the comparer function would be something like: { int result = x.Item1.CompareTo(y.Item1); if (result != 0) { return result }; result = x.Item2.CompareTo(y.Item2); if (result != 0) { return result }; return x.Item3.CompareTo(y.Item3); }. Of course you can reformat that code properly. As you can see, the sort is by Item1 primarily. If the Item1 values are equal, then it moves on to Item2. If Item2 is also equal, then it sorts by Item3. \$\endgroup\$ – JS1 Mar 8 '17 at 18:06
1
\$\begingroup\$

I don't understand all the code but I can help you with an idea to solve the problem

-If there are not train tracks then the solution will be n*m

-If there are train tracks we need to subtract this to n*m. How we subtract this?

First we save the train tracks in array, we will call this array trainTracks. Each of the cells consist of three values like in the input (row, start_column, end_column). Sort this array by row

Now we will solve each row. Take all the train tracks of a row (this is easy because you know that the train tracks are sorted by row) and take the start and end column in array. Something like this

//suppose we are in the row r1
while trainTracks[i]->row == r1
    Points.add(trainTracks[i]->start_column, 1)   //We will refer to this elements Points[i]->first and Points[i]->second
    Points.add(trainTracks[i]->end_column+1, -1)
    i = i + 1

We will see next why construct in that way the array

Now, we sort this array by the first element and if there are tie we take first the greater of the second element.

Create a new array of the same length that Points. In this array keep the cumulative sum of the second elements of Points

That is

//Points it´s already sorted
//cum is the array of the cumulative sum

s = Points.length()
cum[0] = Points[0]->second    

j = 1
while j < s
    cum[j] = Points[j]->second + cum[j-1]
    j = j + 1

Then, we look for the zeros in the array. That because when we put a 1 in the array Points it's because a new train track start and when we put -1 is because the train track finish one position before, but also are using this cell. So, when compute the cumulative sum and find a zero it's because finish a range of train tracks.

Now compute the ranges where are not zeros

s = Points.length()
last = Points[0]->first   //The first cell of Points is always the beginning of a train track

j = 1
while j < s 
    if cum[j] == 0   
        solution -= (Points[j]->first - last)
        if j + 1 < s
            last = Points[j+1]->first        //The beginning of a new range
    j = j + 1

Doing it for each row that appear in the input you can solve it.

I expect it was helpful!

\$\endgroup\$
  • \$\begingroup\$ welcome to the code review, so happy to read your answer. \$\endgroup\$ – Jianmin Chen Mar 4 '17 at 19:35
  • \$\begingroup\$ Thank you! If any doubt about the answer you can tell me \$\endgroup\$ – EmmanuelAC Mar 4 '17 at 19:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.