kostka's blog

By kostka, 2 months ago, In English

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!

 
 
 
 
  • Vote: I like it
  • +42
  • Vote: I do not like it

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    Sum of convex functions is also convex

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it -8 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem D for full points ?

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    use long double

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        2 months ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        Code
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

Spoiler
»
2 months ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

In 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 ?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

sort(x.begin(), x.end());
sort(y.begin(), y.end());
ll mx = x[(n-1)/2] - floor((n-1)/2);
ll my = y[(n-1)/2];
ll ans = 0;
for(int i = 0; i< n; i++){
	ans += abs(my - y[i]);
	ans += abs(mx - x[i] + i);
}

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 Code
»
2 months ago, # |
  Vote: I like it -7 Vote: I do not like it

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!

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Interesting problems

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?