wrong answer for funny marbles(dec 2013 challenge)

@damn_me : ur mistake was in initial update of ur bit :(… codechef accepted soltion CodeChef: Practical coding for everyone :slight_smile:
hope this solved ur problem :slight_smile:

@squal saw CodeChef: Practical coding for everyone
what were the modifications that u made?

@anonymousins: changed only the size of sp from 10000002 to 1000002… result changed from WA to TLE…

please tell me what is wrong with this qOi6pV - Online C Compiler & Debugging Tool - Ideone.com
else i am going to change the approach :slight_smile:

@anonymousins: Bravo!!! :slight_smile: :slight_smile: ur effort paid off :slight_smile: just changed eff_gt and eff to long long int and know what it resulted in AC :slight_smile: :slight_smile: link: CodeChef: Practical coding for everyone (thanks to you i also learnt some c concepts while solving ur solution, my advice is that u learn BIT also coz its useful in many areas :slight_smile: :))

@squal
referring to this solutino of urs CodeChef: Practical coding for everyone and mine solution 6FEqJ2 - Online C++ Compiler & Debugging Tool - Ideone.com , u hav changed the bit initialisation, but why cant we do the way i hav done. I read the topcoder tutorial where it states( Topcoder ), the bit value is same as the array value if the index is an odd no. else summation of certain values. Also, i same the same initialisation in one more solution of some user but i dont have the link now but that got accepted during contest time. So, why such?

@damn_me: bit values computed for topcoder tutorial eg: ur solution: dgs0be - Online C++ Compiler & Debugging Tool - Ideone.com , my sol:xtuNWj - Online C++ Compiler & Debugging Tool - Ideone.com … see the bit tree value in the topcoder tutorial.

@squal Yeah… got my mistake now. However , i did one more way during contest but that gave wrong ans cuz of my array index. But thanks a lot!

First of all hats off to you :slight_smile:
still long long int temp[q];
int cs[n]; resulted in an AC and if u change to int temp[q],cs[n];
fetches a WA. How?

@anonymousins: there are cases like where the sum of a query exceeds the limit of int. There can be totally 10^6 students and each can have 2000 marbles atmost initially and more than that when given during queries. so obviously the resultant value would exceed the limit of int datatype. this is what causes WA when temp is declared int.

@damn_me: :slight_smile: :slight_smile:

but how int cs[n] works? it should also exceed int limit

@anonymousins: int range is –2,147,483,648 to 2,147,483,647, so cs can have atmost 2x10^9(all 10^6 students have 2000 marbles initially) which is <2,147,483,647,but temp in the worst case scenario can have 2x10^9+(50000x2000) which will not fit in int.

temp in the worst case scenario can have 2x10^9+(50000x2000)
Please explain this

@anonymousins: assume n=10^6 and each student is given 2000 marbles initially.
next consider q=50000, suppose the first 49999 queries are G i 2000 (0<=i<=N-1), the last query is S 0 999999 . since only one ‘S’ query, the temp[0] will have (200010^6)+(499992000)=2099998000 which is >int. :slight_smile:

But 1000 ≤ A[i] ≤ 2000

@anonymousins: that condition is applicable only for the initial a[i], it can increase during query phase :slight_smile:

Got it thanks :slight_smile: hope to implement it by BIT :slight_smile:

@anonymousins: happy to have helped :slight_smile: :slight_smile: