PROBLEM LINK:
Setter: Adarsh Agrawal
Tester: Radoslav Dimitrov
Editorialist: Raja Vardhan Reddy
DIFFICULTY:
Cake walk
PREREQUISITES:
NIL
PROBLEM:
Consider a 1D Coordinate system. Initially you are at x=0, and you make jumps along positive x-direction. Though, these jumps are not arbitrary. You are given an array A of N integers, and let
your current position be x, then you will make a jump to smallest y>x, such that y is a multiple of atleast one of the elements in the array A .This way you make jumps indefinitely.What is the maximum length jump that you would make?
EXPLANATION
Let the minimum element in the given array be k. Initially you make a jump of length k (jump from 0 to k) .
Claim: The length of any further jump you make is atmost k.
Proof: Assume you are making a jump with length more than k, that means you are skipping atleast k coordinates during this jump. But, one of these coordinates will be a multiple of k, hence by the constraint that the jump must be made to smallest y>x, this jump is invalid.
Hence, the length of maximum jump is k.
TIME COMPLEXITY:
Finding the smallest element by iterating through the given array = O(n) .
Total time complexity: O(n) for each test case.
SOLUTIONS:
Setter's Solution
#include "bits/stdc++.h"
using namespace std;
#define M 1000000007
#define U 998244353
#define N 1000005
#define int long long
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define rep(i,a,n) for(int i=a ; i<n ; i++)
#define r0 return 0;
#define endl '\n'
#define INF (int)1e15
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
std::cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');std::cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
signed main()
{
ios_base::sync_with_stdio(0);
int TESTS=1;
cin>>TESTS;
while(TESTS--)
{
int n;
cin >> n;;
int mn = INF;
rep(i,0,n){
int t;
cin >> t;
mn = min(mn, t);
}
cout<<mn<<endl;
}
}
Tester's Solution
from collections import deque
inf = 10 ** 18
def read_line_int():
return [int(x) for x in input().split()]
# -----------------#
# Main #
# -----------------#
T = read_line_int()[0]
for test in range(T):
n = read_line_int()
a = read_line_int()
print(min(a))
Editorialist's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#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)a; 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 int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int a[105];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,t1;
cin>>t;
// t=1;
t1=t;
while(t--){
int n,i,mini=inf;
cin>>n;
rep(i,n){
cin>>a[i];
mini=min(mini,a[i]);
}
cout<<mini<<endl;
}
return 0;
}
Feel free to Share your approach, If it differs. Suggestions are always welcomed.