FROGS - Editorial

PROBLEM LINK:

Practice
Div-1 Contest
Div-2 Contest
Div-3 Contest

Author: Alei Reyes
Testers: Felipe Mota and Radoslav Dimitrov
Editorialist: Vichitr Gandas

DIFFICULTY:

Simple

PREREQUISITES:

Sorting, Observations

PROBLEM:

Given N frogs (numbered 1 through N) in a line. For each valid i, the i-th frog is initially at the position i, it has weight W_i, and whenever you hit its back, it jumps a distance L_i to the right, i.e. its position increases by L_i. The weights of the frogs are pairwise distinct. The task is to sort the frogs in the increasing order of weight using the smallest possible number of hits.

EXPLANATION

We want to place the frogs in increasing order of weights. So lets start with the frog with minimum weight. We don’t need to move this frog because moving it to the right will just increase the number of hits.
Now see the frog with second minimum weight. If its current position is already greater than minimum weighted frog then we don’t need to move it because its already in the right of minimum weighted frog. If its position is less or equal to the position of minimum weighted frog then hit this frog until its position becomes greater than minimum weighted frog.
Similarly follow for third minimum weighted frog and so on.

Why this always works?

We want the frogs lined up in sorted order of weights. So the first frog should be the one with minimum weight. Also we are moving the frogs only in right direction. Hence we don’t get any benefit of hitting the frog with smallest weight.
Hitting it would just increase number of hits. As if any frogs with more weight is in left side of it, that frog might have to move more times now. Similarly even if this frog is in left most side, when it moves, it might pass one of more weighted frogs. Even if it doesn’t pass, at least number of hits increased which we want to minimize.
Now we know that we shouldn’t move the minimum weighted frog. What is best strategy for second minimum weighted frog?
If its already in right side of first one, we should not hit it. Why? Because it increase number of hits which we want to minimize. If its in the left then we will hit it minimum number of times such that it just comes in the right of first one.
Similarly we follow for others.

Code Stub
void solve(){
    int n; cin>>n;
    int W[n], L[n];
    for(int i=0; i<n;i++)
    	cin >> W[i];
    for(int i=0;i<n;i++)
    	cin >> L[i];
    int ans = 0;

    // make {weight, position} pairs
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++)
    	v[i] = {W[i], i};

    // sort in increasing order of weight
    sort(v.begin(), v.end());

    // now start with smallest frog
    // position of last frog in order 
    int lastPosition = v[0].second; 

    // keep increasing the position by L[i]
    // until its position becomes greater than lastPosition
    for(int i = 1; i < n; i++){
    	// cur frog position
    	int curPosition = v[i].second;
    	// index of current frog
    	int index = v[i].second;
    	// keep moving this frog until
    	// it crosses last frog
    	while(curPosition <= lastPosition){
    		curPosition += L[index];
    		ans++;
    	}
    	// update lastPosition as cur frog position
    	lastPosition = curPosition;
    }
    
    cout<<ans<<'\n';
}

Time Complexity of the solution is O(NlogN) assuming L_i is very small. Space complexity is O(N).

BONUS PROBLEM
Can you solve it for larger N?.

Hint

Instead of hitting the current frog one by one, just see the position difference between previous frog and current frog and move the current frog (lastPosition - curPosition + L[curIndex])/L[curIndex]) times where lastPosition is the position of previous frog, curPosition is the position of current frog, curIndex is the index of current frog.

Code Stub
void solve(){
    int n; cin>>n;
    int W[n], L[n];
    for(int i=0; i<n;i++)
    	cin >> W[i];
    for(int i=0;i<n;i++)
    	cin >> L[i];
    int ans = 0;

    // make {weight, position} pairs
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++)
    	v[i] = {W[i], i};

    // sort in increasing order of weight
    sort(v.begin(), v.end());

    // now start with smallest frog
    // position of last frog in order 
    int lastPosition = v[0].second; 

    // keep increasing the position by L[i]
    // until its position becomes greater than lastPosition
    for(int i = 1; i < n; i++){
    	// cur frog position
    	int curPosition = v[i].second;
    	// index of current frog
    	int index = v[i].second;
    	// find how many times the frog should move
    	int k = (curPosition <= lastPosition) ? ((lastPosition - curPosition + L[index])/L[index]) : 0;
    	// update ans and lastPosition
    	ans += k;
    	lastPosition = curPosition + k * L[index];

    	// // keep moving this frog until
    	// // it crosses last frog
    	// while(curPosition <= lastPosition){
    	// 	curPosition += L[index];
    	// 	ans++;
    	// }
    	// // update lastPosition as cur frog position
    	// lastPosition = curPosition;
    }
    
    cout<<ans<<'\n';
}

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long int uli;
int rint(char nxt){
  char ch=getchar();
  int v=0;
  int sgn=1;
  if(ch=='-')sgn=-1;  
  else{
    assert('0'<=ch&&ch<='9');
    v=ch-'0';
  }
  while(true){
    ch=getchar();
    if('0'<=ch && ch<='9')v=v*10+ch-'0';
    else{
      assert(ch==nxt);
      break;
    }
  }
  return v*sgn;
}
 
