Can Someone Please Tell Me Why is this Happening ?
Problem : 1238B - Kill `Em All
83162183 This Submission gives TLE
83162136 This Submission gets Accepted
The only difference in both the submissions is shown in the picture
i added one single line of code and got TLE
if i remove this green highlighted line of code the solution gets Accepted ,
Even if I am removing the if condition , the solution gets accepted 83161695
Auto comment: topic has been updated by tejustiwari (previous revision, new revision, compare).
Auto comment: topic has been updated by tejustiwari (previous revision, new revision, compare).
One thing I realized is that the size of template is inversely proportional to the rating of person. At the end you only used basic stl and manipulation, so what was the need of such long template??
That makes no difference kingkong1 & that is not the reason for getting a TLE verdict. Unrated people talking about ratings HUH ! You better Give some contests then we'll talk about ratings and proportionality.
MiFaFaOvO, Um_nik, tourist (occasionally), maroonrk, Benq, and Radewoosh all use templates. These are just a few Legendary Grandmasters that do.
hmm yes so u must have a mega long template, get kong'd
I'm not sure, but declaring
int val[100005] = {}for every test case might cause TLE. I guess maybe modifyingvalmeans that it has to be reinitialized every time. There's no use forvalanyways, sincesetautomatically removes duplicates.In general, try to avoid declaring large constant-length arrays for each test case.
thanks qpwoeirut but have a look at the accepted solution in which i am doing the same . I am declaring
int val[100005] = {}for every test case still the solution gets accepted .Using val[] { the highlighted part } inside the if condition is the reason behind TLE which I suppose is an
O(1)operation and must not be the reason behind TLE but sadly it is the only reasonHere are some interesting observations:
valfromint[]tobool[]gets AC even withval[a[i]] = 1operation enabled.valglobal doesn't help.val[a[i]] = 1operation enabled. 83166543It's some peculiar behaviour. It will be interesting to see if somebody can explain this.
It's definitely not the operation costs.
Below code gets AC and it does everything.
Submission 83167312
TLE occurs only if the statement
val[a[i]] = 1is inside theif (val[a[i]] != 1)condition andvalis anint[]array;Thankyou Grey_Matter for your Great Observations .
Yeah
val[a[i]] = 1is the only reason behind getting TLE .And i guess assigning
val[a[i]] = 1inside the if condition is no more than O(1)If u change int val [ ] to bool val [ ] .. your solution will work.
your edited solution
my solution
found something : )
bool vs int comparison (time)
Which value is better to use? Boolean true or Integer 1?
Thanks Anadii it helped a lot
I use bitset everytime instead of declaring an array of bool.
instead of bool vis[MAXN] ={0);
I write bitset < MAXN > vis; // By default every bit is set 0.
Now you can use this just like you use array by this operator []. Also when you want to clear all the bits of vis array to 0 you can use memset or do it manually taking O(MAXN) time. While in case of bitset you write vis.clear(); And this takes O(MAXN/32) time.
Thanks for sharing Ricktarded
If you do not modify elements of val[] array, the compiler knows its values (all zeroes btw) and optimizes code accordingly.
You can analyze it here: https://godbolt.org/z/NQBf32