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

×

TLE for Sub task 2 (ALATE)

Problem->[ALATE]: https://www.codechef.com/LOCAUG17/problems/ALATE

Please give suggestions to improve my code so that it passes Sub task 2 without TLE(Please help me)

#include bits/stdc++.h
#define ll long long
#define MOD 1000000007
#define N 1000005
using namespace std;
ll a[N],n;
ll func(ll x)
{
    ll k,sum=0;
    for(ll i=x;i<=n;i+=x)
    {
        k=(a[i]*a[i])%MOD;
        sum=(sum+(a[i]*a[i]))%MOD;
        sum%=MOD;
    }
    return sum;
}
int main()
{
    ll t,q,i,j,qno,x,y;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld",&n,&q);
        for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
        for(j=1;j<=q;j++)
        {
            scanf("%lld",&qno);
            if(qno==1)
            {
                scanf("%lld",&x);
                printf("%lld\n",func(x));               
            }
            else
            {
                scanf("%lld%lld",&x,&y);
                a[x]=y;
            }       
        }
    }
    return 0;
}

asked 29 Aug '17, 00:31

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 29 Aug '17, 00:35


Hey @ramini,

To solve this question, ALATE from August Loc you need to do some precomputation so as to fit the answer in specified time-limit.

Since "func" calculates the sum of a given index x and all it's multiple in the given array(squares). So we can precompute all the values for x.

for(i=1;i<=n;i++) {

s=0;

for(j=i;j<=n;j+=i){

  s = ( s + (arr[i]*arr[i]) % 1000000007) % 1000000007 ;

}

sum[i] = s ;

}

Since you have all the pre-computed values than your query of type 1 can be answered in O(1) but the problem arises in the update query for that you need to know which values are actually going to be affected by the change of that particular x. (this is also pre-computed) so whenever a query of 2nd type occurs than you have to iterate over the values of sum[i] which are going to be affected and update their new values which are sum[i]-arr[i]arr[i]+newValue newValue;

EDIT:- First we will pre-compute which are going to affected by the index x.

vector <long> v[100001];
for(ii=1;ii<100001;ii++) { for(jj=ii;jj<100001;jj+=ii) v[jj].push_back(ii); }

After that we just need to iterate over the affected values and update them as they are stored in v[x]

for(i=0;i<v[x].size();i++) {

          sum[v[x][i]] = (sum[v[x][i]] - sq[x] +

nsq+1000000007) %1000000007 ;

         }

where nsq is new square value.

Hope this helps!

(Code)

link

answered 29 Aug '17, 01:38

sandeep_007's gravatar image

5★sandeep_007
7997
accept rate: 16%

edited 29 Aug '17, 02:05

If not clear, please have a look at the code.if after that also your doubt is not clear.. comment below.

