MAGIC123 - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: Shekhar Srivastava
Testers: Sandeep Singh, Arnab Chanda, Sunita Sen

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Knowledge of Sieve of Eratosthenes, Dynamic Programming

PROBLEM:

Chef is planning to eliminate the ghosts from his house with the help of some magical bullets he has. Each bullet has some power level P_i. A ghost can sometimes destroy the magical bullets if it possesses any of the skill S in the range 2 to K (both inclusive) such that S is a factor of P_i.

Given the set of guns (the power of the guns), Chef is having and chef wants to pick only those guns such that the ghost cannot destroy the bullet. Also whenever Chef picks up another gun the power level of this gun should be strictly greater than the previously used gun. He also does not want to alter the order of guns.

A ghost is eliminated only when the sum of powers of bullets it is shot with is greater than or equal to a value X.

Given the powers of guns, the value of K, and the value of X for a ghost find out whether this ghost can be killed or not.

EXPLANATION:

for each test case, we are given

  • the powers of N bullets chef has
  • the value of K
  • the value of X

from the given N bullets we have to find out the ones which cannot be divided by any numbers in the range 2 to K, this can be done efficiently as :

# this technique is similar to the sieve of Eratosthenes algorithm used to find all primes less than N
# create a boolean array mark of size equal to the value of maximum power gun
    mark = [True for _ in range(mp+1)]
    mark[0] = False
    for f in range(2, k+1): # outer loop runs from 2 to K
        if f<=mp:
            if mark[f]:
                mark[f]=False
                for x in range(f*f, mp+1, f): # mark all multiples of f as false
                    mark[x] = False

if the maximum power bullet has value P then the time complexity of finding usable guns becomes O(K.logP) and we need O(P) extra space

Now we need to find the Longest Increasing Subsequence or LIS of guns for which the index in mark array is true.

Note: given the large value of N we need to use some efficient algorithm to find the LIS. The expected time complexity for finding LIS is O(N.logN). You can find a very detailed explanation of the algorithm here.

If the size of LIS is greater than or equal to X then answer is YES else NO.

The overall time complexity is O( N.logN + K.logP ) and we need O(P) extra space.

SOLUTIONS:

Python 
import sys
import bisect
def find_lis(l):
    if len(l)==1:return l 
    lis = l[:1]
    for i in l[1:]:
        if i>lis[-1]:
            lis.append(i)
        else:
            lis[bisect.bisect_left(lis, i)] = i 
    return lis
 
for _ in range(int(sys.stdin.readline())):
    n,k,X = map(int, sys.stdin.readline().split())
    p = list(map(int, sys.stdin.readline().split()))
    mp = max(p)
 
    mark = [True for _ in range(mp+1)]
    
    mark[0] = False
 
    for f in range(2, k+1):
        if f<=mp:
            if mark[f]:
                mark[f]=False
                for x in range(f*f, mp+1, f):
                    mark[x] = False
    
    fin_p = [x for x in p if mark[x]]
 
    if len(fin_p):
        fin_p = find_lis(fin_p)
    
    sys.stdout.write("YES\n" if len(fin_p)>=X else "NO\n")
C++ 
    #include <bits/stdc++.h>
    #define ll long long 
    #define max(a,b) (a>b?a:b)
    #define min(a,b) (a<b?a:b)
    #define ln cout << '\n'
    #define mod 1000000007
    #define MxN 100005
    #define all(x) x.begin(), x.end()
    using namespace std;
     
    vector<string> ans = {"NO", "YES"};
    int CeilIndex(std::vector<int>& v, int l, int r, int key) 
    { 
        while (r - l > 1) { 
            int m = l + (r - l) / 2; 
            if (v[m] >= key) 
                r = m; 
            else
                l = m; 
        } 
      
        return r; 
    } 
      
    int LongestIncreasingSubsequenceLength(vector<int>& v) 
    { 
        if (v.size() == 0) 
            return 0; 
      
        std::vector<int> tail(v.size(), 0); 
        int length = 1; 
        tail[0] = v[0]; 
        for (size_t i = 1; i < v.size(); i++) { 
      
            if (v[i] < tail[0]) 
                tail[0] = v[i]; 
      
            else if (v[i] > tail[length - 1]) 
                tail[length++] = v[i]; 
            else
                tail[CeilIndex(tail, -1, length - 1, v[i])] = v[i]; 
        } 
      
        return length; 
    } 
     
    void solve(){
     
    	int i, j, n, k, tmp, x;
    	cin >> n >> k >> x;
    	vector <bool> ok(100005, 0);
    	vector <int> arr;
     
    	for(i = 2; i <= k; ++i){
    		for(j = i; j <= 100005; j += i)
    			ok[j] = 1;
    	}
     
    	for(i = 0; i < n; ++i){
    		cin >> tmp;
    		if(!ok[tmp])
    			arr.push_back(tmp);
    	}
     
    	if( k >= 5 && 0){
    		cout << "NO" << endl; return;
    	}
     
    	cout << ans[LongestIncreasingSubsequenceLength(arr) >= x] << "\n";
     
     
    }
    int main(){
     
    	ios_base::sync_with_stdio(false);
    	cin.tie(NULL);cout.tie(NULL);
     
    	#ifndef ONLINE_JUDGE
    		freopen("input.txt","r",stdin);
    	#endif
     
    	int t = 1;
    	cin >> t;
    	while(t--)
    		solve();
    }
1 Like