Hackerrank: Kindergarten Adventures

Question

Problem statement

Description:

Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day!

The students are sitting around a round table, and they are numbered from \$1\$ to \$n\$ in the clockwise direction. This means that the students are numbered \$1,2,3,...,n-1,n\$, and students \$1\$ and \$n\$ are sitting next to each other.

After letting the students draw for a certain period of time, Meera starts collecting their work to ensure she has time to review all the drawings before the end of the day. However, some of her students aren't finished drawing! Each student \$i\$ needs \$t_i\$ extra minutes to complete their drawing.

Meera collects the drawings sequentially in the clockwise direction, starting with student ID \$x\$, and it takes her exactly \$1\$ minute to review each drawing. This means that student \$x\$ gets \$0\$ extra minutes to complete their drawing, student \$x+1\$ gets \$1\$ extra minute, student \$x+2\$ gets \$2\$ extra minutes, and so on. Note that Meera will still spend \$1\$ minute for each student even if the drawing isn't ready.

Given the values of \$t_1,t_2,...,t_n\$, help Meera choose the best possible \$x\$ to start collecting drawings from, such that the number of students able to complete their drawings is maximal. Then print \$x\$ on a new line. If there are multiple such IDs, select the smallest one.

Input Format

The first line contains a single positive integer, n, denoting the number of students in the class. The second line contains n space-separated integers describing the respective amounts of time that each student needs to finish their drawings (i.e., \$t_1,t_2,...,t_n\$).

Constraints

• \$1 \le n \le 10^5\$

• \$0 \le t_i \le n\$

Subtasks

\$1 \le n \le 10^4\$ for \$30\%\$ of the maximum score.

Output Format

Print an integer denoting the ID number, \$x\$, where Meera should start collecting the drawings such that a maximal number of students can complete their drawings. If there are multiple such IDs, select the smallest one.

Sample Input

3
1 0 0

Sample Output

2

Explanation

Meera's class has \$n = 3\$ students:

1. If \$x = 1\$, then only two students will finish.
   The first student needs \$t_1 = 1\$ extra minute to complete their drawing. If Meera starts collecting here, this student will never finish their drawing. Students \$2\$ and \$3\$'s drawings are already finished, so their drawings are ready when she collects them in the second and third minutes.

2. If \$x = 2\$, then all three students will finish.
   The second student needs \$t_2 = 0\$ extra minutes, so the drawing is ready for Meera to collect. The next (third) student's drawing is also ready one minute later, as \$t_3 = 0\$. Meera then proceeds to the next (first) student, who needed \$t_1 = 1\$ extra minute. Because she already spent two minutes collecting the work of the other two students, the first student's drawing has already been completed for \$2 - 1 = 1\$ minute.

3. If \$x = 3\$, then all three students will finish.
   The third student needs \$t_3 = 0\$ extra minutes, so the drawing is ready for Meera to collect. The next (first) student's drawing is also ready one minute later, as \$t_1 = 1\$ and \$1\$ minute passed while Meera collected the third student's drawing. She then proceeds to the next (second) student, whose drawing was already completed (as \$t_2 = 0\$)

Starting with student IDs \$x = 2\$ or \$x = 3\$ will result in a maximum number of completed drawings (i.e., \$3\$). Because there are two equally valid answers, we choose the smaller ID, \$2\$, and print it as our answer.

Introduction of Algorithm:

I am learning the segment tree and also binary index tree this weekend, and I studied binary index tree from the article on hackerearth related to binary index tree and segment tree from the blog algorithm: Ahoy, Pirates, so I decided to take some time to practice the algorithm, spent a few hours to work on the algorithm "Kindergarten Adventures" on Hackerrank university codesprint again.

Also, I like to present the idea from Hackerrank editorial notes first, and then share my C# practice code to ask for code review.

Editorial notes:

If a student asks for a N minute extra time, then he can never be happy. We can ignore him.

If a student with id a asks for a t minute extra time, then if we start from id \$a-t\$ (if \$a-t\$ is negative, wrap it around), then he will be happy. Not just that, if we start from any id lower than that he will be happy. So we get a range of students ( the range may wrap around ), from which if we select an id, we are sure to make a happy.

