SPIJUMP - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Shivam
Tester: Mayur Ray
Editorialist: Mayur Ray

DIFFICULTY:

SIMPLE

PREREQUISITES:

Basic Maths

PROBLEM:

Mama Spider & Baby Spider are standing along a track, N units distance apart. Mama Spider can jump a distance of K units and Baby Spider can jump 1 unit each time. For each jump, both spiders need 1 second. If both of them start moving towards each other, then what will be the minimum time needed by them to meet each other, provided Mama Spider cannot jump over Baby Spider?
Note : It’s not necessary that both of them have to jump simultaneously…

QUICK EXPLANATION:

Since distance is N, at most Mama Spider can jump N/K times, & it’s also possible that she doesn’t jump at all. Now we can find the minimum time among all the cases from 0 to N/K using brute force.

EXPLANATION:

At first, whenever we see the problem, it feels like we can do it easily using some mathematical formula. But if it’s not done properly, then it will fail at many edge cases.

Also, if we look at the constraints, we see that they are quite small.

So we can simply do brute force here.

The distance between Mama Spider & Baby Spider is N, & Mama Spider can jump K units in each jump. So, at most, she can jump N/K (integer division) times. Also, it’s possible that she doesn’t jump at all, & the whole distance is covered by Baby Spider. She can also cover any distance in between. We need to find the best case among them, i.e., the case with the minimum time.

For this, we can run a loop from 0 to N/K, & consider that Mama Spider jumped i (0 \leq i \leq N/K) times. Thus, she covers i*K units distance in i seconds. The remaining distance is (N - i*K) units, which is covered by Baby Spider in (N - i*K) seconds. Also, as we need to find the minimum time, so it’s always better if both of them move together for as long as possible.
Hence, the time required in each case will be max (i, N - i*K). And we need to find the minimum one among all i.

ALTERNATE EXPLANATION (using Maths):

If both the Spiders move together, then they’ll cover K+1 units distance each second, & let’s consider M = K + 1. Now, both of them can move together for (N/M) (integer division) seconds, let’s denote it by time. Here, two cases arises :

  • If (N\%M) == 0, that means both of them will move together for time seconds, & meet each other. This is the best possible case & so, answer = time.
  • If (N\%M) \neq 0, then someone has to jump more & the other one less. Here again, two cases arises :
    • If it’s possible for Mama Spider to move for (time + 1) seconds, i.e., if K*(time + 1) \leq N, then the remaining distance can be covered by Baby Spider (& it’s guaranteed than he can cover it in lesser time than her). So, answer = time + 1. This is the second best possible case.
    • Else, they both move for time seconds, covering (time*M) units distance. And the remaining distance is covered by Baby Spider in extra (N - time*M) seconds. So, answer = time + (N - time*M). This is the worst case scenario.
PSEUDO CODE :

M = K + 1;
time = (N / M);
if (N % M == 0)
    ans = time;
else if (K * (time + 1) <= N)
    ans = time + 1; 
else
    ans = (time + N - time * M);

TIME COMPLEXITY :

Brute-force : O(N / K)
Maths : O(1)

SOLUTIONS:

Setter's Solution 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        long int i, m, n, k, ans = 0;
        cin >> n >> k;
        m = n;
        i = 0;

        while (i != m)
        {
            if (i + k > n)
            {
                m--;
                ans++;
            }
            else if (i + k >= m)
            {
                ans++;
                i = m;
            }
            else
            {
                ans++;
                i = i + k;
                m--;
            }
        }
        cout << ans << endl;
    }
}
Tester's & Editorialist's Solution 
#include <iostream>
#include <algorithm>
#include <climits>
#define ll long long int
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T;
    cin >> T;
    while (T--)
    {
        ll n, k, res = LONG_MAX;
        cin >> n >> k;
        // Mama Spider can make n / k jumps at most in the whole track.
        ll mx = n / k;
        for (ll i = 0; i <= mx; i++)
        {
            // Mama Spider makes i jumps in i seconds & covers i*k distance,
            // while Baby Spider covers the remaining distance (n - i * k) in (n - i * k) seconds.
            // The time taken will be the maximum of these two. 
            res = min(res, max(i, n - i * k));
        }
        cout << res << '\n';
    }
    return 0;
}
3 Likes