### kostka's blog

By kostka, 8 days ago,

Round G of Google Kick Start 2020 will start this Sunday (October 18) at 12:00 UTC and will last 3 hours.

See you at g.co/kickstart.

• +70

 » 8 days ago, # |   0 Anyone else facing long queues?
•  » » 8 days ago, # ^ | ← Rev. 2 →   +4 Yes, I too faced long Queues especially in Question 3.
 » 8 days ago, # |   0 How to solve C
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 sort the array and append the whole array with value a[i] + n. For each window w, find the moves required to make all values equal to median which is basically Sliding Cost on CSES. You can see discussion here Code
•  » » » 8 days ago, # ^ |   0 Can you share your submission?
•  » » » » 8 days ago, # ^ |   0 You can view my submissions here.
•  » » » » » 8 days ago, # ^ |   0 thanks. now it's clear.
•  » » » » » 6 days ago, # ^ |   0 Can you explain the idea behind these lines of code in your solution? d=d+abs(m-a[i])-abs(old_m-a[i-k]); if(k%2==0) d-=(m-old_m);
•  » » 8 days ago, # ^ | ← Rev. 2 →   +5 Ternary search on the target node worked for me.
•  » » » 8 days ago, # ^ |   0 I don't understand, can you explain?
•  » » » » 8 days ago, # ^ |   +6 Sure. If the problem is with ternary search then look at https://www.geeksforgeeks.org/ternary-search/The random heuristic that I use is repeating the search several times on different intervals and choose the best one. This is the solution https://pastebin.pl/view/bfb7d20d
•  » » » » » 8 days ago, # ^ |   +4 Why do you need to use heuristic with ternary search ?
•  » » » » » » 40 hours ago, # ^ |   0 heurestic is just a way of thinking,approach etc. Its not a cp topic. A general thing
•  » » 7 days ago, # ^ |   +1 I used binary search in the following manner Let the array be 1 2 3 4 5 6 7 8 9 10 11 12 13 14 then calculate prefix sums, for each i [1,14] we calculate two index, index1 = the point where each element before will be wrapped around using Subtraction, index2 = from where it would be wrapped around from addition eg i=9 index1=2, so all elements before this will be wrapped using Subtraction. And from 2-> 9 all element just add. similarly index2. index1 and 2 can be calculated using binary search, and then you can use prefix sums and array values to get the answer
•  » » » 3 days ago, # ^ |   0 scoobyDoobyDoo Can you please send me a link for your solution? It would be very helpful. Thanks.
 » 8 days ago, # |   +1 My main interests are problem C (Combination Lock) and D (Merge Cards). Did anybody solve C without using ternary search on the final target? I am sure there is a solution avoiding ternary/binary searches. In problem D after some standard thinking it's fairly possible to come up with an n^2 approach. Is it possible to solve the problem faster maybe O(nlogn) or even O(n)? P.S. Since the main goal of Kickstart round is to contribute to recruiting at Google, what do you think how much is the ranking threshold this time to be contacted by Google requiter? What do you think about that magic number?
