×

# CHEFQUE - Editorial

Author: Misha Chorniy
Tester: Jingbo Shang
Editorialist: Pushkar Mishra

Easy-Medium

Hash-Table

# PROBLEM:

Given two types of queries:
1. Add the number to the set of numbers being maintained. 2. Remove the given number from the set if it exists in it.

The numbers to be inserted/deleted are generated according to the following scheme:
$S$ = (a*$S_{i-1}$ + b) mod $2^{32}$,
where $a$ and $b$ are integers.

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 pre-written 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 Hash-Table 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".

1.3k156581
accept rate: 4%

19.8k350498541

None of the sample solutions are opening..

(21 Dec '15, 00:52) 0★

 4 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 7★ceilks 1.8k●9 accept rate: 36%
 4 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/marking-large-integers 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 6★likecs 3.7k●24●81 accept rate: 9%
 2 I got it accepted using hashtable approach mentioned above same as editorialist's way... answered 21 Dec '15, 00:13 5★saar2119 121●3 accept rate: 0%
 1 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 5★saar2119 121●3 accept rate: 0%
 0 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 99●1●6 accept rate: 20%
 0 @pranavarora vector < bool > <-> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes. answered 21 Dec '15, 00:09 6★mgch 445●14●36 accept rate: 20%
 0 I got segfault with the same idea as @pranavarora and tle with the same idea as editorialist. answered 21 Dec '15, 00:11 498●1●7●16 accept rate: 22%
 0 @ashish1610 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 6★mgch 445●14●36 accept rate: 20%
 0 @mgch see my first submission. Link : https://www.codechef.com/viewsolution/8988268 And this is my solution with hashing : https://www.codechef.com/viewsolution/8988506 answered 21 Dec '15, 00:20 498●1●7●16 accept rate: 22%
 0 @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 6★mgch 445●14●36 accept rate: 20%
 0 @mgch Yeah got that difference. But still no idea why hashing failed. answered 21 Dec '15, 00:25 498●1●7●16 accept rate: 22%
 0 @ashish1610 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 6★mgch 445●14●36 accept rate: 20%
 0 when will the problems be made public for practice? answered 21 Dec '15, 01:14 21●1 accept rate: 0%
 0 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 3●3 accept rate: 0% 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)
 0 The problems are not available for practice :( answered 21 Dec '15, 02:13 193●3●9●27 accept rate: 23%
 0 Can this question be solved using BitSet Class in Java? If so anyone can tell its implementation? answered 21 Dec '15, 03:13 415●1●14 accept rate: 8%
 0 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 a(1LL<<31L,false); here is my solution https://www.codechef.com/viewsolution/8990985 answered 21 Dec '15, 11:32 406●1●9 accept rate: 14% @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)
 0 Each solution link has been broken... :( answered 05 Jan '16, 14:31 43●5 accept rate: 0%
 0 I'm getting wrong answer in this code. :( I'm trying hashing with linked list. Would anybody please give a look? ideone link answered 04 Feb '16, 10:35 43●5 accept rate: 0% Got AC ... :) (07 Feb '16, 12:20)
 0 "We know they lie between 0 and 2^32−1, i.e., they can be represented by 31 bits." how its 31 bits.....i think it can be a 32 bits integer,because after mod we can get max value of 2^32-1,which is a 32 bits integer. pliz help @mgch answered 27 Jun '18, 13:29 95●5 accept rate: 3%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,855
×1,723
×344
×105
×39

question asked: 16 Dec '15, 13:27

question was seen: 4,649 times

last updated: 27 Jun '18, 13:29