Not that easy bro. Your case will get halted very quickly. Say we try to check for given x, since a[0] = a[1] in your test case, it will halt in 1 step instead of going till n length.
It’s VERY VERY tricky to generate a case which gives sum as huge factorizable number and EACH divisor goes till length of a given almost ~N distinct a[i]%divisor values (and repeat values like at end of array) , only then we can hit TLE.
But it’s not impossible either until author proves upperbound. It’s not fair to put such ambiguous question in contest.
4*108 operations cannot be completed in 1 second time limit,
because, in 1 second, only 108 operations can be completed, so why the approach mentioned in the editorial is not a TLE? @cherry0697@aryanc403
But, Number of operations is still 2.8*108, which cannot be completed in 1 second, then how @cherry0697 and @aryanc403 are claiming, that these operations are enough to get completed in 1 second?
@cherry0697, Can you tell what was the intuition to sum up the whole array elements and remove the sum of the permutation?
Till this point in the editorial, I was able to understand, but when the summing part came, I was clueless, how to build an intuition like this?
I mean to say, what is the intuition of approaching a problem like this, because it seems somehow un-natural for me to sum up the elements and make equations.
It goes like this that suppose its possible to form permutation from some X, then
for each A[i]
Ai = Qi*X + Ri : Here Ai is element of array, X is chosen divisor and Ri is remainder left. As we said that we supposed that answer is possible then Ri is actually all numbers form 1 to N. So if we sum up each Ai then
sum(A) = sum(R) + (Q1+Q2+Q3+…Qn)X
so : sum(A)-sum(R) = (Q1+Q2+…Qn)X. So we can say that X is basically a factor of sum(A)-sum(R). Moreover sum(R) = N(N+1)/2 as it is sum of 1 upto N so thus we can find all factors of sum(A)-sum(R) and check which one gives the correct answer But still this approach should give TLE as suppose all A[i] are of order 10^7 and suppose I take N = 3 so sum(R) = 6 but sum(A) would be around 310^7 and now the number of factors of a number is given by multiplication of prime factorisation to some power i.e suppose Z = (a^p).(b^q).(c^r) here a,b,c are prime factors of Z, then number of factors of Z = (p+1)(q+1)(r+1). Now this thing could take up large values and thus the above approach provided in editorial must give TLE. I am sorry to say but each time I give a contest on codechef the level goes down each time. Some times even 10^7 wont work in 1s and sometimes even 10^8 will pass in 1s.
if(s==0) then why are we directlty printing yes and n+1, it’s not necessary for ex: 1 1 4 = (1+1+4 =6) also , 1 2 3 =(1+2+3 =6). Can someone make me clear??
Yeah you’re right