SMRSTR - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

Author: Misha Chorniy
Tester: Alexey Zayakin
Editorialist: Oleksandr Kulkov

DIFFICULTY:

CAKEWALK

PREREQUISITES:

None

PROBLEM:

You’re given array D of size N and Q queries X. In each query you have to compute the result of the program

read X
for i = 1..N:
  X = floor(X / D[i])
print X

QUICK EXPLANATION:

You should consider only O(\log X) terms such that D_i\neq 1.

EXPLANATION:

You may keep keep first \min(2\cdot\log_2 X, N) terms of D which aren’t equal one. If there are more non-one terms than X wiil definitely be equal zero at the end of procedure.

ALTERNATIVE SOLUTION:

You can keep product P of non-one terms of D instead of keeping this terms and divide X by P. But you should check then that you output zero if there are too much such terms.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

RELATED PROBLEMS:

1 Like
2

not clear, mine code shows nzec error

3

#include<bits/stdc++.h>

using namespace std;
 
#define ll long long
 
int main() {
    int t;
    cin>>t;
    while(t--) {
        int n,q;
        cin>>n>>q;
        vector<int>a;
        for(int i=0;i<n;i++) {
            int x; cin>>x;
            if(x>1) a.push_back(x);
        }
        int qr[q];
        for(int i=0;i<q;i++) cin>>qr[i];
        for(int i=0;i<q;i++) {
            int temp=qr[i];
            int idx=0;
            while(idx<a.size() && temp>0) {
                temp/=a[idx];
                idx++;
            }
            cout<<temp<<" ";
        }
        cout<<endl;
    }
 
    return 0;
}

why is there no TLE in solution?

4

Hey GUYS, PLz Give it a look , when i was doing this question i came to know an interesting fact that if i was using floor func then it’s giving TLE for subtask 2 , and if I was using int then it’s giving correct ans
NOTE: always use int type only.
SOLN :

/* AUTHOR : fad_coder00000 “FAD means enthusiasm for something” *

#include
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

int main()
{
ll t;

cin>>t;
while(t--)
{
    ll i,n,q,p=1,z=0,flag=0;
    cin>>n>>q;
    ll d[n+1]={0};
    for(i=0;i<n;i++) cin>>d[i];
    for(i=0;i<n;i++) 
    {
        p*=d[i];
        if(p>1000000000)
        {    flag=1;
             break;
        }
    }
    if(flag==1) 
    {
        while(q--) 
        {
            cin>>z;
            cout<<"0"<<" ";
        }
    }
    else
    {
        while(q--)
    {
        cin>>z;
        cout<<z/p<<" ";
    }
    }
    cout<<endl;
}
return 0;

}

5

Can anyone explain how alternative solution given in editorial is correct.

Also if ceil is considered (instead of floor) in the question, is the alternative solution (divide the given number with the product of array elements and then take ceil) still works?

2 Likes
6

It is unclear from what you said. Please provide a link to your code. And also check if you are dividing by zero in any case.

7

Is there only test cases for removing 1? In some of programme even in single loop there is TLE but here using two loops and Ac ?

8

Can someone explain this please?

9

[[x/a]/b]=[x/(a*b)], where [y] means the greatest integer not greater than y. Prove it :wink:

So, [[[x/d1]/d2]/…]/dn] = [[[x/(d1d2)]/d3]/…]/dn] = … [x/(d1d2…*dN)], the only one problem is that d1 * d2 * d3 * … * dn can not fits in long long, so you need to take min(d1 * d2 * … * dn, 1e18), but you need accurately do that.

long long INF = (long long)1e18 + 1;

if (curMul * di > INF) curMul = INF; // curMul * di can overflow, cause curMul < 1e18, di < 1e9.

if (curMul > INF / di) curMul = INF; else curMul *= di; //OK

Also, you can try to use __int128

6 Likes
10

Thank you!