Scaler Topics Fortnightly Contest - 3 Editorial
FREE
This article is part of the Scaler Topics Fortnightly Contest - 3.
Alice and Ambulance
An ambulance driven by Alice have to reach hospital as early as possible to save the patient with health A, but there are N speed breakers, If he go fast on the speedbreaker i where 1<=i<= N the patients health will be reduced by B[i] but it will decrease the time of arrival to hospital by C[i] .
If health A <= 0 then the patient will die.Alice believes that if he reached the hospital with patient health A >= 1 then his doctors will save the patient. Help Alice to find the maximum time he can save.
Problem Constraints
Input Format
- The first argument is the integer A.
- The second argument is the integer array B.
- The second argument is the integer array C.
Output Format
- Return an integer denoting the maximum time he can save.
Build an AI-First Career, Master the Complete Skillset
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
AI Forward Deployed Engineer Program
Full-stack engineering, production AI and client-facing consulting
+1000 moreExample
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Alice will only slowdown for the second speedbreaker and will save a total of 71 units of time.
Explanation 2: In this situation Alice will not slowdown for 2nd and 5th speedbreaker and will save a total of 26 units of time.
Hint
- Try to find the overlapping problems .
Complete Solution
Perfect Appetite
You love burgers a lot, so you visit a shop which sells A different types of burges. But there exist some problems as well. Each burger has a healthiness, unhealthiness and tastiness value associated with it. You are given arrays B, C and D representing the healthiness, unhealthiness and tastiness of ith burger. You wants to eat E different types of burgers such that the sum of ratios of healthiness and unhealthiness is maximum. Return the maximum sum of tastiness which you can achieve.
Problem Constraints
Input Format
- First argument A is an integer.
- Second argument B is an array of integers.
- Third argument C is an array of integers.
- Fourth argument D is an array of integers.
- Fifth argument E is an integer.
Output Format
- Return a single value, representing the maximum sum of tastiness.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: Consider 1-based indexing We will choose burgers at index 5, 6, 9 and 10. There sum of ratios is = 6 + 5 + 1 + 8/7 = 13.142857 Total tastiness = 1 + 9 + 8 + 5 = 23 We can prove that this is the optimal choice of burgers.
Explanation 2: Consider 1-based indexing We will choose burgers at index 8 and 3. There sum of ratios is = 10/4 + 9/2 = 7 Total tastiness = 3 + 10 = 13 We can prove that this is the optimal choice of burgers.
Hint
- To get maximum sum of ratios, it would be best to get top E burgers whose ratios are maximum.
- Think about sorting.
How Scaler Transformed Careers in Different Fields
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ moreComplete Solution
Collect Maximum Candies
You are a candy lover and visited a shop to buy candies. The shopkeeper seeing your excitement for candies, asked you to play the following game: You are given two A x B matrices named as C and D. For each matrix rows are numbered from 1 to A (from top to bottom) and columns are numbered from 1 to B (from left to right). You are currently at cell (1, 1) (intersection of 1th row and 1st column) in matrix C.
You can move in the matrix according to the following rules: Let your current cell be (x, y). You can go to cell (x + 1, y) or (x, y + 1) in the same matrix. Let your current cell be (x, y). You can use teleportation and go to cell (x + 1, y) or (x, y + 1) in the other matrix. (i.e., if you are in matrix C, you can go to matrix D, or if you are in matrix D you can go to matrix C). Each cell of each matrix has some candies in it. What is the maximum number of candies you can collect?
Problem Constraints
Input Format
- First argument A is the number of rows in the matrix.
- Second argument B is the number of columns in the matrix.
- Third argument C is the first matrix.
- Fourth argument D is the second matrix.
Output Format
- Return a single value, the maximum number of candies which can be collected.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation Explanation 1: We will be using 1-based indexing for simulation. The visited cells in the corresponding order would be: (1, 1) of C -> (1, 2) of D -> (2, 2) of C -> (3, 2) of C -> (3, 3) of D. Candies collected would be: 0 + 5 + 4 + 5 + 5 = 19. We can prove that this is the maximum number of candies which can be collected.
Explanation 2: We will be using 1-based indexing for simulation. The visited cells in the corresponding order would be: (1, 1) of C -> (1, 2) of D -> (1, 3) of C -> (2, 3) of D. Candies collected would be: 1 + 4 + 4 + 4 = 13. We can prove that this is the maximum number of candies which can be collected.
Turn Learning into Career Growth
Hint
- We can do simple backtracking.
- It would have ovelapping subproblems, can we store them so that we won't calculate the same thing again and again?
Complete Solution
Catch and Throw
There are N friends playing frisbee. But, these guys are not playing any ordinary game of frisbee, they are controlling their robots where the robots are the actual throwers and catchers. Each robot has a frequency associated with it. The robots can only throw to the right. When a robot throws the frisbee, the first robot to the right, which resonates with the thrower's frequency, catches it. The frequencies of the robots are given by an integer array A. Here, two robots resonate if the GCD of their frequencies is greater than 1. Here, GCD denotes the greatest common divisor of two numbers.
Also, there are M queries given in the form of 2D array B. In each query, there are two integers X and Y. Y throws have to be made, where the first throw starts from the Xth robot. For each query, return the last robot that will catch the frisbee after Y throws have been made. If there is no catcher to receive the frisbee and some positive number of throws are remaining, return the robot's current index and don't make any throws.
Problem Constraints
Input Format
- The first argument is an integer array A, denoting the frequencies of the robots.
- The second argument is an 2-D integer array B, with M rows, where each row contains two integers X and Y, the starting index of the robot and the number of throws to be made respectively.
Output Format
- Return an integer array denoting the answers for each query in the array B.
Example
Example Input Input 1:
Input 2:
Example Output Output 1:
Output 2:
Example Explanation
Explanation 1:
The given array is [3, 4, 6, 8, 11, 12].
Let's find out the answer for each query.
1: (1, 3) => Here, the frisbee moves as follows 1 -> 3 -> 4 -> 6. We can see the after three throws, the robot at index 6 has the frisbee.
2: (2, 2) = > Similarly, the movement is : 2 -> 3 - > 4. So the answer for this query is 4.
3: (5, 1) = > Here, the robot at index five cannot throw the frisbee ahead as no robot can catch it. So the answer to this query is 5.
4: (3, 5) = > Here, the movement is 3 -> 4 -> 6. We can see that we still have 3 throws remaining but there is no robot ahead to catch the frisbee. So, 6 is our answer.
5: (6, 2) = > Here, the robot cannot throw the frisbee ahead as no robot can catch it. So the answer to this query is 6.
Hint
- Can we somehow find the next catcher for every robot?
- How can we traverse the path for a frisbee faster than linear time?