int main(){
//  freopen("example.in", "r", stdin);
//  freopen("example.out", "w", stdout);
  int t = rint('\n');
  assert(1 <= t&&t <= 2e4);
  while(t--){
    int n = rint('\n');
    assert(2 <= n && n <= 4);
    vector<int> w(n), l(n), x(n);
    for(int i = 0; i < n; i++){
      w[i] = rint(i == n-1 ? '\n' : ' ');
      assert(1 <= w[i] && w[i] <= n);
    }
    for(int i = 0; i < n; i++){
      l[i] = rint(i == n-1 ? '\n' : ' ');
      assert(1 <= l[i] && l[i] <= 5);
      x[i]=i;
    }
    int ans = 0;
    for(int W = 1; W<=n; W++){
      int pos = -1;
      for(int j = 0; j < n; j++)
        if(w[j] == W) 
          pos = x[j];
 
      for(int j = 0; j < n; j++){
        while(w[j] > W && x[j] <= pos){
          x[j] += l[j];
          ans++;
        }
      }
    }
    printf("%d\n",ans);
  }
  return 0;
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
template<typename T = int> vector<T> create(size_t n){ return vector<T>(n); }
template<typename T, typename... Args> auto create(size_t n, Args... args){ return vector<decltype(create<T>(args...))>(n, create<T>(args...)); }
long long readInt(long long l,long long r,char endd){
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true){
		char g=getchar();
		if(g=='-'){
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g && g<='9'){
			x*=10;
			x+=g-'0';
			if(cnt==0){
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd){
			if(is_neg){
				x= -x;
			}
			assert(l<=x && x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l,int r,char endd){
	string ret="";
	int cnt=0;
	while(true){
		char g=getchar();
		assert(g!=-1);
		if(g==endd){
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt && cnt<=r);
	return ret;
}
long long readIntSp(long long l,long long r){
	return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
	return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
	return readString(l,r,'\n');
}
string readStringSp(int l,int r){
	return readString(l,r,' ');
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	const int maxt = 20000, maxn = 4;
	int t = readIntLn(1, maxt);
	for(int _ = 1; _ <= t; _++){
		
		int n = readIntLn(1, maxn);
		vector<int> w(n), l(n), pos(n);
		iota(pos.begin(), pos.end(), 0);
		
		for(int i = 0; i < n; i++){
			if(i == n - 1) w[i] = readIntLn(1, n);
			else w[i] = readIntSp(1, n);
		}
		
		for(int i = 0; i < n; i++){
			if(i == n - 1) l[i] = readIntLn(1, 5);
			else l[i] = readIntSp(1, 5);
		}
		
		for(int i = 0; i < n; i++) for(int j = i + 1; j < n; j++){
			assert(w[i] != w[j]);
		}
 
		int ans = 0;
		for(int i = 1; i <= n; i++){
			int at = 0;
			while(w[at] != i) at++;
			for(int j = 0; j < n; j++){
				if(w[j] < w[at]){
					while(pos[at] <= pos[j]){
						pos[at] += l[at];
						ans += 1;
					}
				}
			}
		}
		cout << ans << '\n';
	}
	return 0;
}
 
Editorialist's Solution
/***************************************************

@author: vichitr
Compiled On: 06 Feb 2021

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

void solve(){
    int n; cin>>n;
    int W[n], L[n];
    for(int i=0; i<n;i++)
    	cin >> W[i];
    for(int i=0;i<n;i++)
    	cin >> L[i];
    int ans = 0;

    // make {weight, position} pairs
    vector<pair<int, int>> v(n);
    for(int i = 0; i < n; i++)
    	v[i] = {W[i], i};

    // sort in increasing order of weight
    sort(v.begin(), v.end());

    // now start with smallest frog
    // maintain the position of prev frog in order 
    int lastPosition = v[0].second; 

    // place the frogs in right order
    for(int i = 1; i < n; i++){
    	// cur frog position
    	int curPosition = v[i].second;
    	// index of current frog
    	int index = v[i].second;
    	// keep moving this frog until
    	// it crosses prev frog
    	while(curPosition <= lastPosition){
    		curPosition += L[index];
    		ans++;
    	}
    	// update lastPosition as cur frog position
    	lastPosition = curPosition;
    }
    
    cout<<ans<<'\n';
}

signed main()
{   
    int t=1;
    cin >>t;
    for(int i=1;i<=t;i++)
    {
        solve();
    }
    return 0;
}

VIDEO EDITORIAL:

7 Likes

@vichitr Nice Problem but why did you make it case-bashable due to super low constraints?

@satyankar_2005 it was supposed to be a simple problem that’s why constraints were low. And this was decided by the setter/admin, not me!

@vichitr Great problem. Getting started with CP and had fun!

3 Likes

can anybody help me with my code ?? plss explain whats going wrong
code is here - https://www.codechef.com/viewsolution/42841943

@bhavay2001 Line 17 is wrong. Let the position difference be 4 and L[i] = 3, you are adding 4/3 = 1. But actually you need 2 hits.

https://www.codechef.com/viewsolution/42483459
where this is failing?

My answer is partially correct… but I am not getting what is wrong for subtask 2.
Can someone explain where I am going wrong.
https://www.codechef.com/viewsolution/42847513

i understood the mistake as if the position difference will be less than the number of jumps the hits comes out to be zero , but couldn’t code it up properly , could u pls help me with its solution ??? I’m still facing some implementation issues and the editorial videos’s code is different from the setter code and tester code , soo pls help

@bhavay2001 See the hint under bonus problem.

This part of editorial. This is what you need to do. Replace the line 17 appropriately now.

At line 44, in the if condition it should be <=
Try running your code for the below testcase:
1
3
2 1 3
1 1 1

Your code outputs 2 instead of 3.

1 Like

@nikeshprasad9 OKay, understood. Thank you very much!!

1 Like

What you are trying to do is shift the 2nd frog at the rightmost available position, then shift the 3rd frog after the 2nd frog and then shift 4th frog after the 3rd frog.
This is the exact same mistake I did during the contest.

The problem doesn’t mentions that we have to move 2nd frog then 3rd then 4th, we can move them optimally in any order like 3rd then 4th then 2nd if required to minimise the number of hits.

So we will try to move 2nd frog just next to the 1st frog because even if the position next to 1st frog is currently occupied by 3rd frog it will be emptied after we move the 3rd frog to the rightmost position. So optimally it is like moving the 3rd frog first then moving the 2nd frog. Similarly we try to move the 3rd and 4th frog next to 2nd and 3rd frog respectively because even if it is currently occupied it will be available later.

Try this testcase:
1
3
2 1 3
1 1 1

https://www.codechef.com/viewsolution/42972467

Can anybody help me with java implementation. I am getting WA

@vichitr
What is the problem in my code given below . It shows partially correct
#include <bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while (t-- > 0)
{
int n;
cin >> n;
int a[n];
int b[n];
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < n; i++)
{
cin >> b[i];
}
int pos;
int c;
int tap = 0;
int i, j;
int k = 0;
for (i = 0; i < n; i++)
{
pos = 0;
for (j = 0; j < n; j++)
{
if (a[pos] > a[j])
pos = j;
}
a[pos] = 10 + i;
if (i >= 1)
{
if (c >= pos)
tap = tap + (int)ceil((double)(c - pos + 1) / b[pos]);
c = pos + (int)ceil((double)(c - pos + 1) / b[pos]) * b[pos];
}
else
{
c = pos;
}
}
cout << tap << endl;
}
}

Can anyone explain how the time complexity will be o(nlogn)??

Because of sorting!

Following the editorialist solution made the problem so easy to understand ,thanks man

1 Like