CHEFQUER - Editorial

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?

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;

}

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

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

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

Vector slow, c array fast.

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

1 Like

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++?

1 Like

please someone give me the bruteforce solution

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

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

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.

I didn’t use bruteforce but still getting TLE can anyone check it please?Solution: 48293419 | CodeChef

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;
}

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.

1 Like

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

Ratings updated…

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;
}

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.

1 Like

Have the test cases been updated in the Practice ?