The Revenge Editorial.
PROBLEM LINK: CodeChef: Practical coding for everyone
Author: Reyaan Jagnani
Tester: Jay Sharma
Editorialist: Reyaan Jagnani
DIFFICULTY:
EASY
PREREQUISITES:
Math
PROBLEM:
To find the minimum time at which all the cabbies reach at (22,1) on X-Y plane together.
EXPLANATION:
First of all, as point number 4 in note in question, a cabbie cannot come back to the position he was before ever again. So check the edge cases if
some cabbie (1 or more) or all cabbies are initially at (22,1).
There is one observation that if the least time taken by a cabbie is K and the speed is X, then the the cabbie can reach the destination for every distance of the form (K*X)-(2*i).
After that, we will make total 4 cases -
- Distance between (22,1) and initital cabbie position is odd and its speed is even -> This cabbie will never be able to reach (22,1) because we cannot move odd positions if the speed given is even.
- Distance between (22,1) and initital cabbie position is odd and its speed is odd -> Take the ceil value of distance/speed which gives us the minimum time. Consider K = distance/speed . Now if this value is even, add 1 to it, because odd position can only be achieved in odd number of moves if the speed is odd. So the time at which cabbie will reach (22,1) is K + 2i.
- Distance between (22,1) and initital cabbie position is even and its speed is odd -> Take the ceil value of distance/speed which gives us the minimum time. Consider K = distance/speed . Now if this value is odd, add 1 to it, because even position can only be achieved in even number of moves if the speed is odd. So the time at which cabbie will reach (22,1) is K + 2i.
- Distance between (22,1) and initital cabbie position is even and its speed is even -> Take the ceil value of distance/speed which gives us the minimum time. Consider K = distance/speed . even position can be achieved in odd as well as even number of moves if the speed is even. So the time at which cabbie will reach (22,1) is K + i.
Now we just have to find the minimum number that is consistent with all the above constraints. and if any there are conflicting constraints the answer will be -1.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define testcase ll t; cin>>t; while(t--)
#define endl "\n"
#define quick ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define timetaken cerr<<fixed<<setprecision(10); cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " secs" << endl
using namespace std;
ll division(ll a, ll b)
{
return (a+b-1)/b;
}
int main()
{
quick;
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
testcase
{
ll n, cabbies_with_0_distance=0, max_single = -1, max_double = -1;
cin>>n;
vector<pair<ll,ll>> pos;
vector<ll> speed(n),even,odd,diff,single;
bool check1=1,check=1;
for(ll i=0; i<n; i++)
{
ll x,y;
cin>>x>>y;
pos.pb({x,y});
if(x==22 && y==1) cabbies_with_0_distance++;
}
for(ll i=0; i<n; i++) cin>>speed[i];
if(cabbies_with_0_distance==n)
{
cout<<"0"<<endl;
continue;
}
for(ll i=0; i<n; i++)
{
if(pos[i].first==22 && pos[i].second==1)
{
check1=0;
break;
}
}
if(!check1)
{
cout<<"-1"<<endl;
continue;
}
for(ll i=0; i<n; i++)
{
ll a = abs(pos[i].first-22) + abs(pos[i].second-1);
diff.pb(a);
}
for(ll i=0; i<n; i++)
{
ll a = division(diff[i],speed[i]);
if(diff[i]%2 && speed[i]%2==0)
{
check=0;
break;
}
else if(diff[i]%2 && speed[i]%2)
{
if(a%2==0) a++;
odd.pb(a);
}
else if(diff[i]%2==0 && speed[i]%2)
{
if(a%2) a++;
even.pb(a);
}
else single.pb(a);
}
if(!check)
{
cout<<"-1"<<endl;
continue;
}
if(odd.size()>0 && even.size()>0)
{
cout<<"-1"<<endl;
continue;
}
if(single.size()>0) for(ll i=0; i<single.size(); i++) max_single = max(max_single,single[i]);
if(odd.size()>0) for(ll i=0; i<odd.size(); i++) max_double = max(max_double,odd[i]);
if(even.size()>0) for(ll i=0; i<even.size(); i++) max_double = max(max_double,even[i]);
if(max_single==-1)
{
cout<<max_double<<endl;
continue;
}
if(max_double==-1)
{
cout<<max_single<<endl;
continue;
}
if(max_double>=max_single)
{
cout<<max_double<<endl;
continue;
}
if(max_double%2==0)
{
if(max_single%2==0) cout<<max_single<<endl;
else cout<<max_single+1<<endl;
}
else
{
if(max_single%2) cout<<max_single<<endl;
else cout<<max_single+1<<endl;
}
}
timetaken;
return 0;
}
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int tt=1;
cin >> tt;
while(tt--)
{
int n;
cin >> n;
int x[n],y[n],s[n];
for(int i=0;i<n;i++)
cin >> x[i] >> y[i];
for(int i=0;i<n;i++)
cin >> s[i];
bool poss=true,even=false,odd=false,zero=false;
int d[n];
for(int i=0;i<n;i++)
{
d[i]=abs(x[i]-22)+abs(y[i]-1);
if(d[i]%2==1 && s[i]%2==0)
poss=false;
if(d[i]%2==0 && s[i]%2==1)
even=true;
if(d[i]%2==1 && s[i]%2==1)
odd=true;
if(d[i]==0)
zero=true;
}
if(even && odd)
poss=false;
if(!poss)
cout << -1 << '\n';
else
{
int ans = 0;
for(int i=0;i<n;i++)
ans = max(ans,(d[i]+s[i]-1)/s[i]);
if(even && ans%2==1)
ans++;
if(odd && ans%2==0)
ans++;
if(ans>0 && zero)
cout << -1 << '\n';
else
cout << ans << '\n';
}
}
return 0;
}