•  » » 8 days ago, # ^ | ← Rev. 2 →   +2 Does ternary search work in problem C ? How is the function unimodal ? I kept on getting WA using ternary search.
•  » » » 8 days ago, # ^ |   0 I also didn't manage to prove the unimodality. That was just an assumption + some random heuristic that worked.
•  » » » » 8 days ago, # ^ |   0 Can you please see why my ternary search solution gave WA ? Spoiler#include using namespace std; //Utility functions #define pb push_back #define sz size() #define fi first #define se second #define all(c) (c).begin(),(c).end() //Constants #define EPS 1e-6 #define INF 2e9 //Printing #define coutRV(a,L,R) FE(i,L,R) cout<=a; i--) #define FA(x,cont) for(auto& x : cont) //For debug void __print(int x) {cerr << x;} void __print(long x) {cerr << x;} void __print(long long x) {cerr << x;} void __print(unsigned x) {cerr << x;} void __print(unsigned long x) {cerr << x;} void __print(unsigned long long x) {cerr << x;} void __print(float x) {cerr << x;} void __print(double x) {cerr << x;} void __print(long double x) {cerr << x;} void __print(char x) {cerr << '\'' << x << '\'';} void __print(const char *x) {cerr << '\"' << x << '\"';} void __print(const string &x) {cerr << '\"' << x << '\"';} void __print(bool x) {cerr << (x ? "true" : "false");} template void __print(const pair &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';} template void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";} template void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);} #ifndef ONLINE_JUDGE #define debug(x...) cerr << "[" << #x << "] = ["; _print(x) #else #define debug(x...) #endif //Definitions #define ll long long #define ld long double #define vi vector #define vll vector #define vd vector #define vvi vector > //For UnGraph #define vvpi vector > //For DirGraph #define vviwv(vecname, N, M, value) vector > vecname(N, vector (M, value)) //For DP #define vvlwv(vecname, N, M, value) vector > vecname(N, vector (M, value)) //For DP #define pii pair #define fastIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); //Input #define cini(i) int i; cin>>i; #define cini2(i,j) int i,j; cin>>i>>j; #define cini3(i,j,k) int i,j,k; cin>>i>>j>>k; #define cini4(i,j,k,l) int i,j,k,l; cin>>i>>j>>k>>l; #define cinll(l) ll l; cin>>l; #define cind(d) double d; cin>>d; #define cins(s) string s; cin>>s; s = "#"+s; #define cinv(a, n) vi a(n+1); FE(i,1,n) { cin>>a[i]; } #define cinvd(a, n) vd a(n+1); FE(i,1,n) { cin>>a[i]; } #define cinvll(a, n) vll a(n+1); FE(i,1,n) { cin>>a[i]; } void solve() { ll w, n; cin>>w>>n; vll x(w,0); FE(i,0,w-1) cin>>x[i]; function cost = [&](ll st) { ll moves = 0; FE(i, 0, w-1) { if(st > x[i]) { moves += min(st-x[i], x[i]+n-st); } else if(st < x[i]) { moves += min(x[i]-st, n-x[i]+st); } } return moves; }; ll l = 1, r = n; while(r-l>=3) { ll mid1 = l + (r-l)/3; ll mid2 = r - (r-l)/3; ll c1 = cost(mid1); ll c2 = cost(mid2); if( c1 < c2) r = mid2; else l = mid1; } if(l==r) cout<< cost(l)<<"\n"; else if (l+1==r) cout<
•  » » » » » 8 days ago, # ^ |   0 The ternary search solution isn't correct. I just managed to get accepted because the tests were not strong enough.Here is my solution link https://pastebin.pl/view/bfb7d20d with a random heuristic.
•  » » » » » » 8 days ago, # ^ | ← Rev. 2 →   0 Don't know about your solution but i think ternary search in following way will work .1.Sort the array of weights (say "$w$"). 2.Traverse the array.For index $i$ , minimum cost for converting all other elements to $w[i]$ can be found by doing ternary search on the left of $i$ as well as on the right of $i$ . Leftmost element will try to move to $n$ and then to $n-1,n-2$ and finally to $w[i]$ . Example : suppose $n = 40$ and array after sorting is $2 , 3 , 33 , 35 ,37$ . Suppose we are converting to $35$ . Then for $2$ and $3$ it will best to move toward $40$ and then toward $35$ . Whereas for $33$ it can move directly toward $35$.Similar explanation for the right side of $i$.
•  » » » » » » 8 days ago, # ^ |   0 I would welcome anyone to hack the solution.
•  » » » » 7 days ago, # ^ |   +23 The function F(X) : Min. Moves to convert all elements to X is not unimodal. Consider the following test case : 15 15 11 13 12 3 2 8 13 6 6 11 7 7 1 1 8 The values of F(X) are F(X) for X from 1 to 15(1,59) (2,58) (3,59) (4,60) (5,58) (6,53) (7,50) (8,51) (9,54) (10,54) (11,52) (12,53) (13,56) (14,61) (15,62) The graph looks like this :
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 My solution for C:First we will calculate number of moves required for turning every lock to 1 and also calculate the number of locks whose value is increasing and decreasing. For each lock there is atmost 3 critical numbers (number of the lock, numbers which are at n/2 distance) where the increasing or decreasing nature may change.I inserted all critical points and sorted them and only checked the answer on the critical points.
•  » » 8 days ago, # ^ | ← Rev. 5 →   0 I did it with checking answers for each value in array as a assumed target with some manipulations using prefix sums and two pointers on sorted array My manipulations auto make = [&](int i, int c1, int c2) { int ans = 0; ans += give(i, c1) - (c1 - i + 1) * a[i]; ans += (n - 1 - c1) * (k + a[i]) - give(c1 + 1, n - 1); ans += (i - c2) * a[i] - give(c2, i - 1); ans += (c2) * (k - a[i]) + give(0, c2 - 1); return ans; }; int mi = inf; int p1 = 0, p2 = 0; for (int i = 0; i < n; i++) { while (p1 < n and 2 * (a[p1] - a[i]) < k) p1++; while (p2 < i and 2 * (a[i] - a[p2]) >= k) p2++; int ans = make(i, p1 - 1, p2); mi = min(ans, mi); } Give is just prefix sum of that range
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 I did it using the sliding median(sliding cost on the array of size $2 \times W$). Sort $X$ and consider array $A$ of size $2 \times W$ where first $W$ elements are $X_i$, and last $W$ elements are $N + X_i$. Then it reduces to finding minimum cost in CSES — Sliding Cost with $k = W$ and $n = 2 \times W$.
•  » » » 7 days ago, # ^ |   +4 why are we pushing w elements of n+x_i?
•  » » » » 7 days ago, # ^ | ← Rev. 5 →   0 Since our cost function is $\sum{\min(|x - X_i|, N - |x - X_i|)}$ and it can be observed that $x \in X$.UPD: I'm not sure about the correctness, but I had this intuition that adding $N$ will handle this part $N - |x - X_i|$ (like the usual doubling in circular problems).
•  » » » » » 7 days ago, # ^ |   0 Yeah now I get it.
•  » » » 7 days ago, # ^ |   0 can you please provide the sliding median solution. I had the similar idea, but i needed some help
•  » » » » 7 days ago, # ^ |   0
•  » » 8 days ago, # ^ | ← Rev. 2 →   0 problem C without ternary search. https://pastebin.com/eX0UPCSC
•  » » » 6 days ago, # ^ |   0 Great solution!
•  » » 8 days ago, # ^ |   0 i did it using binary search. PS.: don't know ternary search and how it works
•  » » » 7 days ago, # ^ |   0 Not-Afraid Hey, Can you Please share your Solution as well as approach. I too tried to implement using Binary Search but I failed to do so. It would be helpful if you could share your Solution and your logic/some explanations. Thanks !!
•  » » » » 7 days ago, # ^ |   0 Note: It would be very hard for me to explain every single bit of my solution but i will try to give a rough idea. First let's sort the array. If we want to calculate answer for some index $i$: then the given array splits into three parts: [some_prefix] + [some contiguous subarray containing index i] + [some_suffx]. Note: Above three arrays do not intersect, their union is equal to given array and 1st & 3rd array might be empty. And the idea is that all elements in 2nd array will be directly converted into $ai$. for (val in 2nd array) answer += abs(val - a[i]); and elements in 1st and 3rd array will be converted indirectly i.e. taking them to one end ($1$ or $N$ and then taking them to $ai$). Now for some given $i$ you can calculate the starting and ending index of second array using binary search. The rest is just a bit of calculation using prefix sums. PS: You can take a look at my code at your own risk, because i overkilled it and there is a 99% chance that it will be hard for someone else to understand the code.
•  » » 8 days ago, # ^ |   0 I did it without using ternary search. My approach was calculating number of moves to convert all elements to each x[i] and taking the minimum. For doing so, I used upper bound, lower bound and prefix-sums. I'll describe in detail if someone needs it.
•  » » » 7 days ago, # ^ |   0 Please if you can give detail. I am still unable to understand how binary search works or even two pointer approach for that matter. Also, it will help I think if you could describe how you thought about this problem and came up with the clever solution that it is.
•  » » » 7 days ago, # ^ | ← Rev. 2 →   0 I also used the same approach, but my solution is giving TLE ( on test set 3). Can u please help me figure out, why am i still getting TLE. Time Complexity of my code is ; w*log(w) ; 1 <= w <= 10**5 Link to Solution; https://ideone.com/RbfXkV Thanks in Advance :)
•  » » 7 days ago, # ^ | ← Rev. 3 →   +1 O(w) solution1)Just make an array of 2 * w size with the value from w to 2 * w — 1 is duplicated with extra n.2)Now for each segment of size w find the ans assuming all elements of the segment will become equal to its median(you have to precalculate prefix sum to get sum of a segment).3)get the max of all ans.
 » 8 days ago, # |   0 How to solve D for full points?I simply used brute force for 9 points. I thought of making a tree with its leaves representing the values on the cards and the root representing the answer(expected sum)
