You are not logged in. Please login at www.codechef.com to post your questions!

×

SMRSTR - Editorial

0
2

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:

This question is marked "community wiki".

asked 25 Nov '17, 08:28

melfice's gravatar image

4★melfice
811737
accept rate: 0%

edited 27 Nov '17, 18:03

admin's gravatar image

0★admin ♦♦
19.7k350498541


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?

link

answered 29 Dec '17, 15:05

kvsk's gravatar image

5★kvsk
5314
accept rate: 0%

Can someone explain this please?

(24 Nov '18, 01:03) the_extractor4★
2

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

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

(24 Nov '18, 18:46) mgch6★

Thank you!

(25 Nov '18, 00:16) the_extractor4★

not clear, mine code shows nzec error

link

answered 27 Nov '17, 18:57

singerisbest's gravatar image

1★singerisbest
1
accept rate: 0%

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.

(27 Nov '17, 19:37) yadnesh_viper3★
    #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?

link

answered 28 Nov '17, 10:04

gautamcse27's gravatar image

2★gautamcse27
375
accept rate: 0%

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 ?

(28 Nov '17, 10:31) gautamcse272★

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" *
* Language: C++14
* Facebook: https://www.facebook.com/sanchit.garg.3158 *
* Twitter : https://twitter.com/Thesanchitgarg * *************/

include <iostream>

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;

}

link

answered 01 Dec '17, 00:50

fad_coder00000's gravatar image

1★fad_coder00000
11
accept rate: 0%

edited 01 Dec '17, 00:53

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,482
×1,609
×98
×28

question asked: 25 Nov '17, 08:28

question was seen: 3,168 times

last updated: 25 Nov '18, 00:16