For each student, we get a range. Now, we have to select an id which is covered by maximum number of range. This can be done using Binary Indexed Tree or Segment Tree.

We need to deal with ranges that wrap around. The students are sitting in a circular fashion. Imagine they are sitting linearly like an array from 1 to N. Now just append \$1\$ to \$N\$ to the array, so that we have two segments that go from \$1\$ to \$N\$. Now any \$N\$ consecutive elements of the array is a valid ordering of the students.

Now work with the second segment of the array. For each position \$N+1 \le i \le N+N\$, if student \$i-N\$ request \$t\$ time, then we need to add \$1\$ to range \$i-N+1\$ to \$i-t+1\$.

Next, to find the value of \$X\$, we iterate over \$1\$ to \$N\$ using \$i\$ and select the index for which sum of values at position \$i\$ and \$i+N\$ is maximum.

My Implementation of segment tree

I documented the step by step how a segment tree is built using the array starting from 1, and added some notation for each node in the segment tree using array index ID, range of the node is represented and also the value of node in the comment, went through the sample test case 1 0 0. Make sure that every step is making sense and then assume that the learning of segment tree can be accomplished by this simple test case.

Most important is to implement the API of Modify and Query using time complexity of O(logN), whereas Modify function N is the second argument count which is the range of interval, Query function N is input argument index value. Otherwise timeout will be an issue in the problem solving.

Test case study

I did spend time to learn the algorithm about time complexity. For any N smaller than 100000, I certainly can choose N as 20000 to analyze. Suppose that there are 20000 students in the circle, suppose that the first student only need to 0 minute to finish drawing, so that the first student can complete the drawing for any student chosen by the teacher to start.

Related to SegmentTree class Modify API, it has to increase those 20000 nodes by value 1. If the time complexity is linear O(N), and if all 20000 students has O(N) operation, then there are operations of N² = 20000 x 20000, almost 400 million operations, but the time limit is only 3 seconds, so I am pretty sure that the function will cause timeout. So that we have to lower down to logN intervals to cover the range of [1, 20000] using segment tree.

To make it simple, we assume that the range's width is 1024 instead of 20000, and see how many steps we need to mark in SegmentTree class variable tree[]. We will show only 10 increment operation.

Let us get our hands dirty on the calculation of tree.Modify(0,1024,1). We read the code pasted here first.

public void Modify(int start, int count, int value)
{
    int size = tree.Length / 2;

    int left = start + size + 1;
    int right = start + count + size + 1;

    for (; left < right; left >>= 1, right >>= 1)
    {
        if (left % 2 == 1)
        {
            tree[left] += value;
            left++;
        }

        if (right % 2 == 1)
        {
            right--;
            tree[right] += value;
        }
    }
}

First row of table, left = 20001, right = 21024, since Modify API is called and function arguments: start = 0, count = 1024, value = 1, inside Modify API the variable left is calculated as 20001 and right is calculated as 21024.

The two variables of left and right are iterated from beginning to end 10 times, each iteration two variables's values are recorded in the table. And the highlighted color yellow of left column marks that the index of tree will be incremented by value 1, righ column marks that index - 1 of tree will be incremented by value 1.

and more detail is in the following image:

To summarize, to increment 1024 nodes value by 1, only need to increment 10 nodes represented in tree variable, the index array is [40,79,157,313,656,1251,2501,5001,10001,20001].

The design concern

The API Modify and Query works together very well with SegmentTree, but however each node in the tree does not explicitly include the range it covers, I need to look into this issue and see if there is a quick fix.

