Editorial-CHFCHK

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

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. :slight_smile:

Please forgive me, but could you explain the problem and the solution in a more simpler way?

1 Like

Let assume that you have to jump an value which is the multiple of any of the array elements but the constraints is that it should be smallest multiple (means multiply with 1 in element) of an element in the array , but you have to take a single jump means it is an smallest number in the array :slight_smile:

5 Likes

Someone help me. CodeChef: Practical coding for everyone
When I ran the example tests, Runtime Error. But when I submited, It’s successful? What happend?

Then why question explanation calculate it with 4 to 6. Shouldn’t it be 0 to 2?

#include <bits/stdc++.h>
using namespace std;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)


int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
 		int n;
		 cin >> n;
		 int x[n];
		 for(int i = 0; i < n; i++) {
		 	cin >> x[i];
		 }        
		 sort(x, x + n);
		 cout << x[0] << endl;
	}
}

link : CodeChef: Practical coding for everyone

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

int main() {
// your code goes here
int t,n,k,i,j,c=0;
cin>>t;
for(i=0;i<t;i++)
{
c=0;
k=0;
cin>>n;
int a[n];
for(j=0;j<n;j++)
{
cin>>a[j];
}
sort(a,a+n);
c=a[0];

    cout<<c<<endl;
}
return 0;

}

time complexity : O(nlogn)
the smallest element will be the answer because no jump can be bigger than the samllest number.