### kostka's blog

By kostka, 2 months ago, 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!  Comments (38)
 » 2 months ago, # | ← Rev. 2 →   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
•  » » » 2 months ago, # ^ | ← Rev. 2 →   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 →   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 →   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.
•  » » »
•  » » » » But where are you compensating leading zeroes?
 » can someone tell me what wrong with my solution for problem B. Spoiler#include using namespace std; typedef long long ll; ll a_even = {4,4,3,3,2,2,1,1,0,0}; //a_even[i] represents no.of even nums after i (not including) ll a_odd = {5,4,4,3,3,2,2,1,1,0}; //a_odd[i] denotes no.of odd integers after i (not including i) bool extraa(ll num){ //this functions just checks if given 'l' is boring or not string s = to_string(num); int flag = 1; for(int i=0;s[i];++i){ if(i&1){ if((s[i]-'0')&1)flag=0; } else { if((s[i]-'0')%2==0)flag=0; } if(flag==0)return false; } return true; } int main(){ int t; cin>>t; for(int test = 1;test<=t;++test){ cout<<"Case #"<>l>>r; ll ans = 0; string s1 = to_string(l); string s2 = to_string(r); ll count1 = s1.length(); ll count2 = s2.length(); for(ll i=count1+1;i=0;--i){ if(i&1){ x = x + a_even[s1[i]-'0']*pow(5,poww); } else x = x + a_odd[s1[i]-'0']*pow(5,poww); poww++; } poww = 0; for(int i=s2.length()-1;i>=0;--i){ if(i&1){ y = y + a_even[s2[i]-'0']*pow(5,poww); } else y = y + a_odd[s2[i]-'0']*pow(5,poww); poww++; } if(extraa(l)) x++; //just checking if 'l' is boring or not if(count1!=count2){ y = pow(5,count2) - y; ans = ans + x + y; } else { ans = ans + x - y; } cout<
•  » » 2 months ago, # ^ | ← Rev. 2 →   use long double
•  » » » What?? Why double? It didn't work btw
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   Code#define ll long long int #define ld long double vector odd = {'1', '3', '5', '7', '9'}; vector even = {'0', '2', '4', '6', '8'}; ld f(ll n) { ld ans = 0; string s = to_string(n); for(int i = 0; i < s.size(); i++) { ll cnt = 0; char last = '-'; if(!(i & 1)) { for(char c : odd) { if(c <= s[i]) { last = c; cnt++; } else break; } } else { for(char c : even) { if(c <= s[i]) { last = c; cnt++; } else break; } } if(cnt == 0) { break; } else if(last < s[i]) { ld cur = cnt; for(int j = i + 1; j < s.size(); j++) { cur *= 5; } ans += cur; break; } else { ld cur = (cnt - 1); for(int j = i + 1; j < s.size(); j++) { cur *= 5; } ans += cur; if(i + 1 == s.size()) { ans++; } } } return ans; } ld upto(ld x) { ld ans = 0; ld five = 5; ld ten = 10; while(ten - 1 < x) { ans += five; ten *= 10; five *= 5; } ans += f(x); return ans; } void solve(int &T) { ld l, r; cin >> l >> r; ll ans = (ll)(upto(r) - upto(l - 1)); cout << ans << endl; } 
•  » » » » » Can 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...  public static void main(String[] args) throws IOException { // TODO Auto-generated method stub int t = scn.nextInt(); int x = 1; while (t > 0) { int n = scn.nextInt(); Point[] arr = new Point[n]; for (int i = 0; i < n; ++i) { arr[i] = new Point(scn.nextInt(), scn.nextInt(), i); } System.out.println("Case #" + x + ": " + solve(n, arr)); t--; x++; } } public static long solve(int n, Point[] arr) { Arrays.sort(arr, new yCom()); int yMed = arr[n / 2].y; long ans = 0; Arrays.sort(arr, new xCom()); int xMed = arr[n / 2].x; int i=n/2; while(i>=0) { int x=arr[i].x; int y=arr[i].y; ans+=Math.abs(yMed-y); ans+=Math.abs(xMed-x); xMed--; i--; } xMed=arr[n/2].x+1; i=n/2+1; while(i { @Override public int compare(Point arg0, Point arg1) { // TODO Auto-generated method stub return arg0.x - arg1.x; } } public static class yCom implements Comparator { @Override public int compare(Point arg0, Point arg1) { // TODO Auto-generated method stub return arg0.y - arg1.y; } } public static class Point { int x; int y; int id; Point(int x, int y, int id) { this.x = x; this.y = y; this.id = id; } } static Reader scn = new Reader(); static OutputStream out = new BufferedOutputStream(System.out);  Your code here... 
 » 2 months ago, # | ← Rev. 2 →   Can someone please explain how to solve question B(Boring Numbers) using Digit Dp.
•  » » 2 months ago, # ^ | ← Rev. 2 →   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 →   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 Spoilervoid solve () { ll n; cin >> n; vector x(n),y(n); for (int i = 0;i < n;++i) { cin >> x[i] >> y[i]; } sort(all(x)); sort(all(y)); ll finalY = y[n/2]; ll startX = x[n/2]-n/2; ll ans = 0; for (int i = 0;i < n;++i) { ans += abs(x[i]-startX)+abs(y[i]-finalY); ++startX; } cout << ans << '\n'; } 
 » 2 months ago, # | ← Rev. 2 →   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 ?
•  » » 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 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#include using namespace std; #define ll long long #define MOD 1000000007 #define endl '\n' #define in(x, n) for(int e=0; e> y; x.pb(y);} #define print(x) for(auto it:x)cout << it<< ' '; cout << endl; #define vi vector #define vvi vector #define ii pair #define pll pair #define pb push_back #define F first #define S second int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t; cin >> t; for (int case_num = 1; case_num <= t; case_num ++) { int n; cin >> n; vi x(n), y(n); for(int i = 0; i < n; i++){ cin >> x[i] >> y[i]; } sort(x.begin(), x.end()); // for(int i = 0; i < n; i++){ // x[i] -= i; // } // sort(x.begin(), x.end()); sort(y.begin(), y.end()); ll mx = x[(n-1)/2] - floor((n-1)/2); // ll mx = x[(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 - (n-1)/2 + i - x[i]); ans += abs(mx - x[i] + i); } cout << "Case #" << case_num << ": " << ans << '\n'; } return 0; }