PROBLEM LINK:
Author: Tharun Chowdary
Tester: Mayur Ray
Editorialist: Tharun Chowdary
DIFFICULTY:
EASY
PREREQUISITES:
Sorting, Math
PROBLEM:
On his way back home, Spider-Man saw N kangaroos standing in a queue. The age of the kangaroo standing at i^{th} position is A_i (in days), & it can jump with a length of L_i.
Spider-Man wants your help to find the minimum number of jumps required by kangaroos so that they can stand in decreasing order w.r.t. their age. Kangaroos can jump only in one direction, i.e., from left to right.
Can you help Spider-Man find the minimum number of jumps?
QUICK EXPLANATION:
We try to re-arrange(sort) kangaroos in descending order of their age and calculate the number of jumps needed by each kangaroo to get to the position it is in after sorting with respect to its initial position.
EXPLANATION:
First, we will sort the given kangaroos in descending order of their ages. This step will help us determine how many jumps are needed to move to its position after sorting from its initial position.
Let’s define each kangaroo with three properties {index, age, length}
where, index is the initial index of the kangaroo,
age is the age of the kangaroo
and length is the length of jump it can make.
Now, we can loop through the array from the second element and calculate jumps required by kangaroo at the current index to get to the position that’s greater than kangaroo at the previous index. i.e If we are at ith index, minimum distance to be moved by the kangaroo[i] will be (kangaroo[i -1].index - kangaroo[i].index + 1), and hence number of jumps required for this kangaroo will be ceil(distance/kangaroo[i].length)
Pseudocode for the above step:
result = 0;
for (int i = 1; i < n; i++) {
if (kangaroos[i].index > kangaroos[i - 1].index){
continue;
}
difference = kangaroos[i - 1].index - kangaroos[i].index + 1;
jumps_required = ceil(difference / kangaroos[i].length);
kangaroos[i].index += kangaroos[i].length * jumps;
result += jumps;
}
COMPLEXITY:
O(NlogN), since we are sorting the input kangaroos.
SOLUTIONS:
Tester's Solution
#include <iostream>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define ll long long int
using namespace std;
// it will store the original index, age & length of jump of kangaroo
struct kan
{
ll idx, age, len;
};
// used to sort kangaroos in decreasing order of their ages
bool comp(kan &k1, kan &k2)
{
return k1.age > k2.age;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T;
cin >> T;
while (T--)
{
ll n;
cin >> n;
vector<kan> v(n);
for (ll i = 0; i < n; i++)
{
cin >> v[i].age;
v[i].idx = i;
}
for (ll i = 0; i < n; i++)
{
cin >> v[i].len;
}
// sorts kangaroos in decreasing order of their age
sort(v.begin(), v.end(), comp);
// initially result is 0 (we need no jumps)
ll res = 0;
// it stores the last index (position) where any kangaroo is standing. initially there's no kangaroo, so lastIdx = -1
ll lastIdx = -1;
for (ll i = 0; i < n; i++)
{
// if the current kangaroo is standing behind the last one, we just update it
if (v[i].idx > lastIdx)
{
lastIdx = v[i].idx;
}
else
{
// the current kangaroo has to stand behind the last index (position), so we find the minimum required distance that it needs to move
ll req = lastIdx + 1 - v[i].idx;
// required number of jumps is ceil(required distance / length of jump), & the below expression is just one way to find ceil
ll jumps = (req + v[i].len - 1) / v[i].len;
// it is added to result
res += jumps;
// the last index (position) is updated
lastIdx = v[i].idx + jumps * v[i].len;
}
}
cout << res << '\n';
}
return 0;
}
Editorialist's Solution
import java.util.*;
class Solution {
static class Kangaroo {
int index, age, length;
}
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
int tc = sc.nextInt();
while (tc-- > 0) {
int n = sc.nextInt();
Kangaroo[] kangaroos = new Kangaroo[n];
for (int i = 0; i < n; i++) {
kangaroos[i] = new Kangaroo();
kangaroos[i].index = i;
}
for (int i = 0; i < n; i++)
kangaroos[i].age = sc.nextInt();
for (int i = 0; i < n; i++)
kangaroos[i].length = sc.nextInt();
// sort kangaroos in decreasing order of their age
Arrays.sort(kangaroos, (kang1, kang2) -> kang2.age - kang1.age);
long res = 0;
for (int i = 1; i < n; i++) {
/*
* if current kangaroo's position is already greater than previous kangaroo's
* position, we can skip calculating jumps as its the desired order
*/
if (kangaroos[i].index > kangaroos[i - 1].index)
continue;
// distance current kangaroo should be moved to be ahead of its previous one
long difference = kangaroos[i - 1].index - kangaroos[i].index + 1;
long jumps = (difference + kangaroos[i].length - 1) / kangaroos[i].length;
// update current kangaroo's index
kangaroos[i].index += kangaroos[i].length * jumps;
res += jumps;
}
System.out.println(res);
}
sc.close();
}
}