hello_its_me's blog

CSES "Sliding Window Or" getting TLE
By hello_its_me, 12 months ago, In English

Problem : Sliding Window Or

I am getting a TLE in this problem. This is my code: 

// HELPPP...
#include<bits/stdc++.h>
using namespace std;
vector<long long> v, ors;
int main(){
 int n , k; cin >> n >> k;
 int x , a , b , c; cin >> x >> a >> b >> c;
 long long p = x;
 for(long long i  = 1; i <= n; ++i){
    v.push_back(p);
    p = ( a * p + b ) % c;
 }
 long long ori = 0;
 vector<int> bits(32);
 for(int i= 0 ; i < k; ++i){
  ori |= v[i];
  for(int j = 0 ; j < 32; ++j ){
   if(v[i]&(1LL<<j))bits[j]++;
  }
}
 ors.push_back(ori);
 for(int i = k; i < n; ++i){
  ori |= v[i];
  for(int j = 0 ; j < 32; ++j){
   if(v[i]&(1LL<<j))
      bits[j]++;
  }
  for(int j = 0 ; j < 32; ++j){
   if(v[i-k]&(1LL<<j)){
      bits[j]--;
      if(!bits[j]) ori -= (1LL<<j);
   }
  } 
  ors.push_back(ori);
 }
 long long ans = 0;
 for(auto i : ors)
     ans ^= i;
 cout << ans << endl;
}

How can i avoid the inner 32 loops in for loop ? or is there any other way to do it ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
12 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

32*1e7 operations can only be done if you don't access memory. Calculate element, compute bits time to live, and don't save anything else. Without any tricks it runs in 0.3-0.4 CSES seconds, with a little trickery my solution runs in 0.25 sec (currently #3 in statistics).

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it +1 Vote: I do not like it

you can refer this solution prefix suffix approach !!

→ Reply
»
12 months ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

There exists a linear solution using monotonic deque (or whatever it is called). The structure allows maintaining any associative operation with an identity element — i.e., any monoid operation on the window.

monotonic deque
→ Reply
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    This is only the interface of a queue though. To make it a deque, when popping front and front is empty you move half of the elements from back to front instead, same for popping back. This gives armotized $$$O(1)$$$ per operation.

    Read more here [Tutorial] Minimum Deque.

    → Reply
  • »
    »
    12 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Almost entire sliding window section can be solved using this same code with this, but what's the point, isn't it more fun to think of different solution?

    → Reply