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
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.
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.