PROBLEM LINK:Author: Misha Chorniy DIFFICULTY:EasyMedium PREREQUISITES:HashTable PROBLEM:Given two types of queries: The numbers to be inserted/deleted are generated according to the following scheme: The sum of the numbers finally remaining in the set after all the operations is to be reported. EXPLANATION:Given the number of operations to be executed, i.e., $q = 10^7$, it should be clear that the insertions and deletions from the set are to be done in $\mathcal{O}(1)$. Use of STL or prewritten libraries in C++/Java can't be used since they will definitely time out because of associated overheads. Hash Table Solution One way is to write our own hash table. Editorialist's solution provides a standard implementation of HashTable with chaining to handle collision. For chaining, linked list has been used in the given solution. You can read more about it over the internet. Bitset Solution A neater and more concise solution is using Bitset. Let's think about the naive solution to this problem first. If we could simply keep an array of length $2^{32}1$, then direct insert/lookup in the array would have been possible. The the memory constraints don't allow that big an array. However, let us look at the constraints on the number being inserted/deleted into the set. We know they lie between 0 and $2^{32}1$, i.e., they can be represented by 31 bits. Now, we can use a smart way to index numbers. Let us keep an array of length $2^{26}$. This is perfectly fine with the memory limits. Now, for a 31 bit integer $x$, let the first 26 bits indicate the index in the array where $x$ will reside. The rest 5 bits can be encoded in a 32 bit integer since only different $2^5$ possibilities exist. Please read setter's/tester's solutions for this approach. There is one more intricacy here: calculating $S_i$. If we use the normal $mod$ operation present in some of the programming languages, the solution will exceed time limit. This is because $mod$ is a complex operation and performing it $10^7$ times will not work. The observation is that we have to take $mod$ $2^{32}$. If we keep the data type of $S$, $a$, $b$ to be unsigned, in that case, we will not have to use $mod$ operation because the range of unsigned int is $0$ to $2^{32}1$. Thus, if $S$ goes over $2^{32}$ it will automatically overflow around to greater than $0$. In other words, the compiler will perform the $mod$ function implicitly because of the overflow. COMPLEXITY:$\mathcal{O}(1)$ per insert and delete operation. SAMPLE SOLUTIONS:
This question is marked "community wiki".
asked 16 Dec '15, 13:27

The timelimit wasn't struct enough to prohibit all O(Nlog(N)) approaches. Sorting worked in time. Put the ith queries in a array as triplet (no, i,b), where no is the number of element and b 1 for insertion and 0 for delete. After sorting counting is easy in a single pass. answered 21 Dec '15, 00:15

Was really a tough question to crack. I had heard of bitset earliar but never used it. Tried to read it concept during the contest but couldn't understand it properly. But then got a link to this https://discuss.codechef.com/questions/72572/markinglargeintegers which helped a lot. I also tried to use unordered map (which is available in C++14 as C++4.9.2 gave compile error) but in some worst case in give O(n) complexity due to rehashing. So, I avoided it. Finally, a very naive implementation of the idea given in the above link helped to get AC. (although the 2ns input provided 10000000 777777777 777777777 777777777, took 2.16 sec on Codechef ide and 2.37 sec on my computer to run). So, just to try my luck, at the last moments of the contest, i made and submission and was happy to get AC on the first attempt. Here is a link to my ACed solution https://www.codechef.com/viewsolution/8989357 answered 21 Dec '15, 00:18

I got it accepted using hashtable approach mentioned above same as editorialist's way... answered 21 Dec '15, 00:13

Did it using my own definition of hashtable by handling of collisions through chaining implemented through linked list. Solution link:https://www.codechef.com/viewsolution/8988520 answered 21 Dec '15, 00:11

Umm...I declared a bool vector of length 2^(31) and got AC. Is it possible to do so or I just got lucky here? :P My solution: https://www.codechef.com/viewsolution/8987936 answered 21 Dec '15, 00:08

@pranavarora vector < bool > <> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes. answered 21 Dec '15, 00:09

I got segfault with the same idea as @pranavarora and tle with the same idea as editorialist. answered 21 Dec '15, 00:11

Because ar.resize() allocate many memory, and stack not enough for it. You should allocate memory globally. http://pastie.org/10643748 answered 21 Dec '15, 00:18

@mgch see my first submission. Link : https://www.codechef.com/viewsolution/8988268 answered 21 Dec '15, 00:20

@ashish1610 bool arr[N] and vector < bool > arv(N) it's different things, arr use N bytes of memory, arv use N / 8 bytes. answered 21 Dec '15, 00:23

Because you have many operations with vector, if you firstly do v[i].reserve for all i = 0..10^7. I've added two optimizations, and your code got AC: 1. First vector < ll > > vector < int >, long long works very long 2. Choose modulo as 2^N, then % mod <> & (mod  1), modulo operations works long too http://pastie.org/10643774 answered 21 Dec '15, 00:33

when will the problems be made public for practice? answered 21 Dec '15, 01:14

When I run this code https://www.codechef.com/viewsolution/8987559 on my machine, codechef compile and run or ideone it is showing memory exhausted so how do I run this code? answered 21 Dec '15, 01:49
Plz someone help me in this. I am unable to run this code. As O(10^8) memory can be allocated but this is O(10^10), though I know bitset takes 1/8 of actual memory but still order becomes O(10^9) still memory exhaustion remains. However this code got accepted so plz help me in this.
(21 Dec '15, 02:19)

The problems are not available for practice :( answered 21 Dec '15, 02:13

Can this question be solved using BitSet Class in Java? answered 21 Dec '15, 03:13

this problem shows how much u know about max size of arrays in programming . we can make 2^30 size bool array in c++ but if we use vector then this size goes up to 2^33, in this question we need 2^31 bool values,, so this problem can be solved by using vector<bool> a(1LL<<31L,false); here is my solution https://www.codechef.com/viewsolution/8990985 answered 21 Dec '15, 11:32
@anonymous_b0y vector < bool > <> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes. Refer @mgch previous comments
(21 Dec '15, 11:44)

I'm getting wrong answer in this code. :( I'm trying hashing with linked list. Would anybody please give a look? answered 04 Feb '16, 10:35

None of the sample solutions are opening..