I may not fully understand segment tree or binary index tree and have some misunderstanding of segment tree, I like to ask code review. The C# code passes all of hackerrank test cases.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution
{
    static void Main(String[] args)
    {
        ProcessInput(); 
        //RunTestcase();
    }
    /// <summary>
    /// sample test case documented in the problem statement
    /// private array tree is declared in int[], size of 7, start index is 1 not from 0. 
    /// 
    /// 3
    /// 1 0 0
    /// Segment tree is built like the following:
    ///         0
    ///      /    \
    ///     2      0
    ///    / \    /
    ///   0   1  3
    /// Explanation of the segment tree
    /// 
    /// 1. 1 0 0, first student needs 1 minutes, so the range of [5,6] will be selected 
    /// since students in the range can completet the drawing, ID = 5 and ID = 6 two students
    /// can complete the drawing. 
    /// 
    /// Modify(1,2,1) will modify the segment tree:
    /// Work on the range from 5 to 7, 
    /// 5 in binary form 101
    /// 7 in binary form 111 
    /// the tree will be updated twice, tree[5] += 1, tree[6] += 1     
    ///        0
    ///      /    \
    ///     0      0
    ///    / \    /
    ///   0   1  1
    /// in other words, starting from the first student, the range from [5,6] will be selected 
    /// since students in the range can completet the drawing, ID = 5 and ID = 6 two students
    /// can complete the drawing. 
    ///              [4,6]
    ///              1,0,   
    ///              
    ///             short hand of  
    ///             
    ///             [4,6] range of ID from 4 to 6. 
    ///            1 - ID, 0 - count
    ///            
    ///  ID is from 1 to 6, count is added for the ID range. 
    ///            
    ///                 [4,6]
    ///                 1,0,
    ///          /                 \
    ///        [4,5]              [6,6]
    ///        2,0                3,0   
    ///    /          \          /
    ///   [4,4]      [5,5]      [6,6]
    ///   4,0        5,1        6,1
    /// 
    /// 
    /// 2. second student does not need extra minutes, so there are two ranges, 
    /// two of calls of Modify function, Modify(2,1,1) and Modify(0,2,1)
    /// 
    /// First one, it is to call function Modify (2,1,1)
    /// Modify (2,1,1) will modify the segment tree
    /// Work on the range from 6 to 7, 
    /// 6 in binary form 110
    /// 7 in binary form 111
    /// the tree will be updated once, tree[6] += 1  
    /// 
    ///        0
    ///      /    \
    ///     0      0
    ///    / \    /
    ///   0   1  2   
    ///   
    /// Second one, it is to call function Modify (0, 2, 1)
    /// Work on the range from 4 to 5, 
    /// 4 in binary form 100
    /// 5 in binary form 101
    /// the tree will be updated once, tree[2] +=1
    /// 
    ///        0
    ///      /    \
    ///     1      0
    ///    / \    /
    ///   0   1  2   
    /// The tricky part is that tree[4] and tree[5] can both be incremented 
    /// by 1, but tree[2] is incremented by 1 instead since tree[2] covers
    /// range of ID from 4 to 5. 
    ///
    /// 3. Third student does not need extra minutes, so there is one range,
    ///    call Modify (0, 3, 1)
    ///    Modify (0, 3, 1) will modify the segment tree
    ///    Work on the range from 4 to 7
    ///    4 in binary form 100
    ///    7 in binary from 111
    ///    tree[2] += 1; 
    ///    tree[6] += 1; 
    ///    
    ///        0
    ///      /    \
    ///     2      0
    ///    / \    /
    ///   0   1  3   
    ///  
    /// Next step, query the segment tree by iterating every student. 
    /// tree is an array of int[]{0,2,0,1,1,3]
    /// 
    /// starting from the first student, how many students can finish?    
    /// tree[4] + tree[2] + tree[0] = 2 + 0 + 0 = 2
    /// 
    /// starting from the second student, how many students can finish?
    /// tree[5] + tree[2] + tree[0] = 1 + 2 + 0 = 3
    /// 
    /// starting from the third student, how many stedents can finish?
    /// tree[6] + tree[3] + tree[0] = 3 + 0 + 0 = 3
    /// 
    /// So, the answer is the ID = 2.
    /// </summary>
    public static void RunTestcase()
    {
        int n = 3;
        var minutes = new int[] { 1, 0, 0 };

        var tree = new SegmentTree(n);

        for (int i = 0; i < n; i++)
        {
            int extraMinutes = minutes[i];
            if (extraMinutes >= minutes.Length) continue;

            // calculate the range of current student can complete the drawing
            // depending on their need - extra minutes
            int start = (i + 1) % minutes.Length;
            int end = (i + minutes.Length - extraMinutes) % minutes.Length;
            if (start <= end)
            {
                tree.Modify(start, end - start + 1, 1);
            }
            else
            {
                tree.Modify(start, minutes.Length - start, 1);
                tree.Modify(0, end + 1, 1);
            }
        }

        // Query segment tree 
        int bestIndex = 1;
        int maximumStudents = 0;
        for (int i = 1; i <= minutes.Length; i++)
        {
            var numberCanComplete = tree.Query(i);

            if (numberCanComplete > maximumStudents)
            {
                maximumStudents = numberCanComplete;
                bestIndex = i;
            }
        }

        Console.WriteLine(bestIndex);
    }

    public static void ProcessInput()
    {
        int n = int.Parse(Console.ReadLine());
        var minutes = Console.ReadLine().Split().Select(int.Parse).ToArray();

        var tree = new SegmentTree(n);
        for (int i = 0; i < n; i++)
        {
            int extraMinutes = minutes[i];
            if (extraMinutes >= minutes.Length) continue;

            int start = (i + 1) % minutes.Length;
            int end = (i + minutes.Length - extraMinutes) % minutes.Length;

            if (start <= end)
            {
                tree.Modify(start, end - start + 1, 1);
            }
            else
            {
                tree.Modify(start, minutes.Length - start, 1);
                tree.Modify(0, end + 1, 1);
            }
        }

        int bestIndex = 1;
        int maximumStudents = 0;
        for (int i = 1; i <= minutes.Length; i++)
        {
            var numberCanComplete = tree.Query(i);

            if (numberCanComplete > maximumStudents)
            {
                maximumStudents = numberCanComplete;
                bestIndex = i;
            }
        }

        Console.WriteLine(bestIndex);
    }

    /// <summary>
    /// 
    /// </summary>
    public class SegmentTree
    {
        private readonly int[] tree;

        public SegmentTree(int size)
        {
            tree = new int[size * 2 + 1];
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="start"></param>
        /// <param name="count"></param>
        /// <param name="value"></param>
        public void Modify(int start, int count, int value)
        {
            int size = tree.Length / 2;

            int left = start + size + 1;
            int right = start + count + size + 1;

            for (; left < right; left >>= 1, right >>= 1)
            {
                if (left % 2 == 1)
                {
                    tree[left] += value;
                    left++;
                }

                if (right % 2 == 1)
                {
                    right--;
                    tree[right] += value;
                }
            }
        }

        /// <summary>
        /// 
        /// </summary>
        /// <param name="index"></param>
        /// <returns></returns>
        public int Query(int index)
        {
            int value = 0;
            int i = index + tree.Length / 2;

            for (; i > 0; i >>= 1)
            {
                value += tree[i];
            }

            return value;
        }
    }
}

Answer 1

I'm not going to talk about your algorithm and whatnot, instead let's discuss abstraction and SRP for a moment. Yours isn't bad, but it could use a few tweaks.

First:

public static void ProcessInput()
{
    int n = int.Parse(Console.ReadLine());
    var minutes = Console.ReadLine().Split().Select(int.Parse).ToArray();

We're entirely reliant upon the Console for input handling, which may (is) not a good thing. Instead, let's develop that method to take two strings: one is the n, and the next is the line.

public static void ProcessInput(string nLine, string minutesLine)

And our Console.ReadLine calls would happen outside this class. The class doesn't care where the input came from, it cares what input it got.

Similarly, the Console.WriteLine(bestIndex); should not appear, instead you should return bestIndex and let the caller decide what to do with it. This way you take the responsibility of acquiring input and delivering output away from the ProcessInput method, which can now be named to RunAlgorithm et. al.

Next we are still in that same method, because it still does too many things. Let's break it down further:

• Read input
• Parse input
• Build and fill SegmentTree
• Query for best index from SegmentTree
• Print best index

So we still have three major things it does that can be abstracted, which we should do. It may not seem like much, but failing to extract this processing properly can create unmaintainable code. Each method should have one responsibility, if it has responsibilities > 1 then it should have each responsibility split to a new method, and then make calls and transfer data between those methods. This way, when we debug our code and find something that's wrong, we have a method to narrow it down to. (Especially once a released version is out, and someone says 'I got an exception that mentions the ProcessInput method', well that's bad right now because we have no way of telling where in the method the exception happened.)