The pains of an average programmer

The last time I attempted a programming contest was on 28th Feb when I was trying to be a purple on codeforces. After a long break I thought of attempting codechef cookoff yesterday and I did.

The first problem was a cake walk. Given co-ordinates of triangles the task is to find how many of them were right-angled.

Based on popularity I chose to solve DIVQUERY next. The task is to find how many numbers in an array (size :10**5) between 2 the given indices (Ex: all values in the array between 2nd and 10th element ) are divisible by a given number K. There can be upto 10**5 such test cases. This looked difficult and almost impossible to solve.

After going through the constraints I observed that the values in the array are less than 10**5. After some thought I understood that this could be solved using some kullu thelivithetalu (street smartness). I estimated that the number of factors any number less than 10**5 can have is less than 100. 2*3*5*7*11*13*17 > 10**5 (miscalculation-1). This means that no number less than 10**5 can have more than 64 (2**(7-1)) factors.

For each number in the array I need to store the index for all its factors. For a given number this store can give me indices of all its multiples in the array. As each number can have a maximum of 64 factors the total space this store requires would be 64* 10**5 (<10**7) which is perfectly fine.

What data-structure to use. I have 2 options

  • An array of vectors: Where the ith vector gives the indices of multiples of ith value in the input array. But initializing 10**5 vectors might be very slow and I never liked vectors and could not convince myself about their amortized constant time inserts. Also as it is not possible to have a good estimate of expected size of each vector I cannot use the reserve space option. Option ruled out (miscalculation-2)
  • Map<long,int> : Where the key is actually a pair .
    num = key%1000000
    index  = key/1000000
    

    So the touple (num,index) is the key and the value is the number of multiples of num in the array upto indexth value in the array. Expected number of inserts is 10**7 and expected time is 2* 10**8 .This is perfectly fine. Map it is

Implementation comes next. At first I need to get all the keys that of the map and store them somewhere. Once this is done the required map can be built by iterating over the keys in ascending order.

Attempt-1:
Store all the keys in the map with some dummy value and give them the correct values during the iteration. Java does not allow modifying a data structure while iterating over it. C++ might be doing the same. So store all the keys in a set and then build the map by iterating over the set.

for (long i = 0; i < n; i += 1){
   scanf("%lld",&x);
   for (long j = 0; j < cnt[x]; j += 1){
      long num = factors[x][j];
      st.insert(i + 1000000l*num);
   }
}
long presNum=0,presValue=0;
set::iterator it;
for(it = st.begin(); it != st.end() ; it++){
   long num = (*it)/1000000l,ind=(*it)%1000000l;
   if(num==presNum){
      presValue++;
   }
   else {
      used_cnt[presNum]=presValue;
      presNum=num;
      presValue=1;
   }
   mp[*it]=presValue;
   used[num][presValue-1]=ind;
}
used_cnt[presNum]=presValue;
 
for (long i_ = 0; i_ < tc; i_ += 1){
   long l,r,k; scanf("%lld %lld %lld",&l,&r,&k);
   l-=2;r--;
   long l1=-1,r1=-1;
 
   for (long i = 0; i < used_cnt[k]; i += 1){       
      long i1 = used[k][i];       
      if(l>=i1 && r>=i1) {
         l1=i1; r1=i1;
      }
      else if(r>=i1) r1=i1;
      else break;
   }
 
   long ans =0;
   if(r1>=0) ans = mp[r1+1000000l*k];
   if(l1>=0) ans = ans-mp[l1+1000000l*k];
   printf("%lld\n",ans);
}

Result: TLE

Attempt-2:
Java is very strict. C++ is very loose and may be it does not do the locking business while iterating. After some digging I discovered that this is the case. So the set is not required.


for (long i = 0; i < n; i += 1){
   scanf("%lld",x);
   for (long j = 0; j &lt; cnt[x]; j += 1){
      long num = factors[x][j];
      mp[i + 1000000l*num]=1;
   }
}

long presNum=0,presValue=0;
map<long,long>::iterator it;

for(it = mp.begin(); it != mp.end() ; it++){
   long num = (it->val1)/1000000l,ind=(it->val1)%1000000l;
   if(num==presNum){
      presValue++;
   }
   else {
      used_cnt[presNum]=presValue;
      presNum=num;
      presValue=1;
   }
   mp[it->val1]=presValue;
   used[num][presValue-1]=ind;
}

Result: TLE

Attempt-3:
May be I’m loosing very narrowly and some minor modifications might result in AC. So I better modify the key to (num<<20) + ind. Getting back num, index from key will be key>>20, key&((1<<20) -1). After lot of pain with bracketting I ended with the code is the best I can do.


for (long i = 0; i < n; i += 1){
   ni(x);
   for (long j = 0; j < cnt[x]; j += 1){
      num = factors[x][j];
      //cout<<num<<"-"<<(i + (num<<20))<<" ";
      mp[i + (num<<20)]=1;
   }

}

long presNum=0,presValue=0,ind,r1;
map<long,long>::iterator it;
long __num = ((1<<20)-1);
for(it = mp.begin(); it != mp.end() ; it++){
   num = (it->val1)>>20,ind= ((it->val1)& __num) ;
   if(num==presNum){
      presValue++;
   }
   else {
      used_cnt[presNum]=presValue;
      presNum=num;
      presValue=1;
   }
   it->val2=presValue;
   used[num][presValue-1]=ind;
}
used_cnt[presNum]=presValue;

Result: TLE

Attempt-4:
What if all the test cases are 1,10**5,1 ? My solution would blow off. Use binary search. I always prefer not to use the upper_bound and lower_bound functions. But now I have to.

l1 = *(upper_bound(used[k],used[k]+used_cnt[k],l)-1);
r1 = *(upper_bound(used[k],used[k]+used_cnt[k],r)-1);

Result: TLE again. Screw this . Its not gonna happen and there is not much I can do as the other questions have to be coded with lot of care and I will definitely mess up as there is less than 20 mins to go . Some fb. Sudden thought : Why not try the vector idea? Nothing to lose.

Attempt-5:
Code code code. I implemented the vetor idea.

for (long i = 0; i < n; i += 1){
   ni(x);
   for (long j = 0; j &lt; cnt[x]; j += 1){
      v[factors[x][j]].pb(i);
   }
}
long l,r,k,l1,r1;
while(tc--){
   scanf("%lld %lld %lld",&l,&r,&k);
   l1=(upper_bound(v[k].begin(),v[k].end(),l-2) -v[k].begin());
   r1=(upper_bound(v[k].begin(),v[k].end(),r-1)-v[k].begin());

   printf("%lld\n",r1-l1);
}

Result: Wtf? Where is the submit button? Contest over! The question is added to practice. Submitted my solution and got a WA. I thought I messed up some where.

I opened the editorial and after a quick glance I saw the number 128. Then I realised my miscalculation-1 and then modified the declaration of factors to factors[100001][150] (from factors[100001][100]) and the result is an AC.

Advertisements

2 thoughts on “The pains of an average programmer

  1. Nice Solution. My approach was slightly different. I generated the factors of each number in the array by prime factorization. It seems to work slower than your approach though.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s