•  » » 8 days ago, # ^ | ← Rev. 3 →   0 Overcomplicated solution, see Errichto's solution below.
 » 8 days ago, # | ← Rev. 2 →   0 .
 » 8 days ago, # | ← Rev. 2 →   +44 Screencast with post-commentary and solutions, 2nd place: https://youtu.be/RpyWh424VCE (fast ABD, overcomplicated C with two pointers)
•  » » 7 days ago, # ^ |   0 Your solution to D is soo amazing
 » 8 days ago, # |   0 Can someone explain to me problem C statement.I don't get the part where it says that from 2 you can get to 1 or N.
 » 8 days ago, # |   +3 what was difficulty level of question in terms of codeforces ratings.
 » 7 days ago, # |   0 Can we solve problem D using a linked list ? Space-complexity will be O(n*n) . We can just do what is given in the question .
 » 7 days ago, # |   0 The random test file generated by me for debugging my C solution with 2 binary searches. Tests504 73 6 2 4 7 31 2 3 2 3 2 3 7 11 1 1 1 1 1 1 3 11 1 1 6 103 3 9 10 8 4 7 21 2 2 2 2 1 2 9 51 1 4 2 2 1 2 4 3 1 74 6 63 4 3 6 5 4 4 85 8 7 2 5 83 5 4 7 8 9 71 5 5 1 3 2 2 6 57 92 2 8 1 4 3 11 548 22 1 2 1 1 1 2 1 7 22 2 1 2 1 2 2 8 84 2 4 6 8 8 1 2 4 71 2 2 5 5 94 3 9 4 3 1 98 6 11 1 1 1 1 1 2 22 2 9 54 2 1 4 1 5 5 5 5 8 71 1 4 2 4 1 3 5 8 96 3 4 8 9 8 9 2 6 43 1 4 4 1 2 7 54 4 4 4 2 1 5 9 91 7 1 3 1 3 4 7 3 1 103 6 51 1 5 5 2 5 3 33 2 1 6 54 2 3 4 5 4 7 95 5 9 2 7 8 5 1 96 1 73 7 33 3 2 1 3 3 1 3 51 2 3 10 101 9 2 4 2 2 1 4 5 1 4 102 10 7 10 4 41 3 4 3 7 51 1 5 2 3 2 3 6 72 1 1 5 2 3 10 107 1 3 8 7 2 4 3 2 6 10 102 5 10 2 1 8 6 9 8 1 5 91 8 5 6 9 2 11 1 3 33 2 1 3 101 3 9 4 93 4 3 9 2 107 3 AnswerCase #1: 5Case #2: 4Case #3: 0Case #4: 0Case #5: 13Case #6: 2Case #7: 8Case #8: 0Case #9: 5Case #10: 6Case #11: 8Case #12: 15Case #13: 8Case #14: 0Case #15: 3Case #16: 2Case #17: 13Case #18: 4Case #19: 5Case #20: 0Case #21: 0Case #22: 0Case #23: 6Case #24: 11Case #25: 14Case #26: 5Case #27: 5Case #28: 15Case #29: 0Case #30: 4Case #31: 2Case #32: 4Case #33: 12Case #34: 0Case #35: 0Case #36: 3Case #37: 2Case #38: 13Case #39: 5Case #40: 3Case #41: 6Case #42: 6Case #43: 21Case #44: 20Case #45: 8Case #46: 0Case #47: 2Case #48: 4Case #49: 4Case #50: 4
