Unexpected TLE on CF "The Wu"

#1

Hi, I am doing the problem “The Wu” (https://codeforces.com/contest/1017/problem/D) from the “Intro to Bitwise Operators” module of USACO Gold.

Basically, my solution times out, but it’s the exact same as one of the user solutions (from the USACO guide) that didn’t. My solution, which times out, is as follows:

#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#include <string>
#include <cstdio>
#include <cstring>
#include <algorithm>  
#include <math.h>
#include <numeric>
using namespace std;
using ll=long long;

int main() {
  int n, m, q;
  cin>>n>>m>>q;
  int w[n], up=1<<n, copies[1<<n];
  for (int i=n-1; i>=0; i--) cin>>w[i];
  for (int i=0; i<up; i++) copies[i]=0;
  for (int i=0; i<m; i++){
    string bin;
    cin>>bin;
    copies[stoi(bin, 0, 2)]++;
  }
  int c[up][101], d[up][101];
  for (int t=0; t<up; t++){
    for (int i=0; i<=100; i++) c[t][i]=0;
    for (int x=0; x<up; x++){
      int v=0, a=t^x;
      int b=a^((1<<n)-1);
      for (int i=0; i<n && v<=100; i++){
        if (b&(1<<i)) v+=w[i];
      }
      if (v<=100) c[t][v]+=copies[x];
    }
    d[t][0]=c[t][0];
    for (int i=1; i<=100; i++) d[t][i]=d[t][i-1]+c[t][i];
  }
  for (int z=0; z<q; z++){
    string bin; //t=stoi(bin)
    int k;
    cin>>bin>>k;
    cout<<d[stoi(bin, 0, 2)][k]<<"\n";
  }
}

However, the following code, which is literally the exact same as mine, doesn’t time out:

#include <bits/stdc++.h>
using namespace std;
string s;
int n, m, q, k, x, w[12], cnt[4099]{0}, ans[4099][101]{0};
int32_t main()
{
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 0; i < n; i++) cin >> w[i];
	for(int i = 0; i < m; i++){
		cin >> s; cnt[stoi(s, nullptr, 2)]++; // Store count of duplicates
	}
	for(int i = 0; i < (1<<n); i++){
		for(int j = 0; j < (1<<n); j++){
			int sum = 0, x = i^j; int y = x^((1<<n)-1); // y = Wu binary representation
			for(int k = 0; k < n and sum<=100; k++)
				if(y&(1<<k)) sum+=w[n-k-1]; // Wu value
			if(sum<=100) ans[i][sum]+=cnt[j]; // Difference array
		}
		for(int j = 0; j < 100; j++) ans[i][j+1]+=ans[i][j]; // Prefix sums
	}
	while(q--)
	{
		int k; cin >> s >> k;
		int x = stoi(s, nullptr, 2);
		cout << ans[x][k] << '\n'; // O(1)
	}
}

Could someone please help me debug my code/find out why it’s timing out, when the other solution doesn’t?

#2

Ah, this problem.
I see you haven’t unsynced your IO.
Try that (It’s stupid, I know).

#3

I tried it, still times out unfortunately

#4

From what I can see you use some extra loops to reset your arrays. The user solution you gave doesn’t seem to do such a thing.

Also, FWIW, here’s my submission which doesn’t use arrays.

#5

Wait are you talking about the loop:

for (int i=0; i<=100; i++) c[t][i]=0

? Because that is basically the only loop that my code has but the working code doesn’t. However the combined runtime for this loop would be O(2^n*100) which should barely make a dent on the runtime. Or am I mistaken and you are referring to a different one?

#6

which should barely make a dent on the runtime

IDK, when the difference between AC and TLE can be something as minor as unsyncing IO, every operation starts to matter.