May Long 2019 Solutions Sketches


#1

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 :slight_smile: ). 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/


#2

Don’t worry, we,the programming-lovers are already working on creating unofficial editorials and we’ve already created 2-3 unofficial editorials :slight_smile:
Hope the editorialist gets well soon :slight_smile:


#3

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 ?


#4

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


#5

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.


#6

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.


#7

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.


#8

@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


#9

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


#10

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.


#11

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. :frowning:


#12

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


#13

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.


#14

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]


#15

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.


#16

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).


#17

Yup,right. Implement it. Get AC


#18

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


#19

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. :slight_smile:


#20

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)