•  » » 6 days ago, # ^ |   0 Thank you for these tests!!! My solution was failing only for testcase 26 of yours , corrected it and my solution got accepted :P Btw how did you generate these test cases?
•  » » » 6 days ago, # ^ |   0 Just wrote these random generator in some minutes and then saved the output of this in a file. generator#include using namespace std; typedef long long int ll; #define endl '\n' int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll t=100; cout<
•  » » » » 6 days ago, # ^ |   0 Thanks!
 » 7 days ago, # | ← Rev. 4 →   +14 My video editorial for the round: Google Kick Start Round G, 2020: Editorial rough notes used: google doc notesProof for Problem 3, Set: 2 Initial wheel values(V) = {v1,v2,v3....vw} Claim: it is always possible to get the optimal solution by only trying out the values v1,v2,v3...vw. Assume that value x = p gives a better solution and p does not belong to V.This means we bring all the wheels to the position p and cost is minimised on doing so.We have the following scenario: v1...v2... ... vi....p...v(i+1)... ...vwNow all wheels will reach p by either moving forward or backward.Let's say x1 wheels approach p from the left of it and x2 wheels approach p from the right of it.If x1 < x2 We can obtain a better answer by shifting x=p to x=v(i+1) On similar lines if x1 > x2 then move x to x= vi If x1=x2 It would make no difference to the answer even if we move it to either vi or v(i+1)Hence a better answer cannot be obtained at a value x = p such that p does not belong to V.Let me know if this makes sense.
 » 7 days ago, # | ← Rev. 2 →   0 I am trying to solve the First question in java but getting RE can someone review my code and tell what I did wrong? Submission link
 » 7 days ago, # |   -6 Problem A:My code: #include #define ll long long #define pb push_back #define all(x) x.begin(), x.end() #define sz(x) (ll)(x.size()) #define pll pair #define vll vector #define INF (1ll << 60) #define ld long double // #define tc ll tt; cin >> tt; while(tt--) #define MOD 10000007 using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int tt = 1; cin >> tt; for (int tc = 1; tc <= tt; tc++) { string ss = "akshat"; cin >> ss; long long maxi = 0, ans = 0; int pos = 0; vector ki, st; while (1) { if (ss.find("KICK", pos) == string::npos) break; pos = ss.find("KICK", pos); ki.pb(pos); pos += 4; } pos = 0; while (1) { if (ss.find("START", pos) == string::npos) break; pos = ss.find("START", pos); st.pb(pos); pos += 5; } for (auto pp: ki) { for (auto qq: st) { if (qq > pp) ans++; } } cout << "Case #" << tc << ": " << ans << '\n'; } } It was giving WA. Any idea? I could not figure it out.
