O(n) solution gives TLE on problem with 2sec time limit — CPP +14

Правка en1, от CopyrightC, 2024-07-26 12:56:19

Hello everyone this is my first time posting, so please bare with me :P

So I was solving this problem and came up with a solution.

Idea

say for example x = 7. if ai is of the form 7d + 2 then aj needs to be of the form 7q + '5'. Basically the remainders of ai % x and aj % x needs to add up to x for the sum to be divisible by x. also for ai — aj to be divisible by y, ai % y must be same as aj % y.

Initialize a 2d vector(rems) with all values set to 0.

Loop through the input vector and calculate input%y(remy) and input%x(remx) increment rems[remy][remx].

calculate all possibilities by multiplying rems[remy][remx] * rems[remx][x-remx] at every iteration and add that to ans variable. also subtract the result of product of last time when we iterated through the same rems[remy][remx].

if say x = 8 and remx = 4; the we have to select combinations of 2 elements so we do Nc2 for such values.

    long long n,x,y;
    cin >> n >> x >> y;
    vector<vector<long long>> v(n);
    for(int i = 1;i < n; ++i) cin >> v[i];

    vector<vector<long long>> rems(y, vector<long long> (x, 0)); //init a 2d array
    ll ans = 0;
    ll remx,remy;
    ll curr,curr2;

    for(int i = 0; i < n;++i){
    	remy = v[i]%y;
    	remx = v[i]%x;
    	rems[remy][remx]++;
    	curr = rems[remy][remx];	
    	if(remx && remx!= (x- remx)){
    		curr2 = rems[remy][x-remx];
	    	ans += (curr * curr2) - ((curr - 1) * (curr2)); // on simplification = curr2
    	}
    	else{
    		ans+= (curr * (curr - 1))/2 - ((curr - 1) * (curr -2)/2); //Nc2 - (N-1)C2
    	}
    }

    cout << ans << '\n';	

I am unable to identify where am I going wrong? Exactly where is it taking so long? Also I don't wanna spoil the solution to me by reading tutorial.

If I'm unclear in any part of solution please do let me know. I'll try my best to explain again. Thanks!

Теги tle, c++, dp, o(n)

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский CopyrightC 2024-07-26 13:00:44 0 (published)
en2 Английский CopyrightC 2024-07-26 12:59:40 45 (saved to drafts)
en1 Английский CopyrightC 2024-07-26 12:56:19 2071 Initial revision (published)