WAV2- Editorial

I think you made the logic too complicated. It only needs to use binary search get index, if index >=0. Means exist in array. res is 0. Otherwise calculate the negative counts with opposite index. See my Java approach CodeChef: Practical coding for everyone

please help in my code why they give TLE?
in python lang

n,Q= map(int,input().split())

a = list(map(int,input().split()))

a.sort()

for i in range(Q):

q = int(input())

if q in a:

    print('0')



else:

    d = 0

    for j in a:

        if q < j:

            d+=1

    if d%2 == 0:

        print("POSITIVE")

    else:

        print("NEGATIVE")

Someone please help me to figure out whats wrong in my code.
I have spent 2.5 hr mugging up in this question still getting WA
I binary searched for the upper bound .
HERE is my code.

#include<stdio.h>

int main()
{int N,Q,product=1;
scanf("%d %d",&N,&Q);
int a[N],x[Q];
for(int i=0;i<N;i++)
{
scanf("%d",&a[i]);

}
for(int a=0;a<Q;a++)
{
scanf("%d",&x[a]);
}for(int b=0;b<Q;b++)
{
for(int j=0;j<N;j++)
{
product=product*(x[b]-a[j]);

}

if(product>0)
{
printf(“POSITIVE\n”);

}
else if(product==0)
{
printf(“0\n”);

}
else if(product<0)
printf(“NEGATIVE\n”);

product=1;

}

return 0;

}

hey i solved the wave problem of polynomial in c & i got the correct output but it says time limit exceeded i.e is 1.01 seconds

I am back with another issue. Are the test cases Weak?

The Code getting AC Verdict
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <utility>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define FOR(x, N)					for(int x = 0; x < N; x++)
#define inverse(a, p)				power(a, p - 2, p)

typedef unsigned long long int ull;
typedef long long int ll;

const int dc[] = {1, 0, 0, -1, -1, -1, 1, 1};
const int dr[] = {0, 1, -1, 0, -1, 1, -1, 1};

const ll shit	= ((ll)(998244353));
const ll mod	= ((ll)(1e9 + 7));
const ll hell	= ((ll)(1e9 + 9));
const ll inf	= ((ll)(1e18 + 3));

static inline ll gcd(ll a, ll b) {
	for(ll rem; b > 0; rem = a % b, a = b, b = rem);
	return a;
}
static inline ll lcm(ll a, ll b) {
	return (a * b) / gcd(a, b);
}
static inline ll mul(ll a, ll b, ll p) {
	return ((a % p * b % p) % p + p) % p;
}
static inline ll add(ll a, ll b, ll p) {
	return ((a % p + b % p) % p + p) % p;
}
static inline ll sub(ll a, ll b, ll p) {
	return ((a % p - b % p) + p) % p;
}
static inline ll SUM(ll a, ll b) {
	return a + b;
}
static inline ll AND(ll a, ll b) {
	return a & b;
}
static inline ll XOR(ll a, ll b) {
	return a ^ b;
}
static inline ll OR(ll a, ll b) {
	return a | b;
}

#define nax 2000003


void preCompute() {
	return;
}

template <typename T>
int binarySearch(vector<T> &a, T key) {
    int lb = 0;
    int ub = a.size() - 1;
    while(lb <= ub) {
        int mid = (lb + ub) / 2;
        if(a[mid] == key) {
            return mid;
        }
        else if(a[mid] < key) {
            lb = mid + 1;
        }
        else {
            ub = mid - 1;
        }
    }
    return -1;
}

template <typename T>
int bisect_left(vector<T> &a, T key) {
    int ind = binarySearch(a, key);
    double k = key;
    if(ind != -1) {
        k = ((double)(key)) - 0.5;
    }
    int lb = 0, ub = a.size() - 1;
    while(lb <= ub) {
        int mid = (lb + ub) / 2;
        if(a[mid] < k) {
            lb = mid + 1;
        }
        else {
            ub = mid - 1;
        }
    }
    return lb;
}

void solve() {
	int n, q;
	cin >> n >> q;
	vector<int> a(n);
	for(auto &x: a) {
		cin >> x;
	}
	sort(a.begin(), a.end());
	for(; q > 0; q--) {
		int x;
		cin >> x;
		if(binarySearch(a, x) != -1) {
			cout << 0 << '\n';
			continue;
		}
		int pos = bisect_left(a, x);
		int neg_count = pos;
		if(neg_count % 2) {
			cout << "NEGATIVE" << '\n';
		}
		else {
			cout << "POSITIVE" << '\n';
		}
	}
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int t = 0;
	t++;
	if(!t) cin >> t;
	preCompute();
	FOR(test, t) {
		// cout << "Case #" << (test + 1) << ": ";
		solve();
	}
	return 0;
}

Input

5 6
1 3 5 100 120
-2
2
4
80
107
5

Expected Output (Edited)

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

Code’s Output

POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
0

Now that the problem had more than 3282 + 4109 = 7391 successful submissions during the contest, can we accept this?

So did they take some action already?

They didn’t and I guess they never do. And I can’t resist myself from pointing out mistakes.

Your code’s time complexity is O(N*Q) and your product variable is bound to overflow. Check the constraints.

There isn’t a binary search operation in your code @amandikshit10. Your time complexity is O(N*Q).

1 Like

Find has an approximately linear time complexity @tushar_harsh. Check this out: http://www.cplusplus.com/reference/algorithm/find/

1 Like

@rogue_raven

According to your set, P(x) = (x - 1)(x - 3)(x - 5)(x - 100)(x - 120)
In this case putting your queries in place of x gives the following output which is expected from the problem:

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

which does not match with your either of your expected or code’s output. No idea how your code got AC.

Hey shouldn’t the actual output be :
NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

I overlooked the negative sign. Yes, the expected output is

NEGATIVE
POSITIVE
NEGATIVE
POSITIVE
NEGATIVE
0

Let me edit that.

“Poor test cases” is the only reason. Author and tester are responsible for that.

oh ! all this time I thought it was constant, my bad not considering it, thanks !!

1 Like

Your code does not even pass the example test case. Please refer to the proper usage of lower_bound algorithm function. Your code got AC due to their poor test cases.

can someone explain TLE reason here
https://www.codechef.com/viewsolution/48057518

You are sorting the array Q times…just sort it once before taking the queries

1 Like

I have no idea what is the time complexity is. and I can’t see any constraint issue in the product variable.