•  » » 6 days ago, # ^ |   +1 You should increase pos by 3 when checking string "KICK" because KICK string can overlap like "KICKICK" in this case you will skip the second string KICK
•  » » » 6 days ago, # ^ |   0 Thank You very much for replying. Now I got it.
•  » » » » 6 days ago, # ^ | ← Rev. 2 →   0 btw your corrected code with pos+=3; should give TLE. but because of only 2 test sets google can't have 100 testcases with same string.with below input your code will give TLE.100 testcases with same strings of length 10^5. KICKSTARTKICKSTARTKICKSTART...(upto 10^5 length). your ki and st vectors will be of lengths (10^5)/9. so total time complexity of each test will be around 10^8. so total time will be 10^10. which will give TLE
 » 7 days ago, # |   -7 Congratulations tmwilliamlin168 for winning!Solution video link: https://youtu.be/xCYQQoaKftI .
 » 7 days ago, # |   +56 The last problem (Merge Cards) can be solved in $O(N)$ instead of $O(N^2)$, and it's pretty simple.There are $N-1$ possible bars (splits) between the $N$ elements, and the described process just removes bars in random order. When a bar is removed, the score increases by the sum of elements up to next existing bar on the left and on the right. We add element $a_i$ to the score when removing bar between positions $j$ and $j+1$ if and only if all bars between $i$ and $j$ were already removed (assume $i \leq j$). One bar is last among $j-i+1$ bars with probability $\frac{1}{j-i+1}$ so we increase the answer by $\frac{a_i}{j-i+1}$. Iterating all pairs $(i, j)$ is $O(N^2)$, and we get rid of iterating $j$ by precomputing harmonic sum $\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \ldots$. code (20 lines)#include using namespace std; int main() { int T; scanf("%d", &T); for(int test = 1; test <= T; ++test) { int n; scanf("%d", &n); vector harmonic(n + 1); for(int i = 1; i <= n; ++i) { harmonic[i] = harmonic[i-1] + 1. / i; } double answer = 0; for(int i = 0; i < n; ++i) { int ai; scanf("%d", &ai); answer += ai * (harmonic[i] + harmonic[n-1-i]); } printf("Case #%d: %.10lf\n", test, answer); } }