(29 Aug '17, 01:44) sandeep_0075★

first store all the divisor of 1 to 100000 using sieve .make a dp to store all the func(x) value for all indexes.for query no 2 update all the indexes which divides the x by iterating through all the divisors of x. hope this helps

link

answered 29 Aug '17, 01:13

manaranjanfav's gravatar image

4★manaranjanfav
235
accept rate: 0%

Can you please be more elaborate? If possible can you share your code with comments if you've done it.

link

answered 29 Aug '17, 01:32

ramini's gravatar image

2★ramini
615
accept rate: 8%

Can you please explain how did you update the values of sum[i]?

link

answered 29 Aug '17, 01:57

ramini's gravatar image

2★ramini
615
accept rate: 8%

updated the answer.

(29 Aug '17, 02:05) sandeep_0075★

I understood finally. Thank you so so so much!!! You made me learn something.

link

answered 29 Aug '17, 02:19

ramini's gravatar image

2★ramini
615
accept rate: 8%

Hey @sandeep_007 I wrote the code as you said. But I am getting an error as shown in Ideone. What's wrong in it?Please help bro.

include bits/stdc++.h

define MOD 1000000007

define ll long long

using namespace std; ll a[100001]; ll sum[100001]={0}; ll n;

ll s[100001][100001]={0};

void precompute() {
for(ll i=1;i<=n;i++) { for(ll j=i;j<=n;j+=i) { sum[i]=(sum[i]+(a[j]a[j])%MOD)%MOD; } }
} void effect() { for(ll i=1;i<=100000;i++) { for(ll j=i;j<=100000;j+=i) { s[i][j]=i; } } } int main() { ll t; scanf("%lld",&t); effect(); while(t--) { ll q,i,j,nsq,qno,x,y; scanf("%lld%lld",&n,&q); for(i=1;i<=n;i++) scanf("%lld",&a[i]); precompute(); while(q--) { scanf("%lld",&qno); if(qno==1) { scanf("%lld",&x); printf("%lld\n",sum[x]); } else if(qno==2) { scanf("%lld%lld",&x,&y); nsq=(y
y)%MOD; j=x; for(i=1;i<=n;i++) { if(s[i][j]!=0) { sum[(s[i][j])]=(sum[(s[i][j])]-((a[x]*a[x])%MOD)+nsq)%MOD; } } a[x]=y; } }
} return 0; }

link

answered 29 Aug '17, 12:29

ramini's gravatar image

2★ramini
615
accept rate: 8%

edited 29 Aug '17, 12:32

Hey @ramini

it was great to hear from you again, you just did a small mistake, an array of that much size cannot be initialized so you have to make a vector.

(29 Aug '17, 12:37) sandeep_0075★

if you aren't familiar with vector, follow the tutorials on hackerrank.

(29 Aug '17, 12:38) sandeep_0075★

@sandeep_007 it will be helpful for me if you check my solution ! even i had updated for query 2 https://www.codechef.com/viewsolution/15134001 i had thought over it for hours! plz !

link

answered 29 Aug '17, 12:42

cis_pie's gravatar image

5★cis_pie
1055
accept rate: 9%

Hey @sandeep_007, I still get tle even subtask1 , can you look at it. ideone

link

answered 29 Aug '17, 20:13

we7d's gravatar image

2★we7d
222
accept rate: 0%

Hey @we7d,

Your solution goes wrong when you are taking input in %d while it should be %lld as 'a' is long long.

for(int i=1;i<=n;i++){scanf("%d",a+i);a[i] = a[i]*a[i] %MOD;sum[i]=0;}

Hope this helps!

link

answered 29 Aug '17, 20:16

sandeep_007's gravatar image

5★sandeep_007
7997
accept rate: 16%

#include<iostream>
#include<cmath>
#define mod 1000000007
#define sc scanf
#define ll long long int

using namespace std;

void update(ll A[],ll ar[],ll index,ll val)
{
    ll t=(val*val-ar[index]*ar[index]+3*mod)%mod;
    A[index]=(A[index]+t+3*mod)%mod;
    for(ll i=1;index!=1 && i<=sqrt(index);++i)
    {
        if(index%i==0)
        A[i]=(A[i]+t)%mod;
    }       
}

int main()
{
    int t;  sc("%d",&t);
    while(t--)
    {
        ll no,Q;  sc("%lld %lld",&no,&Q);
        ll ar[no+1]={0},A[no+1]={0};

        for(ll i=1;i<=no;++i)
        {
            sc("%lld",&ar[i]);
        //  ar[i]=(ar[i]*ar[i])%mod;
        //  A[i]=ar[i];
            A[i]=(ar[i]*ar[i])%mod;
            for(ll j=1;i!=1 && j<=sqrt(i);++j)
            {
                if(i%j==0)
                A[j]=(A[i]+A[j])%mod;
            }
        }
/*      
        for(int i=1;i<=no;++i)
        cout<<ar[i]<<" ";
        cout<<endl;
        for(int i=1;i<=no;++i)
        cout<<A[i]<<" ";
        cout<<endl;     
*/      
        while(Q--)
        {
            ll c,x;  ll y;
            sc("%lld",&c);
            if(c==2)
            {
                sc("%lld %lld",&x,&y);
                update(A,ar,x,y);
                ar[x]=y;
            }
            else
            {
                sc("%lld",&x);
                printf("%lld\n",A[x]%mod);

            }
        }

    }

    return 0;
}

Why my answer is wrong???? plz help...

link

answered 01 Sep '17, 02:49

supriyanta's gravatar image

1★supriyanta
11
accept rate: 0%

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:

×715
×14

question asked: 29 Aug '17, 00:31

question was seen: 563 times

last updated: 01 Sep '17, 02:49