CHEFQUE - Editorial

@ashish1610

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

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

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

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

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

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

@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

when will the problems be made public for practice?

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?

The problems are not available for practice :frowning:

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

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

Each solution link has been broken… :frowning:

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

ideone link

"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

None of the sample solutions are opening…

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.

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

Got AC … :slight_smile:

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;
}

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