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;
}