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: CodeChef May Challenge 2019 – aleigorithms
15 Likes
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
7 Likes
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 ?
7 Likes
cc editorials are more detailed, but I think the outlines provided are good enough for you to start learning.
2 Likes
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.
3 Likes
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.
1 Like
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: CodeChef: Practical coding for everyone
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.
Can anyone please help how to derive this “(n+1)!-1” for first sum i.e, reduce to one
1 Like
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
1 Like
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.
1 Like
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)
3 Likes
Would really derive this while solving this problem in a contest?
1 Like