•  » » 7 days ago, # ^ |   0 Since no one has answered this question above, I am asking you can you tell us what was difficulty level of problem C and D in terms of codeforces ratings?( this would help me in practice)
•  » » » 7 days ago, # ^ |   +8 You can do the comparison yourself. Either by seeing how complicated topics and solutions are, or by seeing how many people solved it or how quickly people in the top got AC. Then tell us here what difficulty it is.
•  » » » » 7 days ago, # ^ |   0 I was able to solve testset 1 and 2 for problem C but couldnt solve its testset 3, So I think testset 3 difficulty was somewhat around ummmmm.... ~1800(maybe)? And D ~2100? I dont know if its correct or not, Its been 2 months since I started CP thats why I wanted to ask form an experienced guy.
•  » » » » » 6 days ago, # ^ | ← Rev. 2 →   0 In Global round 11, C was solved by 1.3k people and it's rated 2000. So i think test case 3 of C deserves at least 2100+. In terms of difficulty as well i'd say.
•  » » » » » » 6 days ago, # ^ |   0 I solved testcase 3 of C, and i have full confidence in myself that i can't solve 2100+ rated problem in a contest.
•  » » » » » » » 6 days ago, # ^ |   0 Yea same here... Although i took abt an hour for c but did solve it.. It feels more like a 1700-1800 problem
•  » » » » » » » 6 days ago, # ^ | ← Rev. 2 →   0 I don't agree with that logic. Maybe you did it now for the first time, you never know. Edit: the problem rating on CF depend on the previous problem difficulty in the same contest so my comparison wasn't very accurate either.
•  » » 6 days ago, # ^ |   0 What would have happened if instead of merging 2 adjacent elements, we were allowed to merge any 2 random elements from array and keeping other conditions same .
•  » » 6 days ago, # ^ | ← Rev. 2 →   0 I got the O(n^3) approach where we define 2 random variables X1, X2.Where X1 is the sum accumulated by merging [L, I] to a single elementWhere X2 is the sum accumulated by merging [I + 1, R] to a single elementSo the answer would be a another random variable X = X1 + X2 + v[i] + v[i + 1]By law of expectations : E[X] = E[X1] + E[X2] + v[i] + v[i + 1].However I did not get why your approach works, can you share the rules/laws you used to get to the result.
•  » » » 5 days ago, # ^ |   +3 I call it "contribution to the answer" but it's just linearity of expectation. Check out my old tutorial https://codeforces.com/blog/entry/62690