1
\$\begingroup\$

I was trying to attempt below given challenge. I tried multiple ways to solve the problem but none of them were good enough to pass the time limit. Please advise if you have any idea to improve on this.

Problem: You are visiting a building of N floors. On every floor, only one ladder of specified length is present. If the length of the ladder is x units, you can reach y floors above from the current one.

You can leave the ladder in between in order to change the ladder, but you can only start from the starting floor of the ladder.

You are given Q questions. In each question, you will be given a floor number. For each question, you have to tell the least number of ladders required to reach given floor. Initially, you are on the ground floor.

Input Format: The first line contains an integer T, indicating the number of test cases. For each test case: The first line contains an integer N, indicating number of floors in the building. Next line contains N space separated positive integers which denote the length of ladder at each floor (First integer corresponds to ladder length on ground floor, second integer corresponds to ladder length on first floor and so on) . Next line contains an integer Q, indicating number of questions. Following Q lines contain an integer each, denoting the floor number for which answer is to be computed.

Output Format: For each question, print the least number of ladders required required to reach given floor. Answer for each question should come in a new line.

Sample Input:

1
10
2 2 1 1 2 2 3 1 1 1
10
5
4
3
2
1
10
9
8
7
6

Sample Output:

4
3
2
1
1
6
5
5
5
4

Problem Reference

Solution:

class Program
{
    static void Main(string[] args)
    {
        int T = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < T; i++)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            sb.EnsureCapacity(sb.Length + (5 * N));
            int[] numOfStairs = new int[N + 1];
            numOfStairs[0] = 0;
            string[] stairs = Console.ReadLine().Split();
            int[] reaches = new int[N];
            for (int j = 0; j < stairs.Length; j++)
            {
                int length = Convert.ToInt32(stairs[j]);
                reaches[j] = j + length;
            }
            int Q = Convert.ToInt32(Console.ReadLine());

            for (int j = 0; j < Q; j++)
            {
                int target = Convert.ToInt32(Console.ReadLine());
                sb.AppendLine(GetShortestPath(target, reaches.Take(target).ToArray(), numOfStairs).ToString());
            }
        }
        Console.WriteLine(sb.ToString());
    }
    static int GetShortestPath(int target, int[] reaches, int[] numOfStairs)
    {
        if (numOfStairs[target] == 0 && target != 0)
        {
            List<int> connectedFloors = GetPreviousFloorList(target, reaches);
            int[] shortestPaths = new int[connectedFloors.Count];
            for (int i = 0; i < connectedFloors.Count; i++)
            {
                int shortestPath = GetShortestPath(connectedFloors[i], reaches.Take(connectedFloors[i]).ToArray(), numOfStairs);
                shortestPaths[i] = shortestPath;
            }
            int result = shortestPaths.Min() + 1;
            numOfStairs[target] = result;
            return result;
        }
        else
        {
            return numOfStairs[target];
        }
    }
    static List<int> GetPreviousFloorList(int target, int[] reaches)
    {
        List<int> floors = new List<int>(target / 2);
        for (int i = 0; i < target; i++)
        {
            if (reaches[i] >= target)
                floors.Add(i);
        }
        return floors;
    }
}
New contributor
Akshay Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
3
1
\$\begingroup\$

Applied few minor optimisations to the code from the OP's answer. Also fixed naming issues (locals name starts from a lower-cased letter).

class Program
{
    static void Main(string[] args)
    {
        int t = int.Parse(Console.ReadLine());
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < t; i++)
        {
            int n = int.Parse(Console.ReadLine());
            int[] numOfStairs = new int[n + 1];
            int floorsMarked = 0;
            string[] str = Console.ReadLine().Split();
            for (int j = 0; j < str.Length; j++)
            {
                int length = int.Parse(str[j]);
                int reach = j + length > n ? n : j + length;
                while (floorsMarked < reach)
                {
                    floorsMarked++;
                    numOfStairs[floorsMarked] = numOfStairs[j] + 1;
                }
                if (reach == n)
                    break;
            }
            int q = int.Parse(Console.ReadLine());
            for (int j = 0; j < q; j++)
            {
                int target = int.Parse(Console.ReadLine());
                sb.Append(numOfStairs[target]).AppendLine();
            }
        }
        Console.Write(sb);
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the input. I noticed that you changed Convert.Int32 to int.parse which is a tad bit faster but i do not see any other changes that would reduce execution time. Let me know if i am missing anything. I also noticed that you reduced the size of Array "numOfStairs" to n from n+1. I think that would cause a IndexOutOfBound since for the last floor, the index would be n -> size needs to be n+1. \$\endgroup\$ – Akshay Gupta May 4 at 5:04
  • \$\begingroup\$ @AkshayGupta Console.Write(sb); didn't affect the performance? Further performance tweaks require .NET Core, and more details on input steucture sizes. For example, you may use ArrayPool<T> instead of allocating array. Span<T> can be also useful with stack allocations. \$\endgroup\$ – aepot May 4 at 6:01
  • \$\begingroup\$ Thanks for the inputs. i will look into implementing your advice. Also, i did not know that Console.Write(sb); is faster than Console.WriteLine(sb); \$\endgroup\$ – Akshay Gupta 2 days ago
0
\$\begingroup\$

I was finally able to reduce it enough to return result for 1 million inputs in around 10 secs.

class Program
{
    static void Main(string[] args)
    {
        int T = Convert.ToInt32(Console.ReadLine());
        StringBuilder sb = new StringBuilder("");
        for (int i = 0; i < T; i++)
        {
            int N = Convert.ToInt32(Console.ReadLine());
            int[] numOfStairs = new int[N + 1];
            numOfStairs[0] = 0;
            int floorsMarked = 0;
            string[] str = Console.ReadLine().Split();
            for (int j = 0; j < str.Length; j++)
            {
                int length = Convert.ToInt32(str[j]);
                int reach = j + length > N ? N : j + length;
                while (floorsMarked < reach)
                {
                    floorsMarked++;
                    numOfStairs[floorsMarked] = numOfStairs[j] + 1;
                }
                if (reach >= N)
                    break;
            }
            int Q = Convert.ToInt32(Console.ReadLine());
            for (int j = 0; j < Q; j++)
            {
                int target = Convert.ToInt32(Console.ReadLine());
                sb.AppendLine(numOfStairs[target].ToString());
            }
        }
        Console.WriteLine(sb.ToString());
    }
}
New contributor
Akshay Gupta is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

Your Answer

Akshay Gupta is a new contributor. Be nice, and check out our Code of Conduct.

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.