CHEFQUE - Editorial

editorial
, , , ,
9

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 Marking large integers - general - CodeChef Discuss 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 CodeChef: Practical coding for everyone

4 Likes
10

@mgch see my first submission. Link : CodeChef: Practical coding for everyone

And this is my solution with hashing : CodeChef: Practical coding for everyone

11

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

12

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

13

@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
14

when will the problems be made public for practice?

15

When I run this code CodeChef: Practical coding for everyone on my machine, codechef compile and run or ideone it is showing memory exhausted so how do I run this code?

16

The problems are not available for practice :frowning:

17

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

18

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

19

Each solution link has been broken… :frowning:

20

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

ideone link

21

"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

2 Likes
22

None of the sample solutions are opening…

23

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.

24

@anonymous_b0y vector < bool > <-> bitset in C++ in terms of memory, vector < bool > v(N) use N / 8 bytes. Refer @mgch previous comments

25

Got AC … :slight_smile:

26

Can anyone please explain how to optimize this.Im getting TLE.

#include<bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	std::cin >> t;
	long long mod=4294967296;
	while(t--)
	{  
	    int q,s1,a,b;
	    cin>>q>>s1>>a>>b;
	    bitset<1000000002> bt;
	   // cout<<"created bitset "<<"\n";
	    long long prev=s1,num=0;
	    long long ans=0;
	    while(q--){
	         num=prev/2;
	         if(prev&1){
	             bt[num]= (bt[num] | 1);
	         }else{
	             bt[num]  = (bt[num] & 0);
	         }
	         prev=(((a*prev)%mod)+(b%mod))%mod;
	    }
	    string s=bt.to_string();
	    for(int i=1000000001;i>0;i--){
	        ans+=(s[i]-'0');
	    }
	    cout<<ans<<"\n";
	    
	    
	    
	}
	return 0;
}
27

While Calculating si=(si-1*a+b)mod2*32.We can get overflow in (si-1*a) as well right.Also not able to understand here how compiler handles overflow.can you please explain it

29

Actually I guess, the author is referring to the situation where we are inserting s/2 and not s. So 31 bits are sufficient. Though si value needs 32 bits, si/2 needs only 31 bits.