The last round of Google Kick Start 2020 will take place this Sunday (November 15) at 3:00 UTC and will last 3 hours. Make sure you participate!

See you at g.co/kickstart.

UPD: Thank you for participating! Analysis can be found in the problem view. See you next year!

In problem C , i did ternary search for y coordinate and ternary search for x coordinate for a given y coordinate .

Before coding the solution i verified by random test cases if function is convex but i was not able to prove it . Can some one provide the prove.

UPD : I didn't knew the median solution for both x and y coordinate . Proving why median solution works also proves why ternary search will work.

Sum of convex functions is also convex

I didn't get you.For a given y how to prove that best possible x will be convex function ? And after finding best possible answers say ans for each y , graph of y vs ans will be also convex . How to prove that ? UPD : Understood. Thanks.

Seriously? Ternary search worked? I thought of doing this but couldn't prove it'll work then forgot about it. Damn.

Btw, for y coordinate just converging to median was enough.

How do we do C ?

(Also please let me know that if the y coordinate will be median of all y-values ? and the answer for y-coordinates and x-coordinates are independent ? )

I don't know the prove (i verified using random test cases).First sort the points array.Then you can do ternary search for y coordinate and ternary search for x coordinate for a given y coordinate to find the starting point of final horizontal line. Finally calculate the Manhattan distance.

How to solve problem D for full points ?

Imagine doing Digit Dp in B, because your brain doesn't works. :(

What do you mean? don't tell me that there was an easier way ?

Pl elaborate how it can be done with digit dp .

Check comment by neal.

See this

But where are you compensating leading zeroes?

can someone tell me what wrong with my solution for problem B.

Spoileruse long double

What?? Why double? It didn't work btw

CodeCan you explain the reason why you used long double instead of long long int?

WA on 2nd case so :)

you kidding me bro? why waste my time then!

My screencast (+ explanations) here: https://codeforces.com/blog/entry/84639

For Boring numbers I am not getting the part of leading zeroes compensation. How is that part covered with that code. please quote with an example. I have read may solutions but didn't find how is that part working

If

`digit = 0`

(meaning we are on the first/highest digit of the number) then we don't allow`d = 0`

.I guess I'm doing the same thing in problem C as everyone and as told in Analysis. But this doesn't work. Please help! Thanks

Code...

Can someone please explain how to solve question B(Boring Numbers) using Digit Dp.

I think you can understand from the code.

dp[ind][re]=no. of required nos. of starting from index 'ind' and 're' is to check if the index 'ind' is tight or loose.

Then just use recursive dp to set index 'ind' with desired number and calculate answer by solve(R)-solve(L-1).

In C,for solving for x-axis, why is it wrong to just sort the x coordinates and start mapping them to x[n/2]-n/2, x[n/2]-n/2+1, x[n/2]-n/2+2 and so on... here is my logic, i can't figure out what's wrong

SpoilerIn problem C, the idea (according to neal and official analysis) that we first transform the x-coordinates to x[i] — i and then converge all these values to the same x coordinates using the median of these values. Can someone please help that what is actually going on in here and how do this thing makes all the values to be in a line ?

basically every x in X(array) should come at x+i (i=0,1,2,..,n-1), since it's given in the problem that every point should be adjacent in a horizontal line. Thus we need to sort all x's and then we need to subtract from every x i.e., X[i]-i so that the median x will be such that every x will be arranged in a line. It's very similar to finding a meeting point for all y in Y such that cost(distance moved) will be minimum. This is very standard problem, we sort all y and then find median y = Y[n/2] and then do summation abs(Y[i]-median_y). This will bring every y in Y to median_y. Similarly for X we need to do the same but the change will be every x in X should come at median_x+i (i=0,1,2,3..n-1). Thus, our new cost function will be summation abs(X[i]-(median_x+i)) or abs((X[i]-i)-median_x). I hope this will clear everyone's doubt. (p.s. Hit Up-Vote if you liked).

In C , I know the x[i] -= i approach , but i tried similar

I tried some random cases(and the answer matched with the x[i] -= i approach) but not able to figure out what's wrong with this as it is not passing in the kickstart? Can someone please help?

Full CodeYour code is still wrong!!

ecnerwala video solnhttps://www.youtube.com/watch?v=G47tDfgCTsE&t=872s

Hey Guys , I Just appeared for Google Kickstart Round H , and got almost 2 question's solved and got a rank of 1962 but till now i can't see the certificate of participation in my Kickstart profile!! Can anybody here tell me how and when will i get it ? because i guess till now everyone has got it !

Please help!!

my kickstart username — Yogendra7 ( you can check for verification even if you doubt in Round H leaderboard )

I even mailed at kickstart@google.com but still no reply!

I too am unable to see certificate. This was my first kickstart btw! If you get any solution then please share!

did you got it now ?? .. cz i still had not got it .. it was also my first kickstart

yes, I got it today. You too should probably check now!

yes me too

Interesting problems

In C, everyone is using median = X[n/2], but if n is even then we have 2 medians, why don't we need to take maximum answer considering both value as two medians separately?