Блог пользователя kostka

Автор kostka, 3 года назад, По-английски

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!

  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    Sum of convex functions is also convex

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

      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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem D for full points ?

»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

Spoiler
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    use long double

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        Code
»
3 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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
»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

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
»
3 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

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 ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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