May Long editorials will take some days to be published (our dear editorialist is not feeling well), many of you already know I published in my personal blog the solutions outlines (I’m getting a lot of visits ). However probably some people still don’t have the link, so I was asked to create a separate thread sharing the link: https://aleigorithms.wordpress.com/2019/05/06/codechef-may-challenge-2019/

Don’t worry, we,the programming-lovers are already working on creating unofficial editorials and we’ve already created 2-3 unofficial editorials

Hope the editorialist gets well soon

I cannot believe this. editorial should be written by author at same time as problem. Codeforces show editorial immediately after contest.

What is a point of solving if not learning ?

cc editorials are more detailed, but I think the outlines provided are good enough for you to start learning.

I agree, but this editorials are hard to find. Instead of manually checking old contest for editorial every day, I believe it should be automatically revealed after the contest.

Its just the thing that bothers me the most here.

Thank you for the Editorials @alei, I have one question regarding WTBTR problem. I could come up with the same idea as the editorial answer you provided. But i couldnt prove why it works. Could you please provide a proof sketch if possible. Thank you once again for your effort and time.

if there are less than n-1 different x or y coordinates, we can draw lines that goes through every point. Otherwise there will be two points for which no line pass, the best we can do is by drawing a line in the middle.

@alei the solution for BINARY talks of an amortized O(N) approach, but I implemented a similar algorithm with same complexity and still received TLE for 2 cases. Could you please explain that?

Here is my solution: https://www.codechef.com/viewsolution/24264323

Don’t use python. Use C++.You should get AC then!

Not sure about that since the conversion of the input array to binary will take significant time, especially if N is as high as 10^6.

What was the expected time complexity of **PKLVES**?

My O((n+q)*log^2n) is tle. And some people got tle on O((n+q)*logn) soln as well.

Can anyone please help how to derive this “(n+1)!-1” for first sum i.e, reduce to one

Forget that formula… Say for 1 2 3 4

Run a loop, take 1 and 2,that makes 5 ,now combine 5 with 3 in next iteration, after combining,you’ll get, 23,now in next iteration,combine 23 with 4.

There is no formula needed, just run a simple for loop.

Done with this approach only two cases are passed.

I think so i have to first find the max of given n’s and then store their operation in array after that again i will run the loop from 1 to n and display answer as a[n]

Learn to do precomputation.

Its a nice topic.

Calculate and store the answer for n=1 to 1000000 before accepting any testcases and now you can answer each query in O(1),so the time complexity will be O(T+1000000), where ‘T’ is the number of test-cases.

Any method works.I m considering the max among all test cases and then all the queries on O(1) and u r precomputing first only till 1000002 and then all queries in O(1).

Yup,right. Implement it. Get AC

Brother let me know if u get that formula derived “n+1! - 1” i m eagerly curious to know this.

There is no derivation of this formula. It is very easy question, you should not think much about it. Whenever , I’ve to get a formula, I just do observation for n=1,2,3…etc.

Thats it. My friend who solved this problem,she reached the same formula just by observing and not by derivation.

Its simple…

I have two proofs :

# 1)

The output value was…

ans = (1 + 2 + 3 + 4+...n)+( (1*2 + 1*3+ ...) + (2*3 + 2*4 + ... ) + ...) + … + (1*2*3*...*n )

Nc1 + Nc2 + ...+ NcN terms…

Now see expansion of

(a+1)*( b+1) = 1 + a +b + a*b

=>(a+1)*( b+1) - 1 = a +b + a*b

(a+1)*( b+1)*(c+1) =1+ a +b + c + a*b + b*c + a*c + a*b*c

=>(a+1)*( b+1)*(c+1) -1 = a +b + c + a*b + b*c + a*c + a*b*c

hence similarly,

ans = ( ( (1+1)*(2+1)*(3+1)*(4+1)*...*(n+1) ) -1 ) = (n+1)! -1

# 2)

for n=1 => ans=f(n)=f(1)=1

now, f(2) = f(1) + 2 + f(1)*2 = 1+2+2

similarly, f(n) = f(n-1) + n + f(n-1)*n

putting f(n) = (n+1)! -1

f(1) = 1

f(n-1) + n + f(n-1)*n = (n!-1) + n + (n!-1)*n = n! + n!*n +n -n -1 = (n+1)! -1 = f(n)