SQRSUBMA - Editorial

Why sz should be divisible X, which is sum of elements?
Why can’t we have for example 3*3 submatrix which sums to 17?

I liked this problem and spend all time on this… here is what i ended up on.
here is my approach … i noticed that sum of any square submatrix is going to be like following …
lets take an example of Array = 1 2 3
now matrix would be …

2 3 4
3 4 5
4 5 6

i am not good in math , but next thing i found out that any submatrix is made of xi, yi, xii, yii as i being coordinates of starting cell and ii being coordinates of ending cell. if take an example cell (1, 2) to (2, 3) it is made of ranges (1, 2) and (2, 3) and sum of this sub array can be calculated as sum of all these elements (1 + 2 + 2 + 3) * 2 as these all will occur twice in the sum … (because our matrice is made of such sums…). i just used this …
i searched for all options there were to make possible square submatrices… and then found this cool optimisation that x should be divisible by the size of my square submatrix…
and next thing i found out i just need to to find subsets of given matrix and look if sum of any two subsets of same size multiplied with size of the sub matrice yeilds my X or not… (only same sized sub-arrays would create a square sub matrices).
i am a new bie, couldn’t think much to implement it all efficently and ended up using multisets to count possible sum … here is my impletentetion it only got one only one AC. I am open to suggestion thankyou.

in my code i used double loop, i loop specifies the the size of sub array, and j specifies the staring point. multiset records all the sums in a given subset size (which is being defined by i). and then just calculating, there is a expection in all this that subarrays that start on the main diagonal would be read twice in this method, so i am decrementing my count on this exception.

1 Like

I’m taking about frequency array. You’d spend O(X) time for each sz. For T = 100 and X = 10^6, that might cause trouble.

Map we can clear all, though map might have additional overhead over frequency array.

sz divides X. sz must be factor of X.

1 Like

Referring this OEIS sequence, it won’t go over 240

2 Likes

Can you please explain how did you estimated the size of the frequency array ?As maximum size might have to be something like 10^10 ?

You only care about subarray sums up to X (since values are non-negative)

@swapnil159 I was also approaching the problem in the same way.Looks like the map was the only reason I was getting TLE. Thanks for the information.

1 Like

SImple:

By the above given maths , Finally you will get X = sz * (sum of two subarrays of size sz)
So sz divides X. Find all the divisors of X and store them. For every S = X/sz , find the sum of two subarrays whose sum is S using sliding window method.

@taran_1407 The editorial link on problem page is wrong, please fix it.

I am getting different results whle submitting my solution in different C++ standards. Here is my code

This is the result with C++ 14

This is the result with C++ 17

Please look into this @admins @taran_1407 . Also if anyone can point out the mistake, I’ll be grateful.

My code’s time complexity is also O( sqrt(X)+d(X)∗N) then why TLE
can somebody tell me what is wrong
my code Link

Thanks

Can somebody please help I am getting Runtime Error Submission Link
Edit - Found the Mistake

Can someone plz explain why is time limit 3 sec in this problem??

1 Like

Its already very tight bro why do you want to reduce it even further :sweat_smile: ?

https://www.codechef.com/viewsolution/34840483
can anyone tell the mistake in my code/logic please
i would be very thankfull

can u please tell why we are considering freq[z-s] in answer and not simple freq[z] in the editorial?

Bij= Ai+Aij
if we take take submatrix of length 3
then ,
sum = B00+B01+…+B22
see if you open up each Bij as Ai+Aj
then all Ai & Aj in the sum will be multiple of 3(which is also the side length of submatrix)
so 3 is a factor of sum
and we want those submatrix whose ,sum = X
hence 3 should also be the factor of X.

In the above e.g.
considering this cell (1,1) & (3,3) we get side length = 3
sum of subarray with these two cell at edge = (1+1+3+3) * 3 = 24
but in actual the sum is 2+3+4+3+4+5+4+5+6 =36 , hence it may contradict

please guide me if i got the above e.g. in wrong aspect(probably my misconception)!

I applied the approach mentioned in the editorial post contest ,
still getting that 3 second TLE
can anyone find any unecessary additional run in my code to reduce time
https://www.codechef.com/viewsolution/34857515
(P.S. - comment are mentioned sidewise to clarify the all steps in code)