CHEFQUER - Editorial

[psitapati10]

n,q=map(int,input().split())
l=list(map(int,input().split()))
for i in range(q):
    p=list(map(int,input().split()))
    if p[0]==1:
        L,R,X=p[1]-1,p[2],p[3]
        k=0
        for j in range(L,R):
            l[j]+=(X+k)*(X+k)
            k+=1
    else:
        print(l[p[1]-1])

What happened?u were not able to access the link i provided or u mean the logic is not so clear with the variables?

[rraj45035]

When I brute-forced with Vectors, it showed me TLE, but it got passed on using arrays. Can anyone please clarify when to use vectors and when to use arrays?

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define f1(a, b) for (int i = a; i < b; i++)
#define f2(a, b) for (int i = a; i > b; i–)
void boost()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
int main()
{
// boost();
int t;
ll a, b, temp, l, r, x, y;
cin >> a >> b;
//cout<<a<<b<<endl;
vector v;
f1(0, a)
{
cin >> temp;
v.push_back(temp);
}

f1(0, b)
{
    cin >> temp;
   
    if (temp == 1)
    {
        cin >> l >> r >> x;
        
        for (ll j = l; j <= r; j++)
        {
            v[j-1] +=(x + j - l)*(x + j - l);
           // cout<<v[j-1]<<"r"<<endl;
        }
    }
    else
    {cin>>y;
    
        cout<<v[y-1]<<"\n";
    }
}
return 0;

}

[ratneshpatil33]

y do we use fenwick arrays instead of vector to store the changes
note:- i dk about fenwick arrays

[gouravsingh675]

why do I get an error saying “Time limit exceeded” for my code as below for this question, it works locally for me; please help me, thank you!
https://www.codechef.com/viewsolution/48305839

[sarvesh_21]

Why brute force is working here,please recheck all passed AC solutions with strong test cases.

[alexmercerind]

Vector slow, c array fast.

[amitired]

Meanwhile, me who didn’t even try the BruteForce, lol!

[sandipan_2224]

I have a small question. Why does my brute force approach [O(N*Q)] gives TLE with a vector but passes under 1s with an array-based implementation in C++?

[sabertooth_69]

please someone give me the bruteforce solution

[sandipan_2224]

https://www.codechef.com/viewsolution/48307545

[aryaniiit123]

link was directing to my page…
I too did this after knowing the brute force thing…
I did in c++

[vichitr]

what you shared is not a link to your submission rather its link to submit page. Submission link looks like this https://www.codechef.com/viewsolution/48282321.

[varreyrishi]

I didn’t use bruteforce but still getting TLE can anyone check it please?CodeChef: Practical coding for everyone

[abhinav_700]

can anyone tell why my brute force method runs fine for given test case but gives runtime error during submission

#include <iostream>
#include<vector>
#include<cmath>
using namespace std;
long long int power(long long int x,long long int y)
{


    long long int res = 1;
    while (y)
    {
        if (y % 2 == 1)
            res = (res * x);


        y = y >> 1;

        x = (x * x);
    }
    return res;
}
int main() {
	// your code goes here
	long long int n,a,q;
	cin>>n>>q;

	vector<long long int>arr;
	for(long long int i=1;i<=n;i++)
	{
	    cin>>a;
    	arr.push_back(a);
	}
	q+=2;
	while(q-=2)
	{
	    long long int c1,c2,l,r,x,y;
	    cin>>c1>>l>>r>>x;
	    cin>>c2>>y;
	    for(long long int i=l;i<=r;i++)
	    {
	        arr[i-1]+=power(x+i-l,2);
	    }
	    cout<<arr[y-1]<<endl;

	}

	return 0;
}

[admin]

Our test data was weak for this problem. Apologies for the mistake. We’ll be adding stronger data in Practice, but the contest submissions will remain as they are.

[coder_shriv]

I did this problem both in python and cpp as well…
Can anyone please tell why it gives TLE in python and AC in cpp??

python submission
cpp submission

[coder_shriv]

Ratings updated…

[tusharnath10]

Could someone tell where I went wrong?

#include <bits/stdc++.h>

#define for0(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define forc(i, l, r) for (int i = (int)(l); i <= (int)®; ++i)
#define forr0(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define forr1(i, n) for (int i = (int)(n); i >= 1; --i)

using namespace std;

#define pb push_back
#define pob pop_back
#define fi first
#define se second

typedef vector vi;
typedef vector vvi;
typedef pair<int, int> ii;
typedef vector vii;
typedef long long ll;
typedef vector vll;
typedef vector vvll;
typedef double ld;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.precision(10);
cout << fixed;
int t;
cin>>t;
while(t–)
{
int l,h,x=0,count=0,m=0;
cin>>l>>h;
string str;
cin>>str;
for0(i,l)
{
if (str[i]==‘0’)
{
x++;
m++;
if(x==h || m==h) count++;
}
else if (str[i]==‘1’ && x!=0 && str[i-1]!=1)
{
h=2*(h-x);
m=0;
}
}
if(count>0) cout<<“YES”<<endl;
else cout<<“NO”<<endl;
}
return 0;
}

[aloo08051999]

Please CodeChef focus on giving good test cases passing brute force is not at all acceptable because it causes major issues in ranking. Btw Good Problem.

[bubu2006]

Have the test cases been updated in the Practice ?