Editorial: Frogs and Lily Pads

The problem requires finding the last lily pad a frog visits and the number of jumps before exiting. A brute-force simulation (O(N²)) would be inefficient, so we use a reverse DP approach (O(N)).

By iterating backward (right to left), we precompute and store results:

• If a jump from i exceeds N, the last visited pad is i, and jumps = 1.
• Otherwise, we use precomputed values from next = i + a[i], avoiding redundant calculations.

Time Complexity : O(N)

Code :

#include <bits/stdc++.h>
using namespace std;

void solve()
{
		int n, m;
		cin >> n;
		vector<int> v(n);
		for (int i = 0; i < n; i++)
		{
				cin >> v[i];
		}
		vector<int>jump(n, 0), end_pos(n, 0), to(n, 0);
		for (int i = n - 1; i >= 0; i--) {
				int next = i + v[i];
				if(next >= n)
				{
						jump[i] = 1;
						end_pos[i] = i;
						to[i] = i + v[i];
				}
				else{
						jump[i] = 1 + jump[next];
						to[i] = to[next];
						end_pos[i] = end_pos[next];
				}
		}

		for(int i = 0; i < n; i++)
		{
				cout << end_pos[i] + 1 << " " << jump[i] << endl;
		}
}

int32_t main()
{
		ios::sync_with_stdio(false);cin.tie(0),cin.tie(0);
		int t = 1;
		// cin >> t;
		for (int tc = 1; tc <= t; ++tc)
		{
				// cout << "Case " << tc << ": ";
				solve();
		}
}