You are not logged in. Please login at www.codechef.com to post your questions!

×

CHEFQUE - Editorial

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Easy-Medium

PREREQUISITES:

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:

Author
Tester
Editorialist

This question is marked "community wiki".

asked 16 Dec '15, 13:27

pushkarmishra's gravatar image

4★pushkarmishra
1.3k156581
accept rate: 4%

edited 16 Feb '16, 13:40

admin's gravatar image

0★admin ♦♦
19.8k350498541

None of the sample solutions are opening..

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

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.

link

answered 21 Dec '15, 00:15

ceilks's gravatar image

7★ceilks
1.8k9
accept rate: 36%

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

link

answered 21 Dec '15, 00:18

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

I got it accepted using hashtable approach mentioned above same as editorialist's way...

link

answered 21 Dec '15, 00:13

saar2119's gravatar image

5★saar2119
1213
accept rate: 0%

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

link

answered 21 Dec '15, 00:11

saar2119's gravatar image

5★saar2119
1213
accept rate: 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

link

answered 21 Dec '15, 00:08

pranavarora's gravatar image

6★pranavarora
9916
accept rate: 20%

@pranavarora vector < bool > <-> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes.

link

answered 21 Dec '15, 00:09

mgch's gravatar image

6★mgch
4451436
accept rate: 20%

edited 21 Dec '15, 00:21

I got segfault with the same idea as @pranavarora and tle with the same idea as editorialist.

link

answered 21 Dec '15, 00:11

ashish1610's gravatar image

4★ashish1610
4981716
accept rate: 22%

@ashish1610

Because ar.resize() allocate many memory, and stack not enough for it. You should allocate memory globally. http://pastie.org/10643748

link

answered 21 Dec '15, 00:18

mgch's gravatar image

6★mgch
4451436
accept rate: 20%

@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

link

answered 21 Dec '15, 00:20

ashish1610's gravatar image

4★ashish1610
4981716
accept rate: 22%

edited 21 Dec '15, 00:22

@ashish1610 bool arr[N] and vector < bool > arv(N) it's different things, arr use N bytes of memory, arv use N / 8 bytes.

link

answered 21 Dec '15, 00:23

mgch's gravatar image

6★mgch
4451436
accept rate: 20%

@mgch Yeah got that difference. But still no idea why hashing failed.

link

answered 21 Dec '15, 00:25

ashish1610's gravatar image

4★ashish1610
4981716
accept rate: 22%

@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

link

answered 21 Dec '15, 00:33

mgch's gravatar image

6★mgch
4451436
accept rate: 20%

when will the problems be made public for practice?

link

answered 21 Dec '15, 01:14

punjabidon's gravatar image

5★punjabidon
211
accept rate: 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?

link

answered 21 Dec '15, 01:49

deepak2015's gravatar image

5★deepak2015
33
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) deepak20155★

The problems are not available for practice :(

link

answered 21 Dec '15, 02:13

anshkhanna7's gravatar image

4★anshkhanna7
1933927
accept rate: 23%

Can this question be solved using BitSet Class in Java?
If so anyone can tell its implementation?

link

answered 21 Dec '15, 03:13

ankurverma1994's gravatar image

4★ankurverma1994
415114
accept rate: 8%

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

link

answered 21 Dec '15, 11:32

anonymous_b0y's gravatar image

5★anonymous_b0y
40619
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) ankurverma19944★

Each solution link has been broken... :(

link

answered 05 Jan '16, 14:31

mukit_mkbs's gravatar image

3★mukit_mkbs
435
accept rate: 0%

I'm getting wrong answer in this code. :( I'm trying hashing with linked list. Would anybody please give a look?

ideone link

link

answered 04 Feb '16, 10:35

mukit_mkbs's gravatar image

3★mukit_mkbs
435
accept rate: 0%

Got AC ... :)

(07 Feb '16, 12:20) mukit_mkbs3★

"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

link

answered 27 Jun '18, 13:29

souradeep1999's gravatar image

6★souradeep1999
955
accept rate: 3%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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