PROBLEM LINK:
Setter: Raj Khandor
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Easy
PREREQUISITES:
Observation would be enough.
PROBLEM:
Given a strictly decreasing array A with N elements at time 0, at each second, A_i increases by i for 1 \leq i \leq N
Find the first moment of time when there are at least two elements equal in A
QUICK EXPLANATION
- It is sufficient to check only pairs of consecutive integers, calculating the time when both integers would be equal and minimum time among all would be the required time.
- This works because increasing A_i by i and A_{i+1} by i+1 is equivalent to reducing their difference by 1 since A_i > A_{i+1} Hence, it is guaranteed that they’ll be equal after A_i-A_{i+1} seconds.
EXPLANATION
I’m going to use a few observations to obtain the required solution.
Lemma 1: For every consecutive pair of integers A_i and A_{i+1}, they become equal at time A_i - A_{i+1}
Proof: This one is fairly simple. Suppose t is the time A_i and A_{i+1} become equal, if they ever become equal.
At time t, we have A_i+i*t = A_{i+1}+(i+1)*t implying t = A_{i}-A_{i+1}. Since we are guaranteed that A_i > A_{i+1}, t is a positive integer, thus A_i and A_{i+1} become equal at time A_i-A_{i+1}
This also proves that consecutive elements always become equal at some point of time.
Lemma 2: In the final solution, only the times when any pair of consecutive integers become equal, matters.
Proof: Let us assume that minimum time to become equal is given by pair (A_i, A_i+2), say t and no consecutive pair gives time \leq t. Now, Since we initially have A_i > A_{i+1} > A_{i+2}, and now A_i = A_{i+2}, A_{i+1} must be one of the following cases.
- A_{i+1} = A_i = A_{i+2}
- A_{i+1} > A_i
- A_{i+1} < A_{i+2}
In the first case, t is also the minimum time given by a consecutive pair of integers (A_i, A_{i+1}) and pair (A_{i+1}, A_{i+2}), leading to contradiction in this case.
In the second case, we can apply first lemma to see that initially A_{i+1} < A_i and at time t, A_{i+1} > A_i implies pair (A_i, A_{i+1}) was equal at some time t' < t leading to contradiction in this case as well.
Lastly, in the third case as well, initially we have A_{i+1} > A_{i+2} and at time t we have A_{i+1} < A_{i+2} implying pair (A_{i+1}, A_{i+2}) was equal at some time t'' < t leading to contradiction.
Hence, our assumption is contradicted in every case, proving that the minimum time is always given by the minimum of times each pair of consecutive integers become equal.
After all this, we can easily compute the minimum time each consecutive pair of elements become equal and determine the minimum time.
TIME COMPLEXITY
Time complexity is O(N) per test case.
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
ll t;
cin>>t;
while(t--)
{
ll n;
cin>>n;
ll a[n];
for(ll i=0;i<n;i++)
cin>>a[i];
ll ans = LONG_MAX;
for(ll i=0;i<n-1;i++)
ans = min(ans,a[i]-a[i+1]);
cout<<ans<<"\n";
}
return 0;
}
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout)
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// find_by_order() // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
ll a[123456];
int main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
while(t--){
int n;
cin>>n;
int i;
rep(i,n){
cin>>a[i];
}
ll mini=a[0]-a[1];
rep(i,n-1){
mini=min(mini,a[i]-a[i+1]);
}
cout<<mini<<endl;
}
return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
public class Main{
//SOLUTION BEGIN
//Into the Hardware Mode
void pre() throws Exception{}
void solve(int TC)throws Exception{
int n = ni();
long[] a = new long[n];
for(int i = 0; i< n; i++)a[i] = nl();
long ans = a[0]-a[1];
for(int i = 1; i< n-1; i++)ans = Math.min(ans, a[i]-a[i+1]);
pn(ans);
}
//SOLUTION END
void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
void exit(boolean b){if(!b)System.exit(0);}
long IINF = (long)1e18;
final int INF = (int)1e9, MX = (int)2e6+5;
DecimalFormat df = new DecimalFormat("0.00");
double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-7;
static boolean multipleTC = true, memory = false, fileIO = false;
FastReader in;PrintWriter out;
void run() throws Exception{
if(fileIO){
in = new FastReader("C:/users/user/desktop/inp.in");
out = new PrintWriter("C:/users/user/desktop/out.out");
}else {
in = new FastReader();
out = new PrintWriter(System.out);
}
//Solution Credits: Taranpreet Singh
int T = (multipleTC)?ni():1;
pre();
for(int t = 1; t<= T; t++)solve(t);
out.flush();
out.close();
}
public static void main(String[] args) throws Exception{
if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
else new Main().run();
}
int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
void p(Object o){out.print(o);}
void pn(Object o){out.println(o);}
void pni(Object o){out.println(o);out.flush();}
String n()throws Exception{return in.next();}
String nln()throws Exception{return in.nextLine();}
int ni()throws Exception{return Integer.parseInt(in.next());}
long nl()throws Exception{return Long.parseLong(in.next());}
double nd()throws Exception{return Double.parseDouble(in.next());}
class FastReader{
BufferedReader br;
StringTokenizer st;
public FastReader(){
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws Exception{
br = new BufferedReader(new FileReader(s));
}
String next() throws Exception{
while (st == null || !st.hasMoreElements()){
try{
st = new StringTokenizer(br.readLine());
}catch (IOException e){
throw new Exception(e.toString());
}
}
return st.nextToken();
}
String nextLine() throws Exception{
String str = "";
try{
str = br.readLine();
}catch (IOException e){
throw new Exception(e.toString());
}
return str;
}
}
}
Feel free to share your approach. Suggestions are welcomed as always. 