By darkshadows, history, 6 months ago, ,

Google Kick Start hosts online rounds throughout the year, giving participants the opportunity to test and grow their coding abilities while getting a sample of the programming skills needed for a technical career at Google. Top candidates might be invited for interviews.

I invite you to solve some fun and interesting problems on Apr 20 2019, 23:00 UTC.

Dashboard can be accessed here during the contest. Problem analysis will be published soon after the contest.

• +32

 » 6 months ago, # |   0 For C large, I somehow feel that $Opt(l_1) <= Opt(l_2)$ if $l_1 <= l_2$, where $Opt(l)$ is the right-most index $r$ such that the tickets in range $[l, r]$ is maximum. Then I applied some divide-and-conquer, but failed to pass. Can anyone give an example where this is not the case? Thanks!
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 :`|
•  » » » 6 months ago, # ^ |   0 I changed my code during the contest to find the "leftmost" but still failed.Could you please explain why $ans[l_1][j] - ans[l_2][j]$ is non-increasing with $j$? Or would you like to give a example where my assumption is wrong?
•  » » » » 6 months ago, # ^ |   0 Sorry, I made mistake in my proof, This case will fail your argument. 6 25 5 5 1 5 2
•  » » » » » 6 months ago, # ^ |   0 But the $Opt$ value for each left point is the right-most point in the array, right?
•  » » » » » » 6 months ago, # ^ |   0 Following 1-based indexing Opt(1) = 6, but Opt(2) = 4), right?
•  » » » » » » » 6 months ago, # ^ |   +5 I see! Thank you so much!
 » 6 months ago, # |   -23 I feel this year is harder than last year. Am I wrong..
 » 6 months ago, # | ← Rev. 2 →   -32 darkshadows I am Ranked 58th globally. Are there any chances of getting call for an interview? Thanks.
 » 6 months ago, # |   0 Could anyone please explain to me why B — Test 1 uses sorting by 'L_i'? I thought it must be min(E_i, L_i) at each step since L_i is meaningless if it is more than the current energy?
•  » » 6 months ago, # ^ | ← Rev. 3 →   0 Infact i had the same doubt. Your condition i.e min(Ei,Li) works good for only 1st second.Consider a following case:E1=70 L1=50E2=80 L2=40lets say that optimal sequence wants to get above stones eaten after 1st second ( may be due to other stones having large L and E as well) . Then even though L2
•  » » 6 months ago, # ^ |   0 No matter what E_i is, the solution is always sorted by L_i. This is the key point. So the problem is simply to choose or not to choose stones from a L_i-sorted list.
•  » » » 6 months ago, # ^ |   0 Yes but I want to understand why it works like that and why is E_i not considered?
•  » » » » 6 months ago, # ^ |   0 Imagine why the smaller L is preferred. In such cases the actual potential loss of the bigger is the current E_big (< L_small < L_big). After the smaller is picked, the bigger reduces to zero, and can never be picked. So the order smaller -> bigger is actually smaller -> not picked. It's the same as bigger -> smaller, which is not picked -> smaller. That's why the bigger-L-first-order covers all the cases.
•  » » » » » 6 months ago, # ^ |   0 okay, it does make sense more if we exclude the not picked. Thanks.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   0 Let's say there are two sweets and the corresponding happiness factor and decay factors are $(e_{1}, l_{1})$ and $(e_{2}, l_{2})$. And suppose $l_{1} \ge l_{2}$. If you eat sweet1 then sweet2, you get the total happiness as $H_{1} = e_{1} + e_{2} - s*l_{2}$. But if you eat sweet2 then sweet1, the total happiness is $H_{2} = e_{1} + e_{2} - s*l_{1}$. You can easily observe that the order in which you eat depends on $l_{1}$ and $l_{2}$. And you can also observe that $H_{1} \ge H_{2}$ — Which means that eating sweet with higher decay factor first is better.It's not hard to see that this can be easily extended to large test.
•  » » » » » 6 months ago, # ^ |   0 actually, I think it should be e_1 + e_2 — s * min(e_2, l_2). Am I right?
 » 6 months ago, # |   0 Can somebody please explain segment tree operations for Problem 3 Diverse Subarray large test case?I'm not able to understand how max prefix sums of two child nodes can be used to calculate max prefix sum of the parent node.Please include complexity analysis too.
•  » » 6 months ago, # ^ |   0 Store the maximum prefix sum and sum of the elements covered by a node's range for each node. Consider a node P with a left child L and a right child R. The value of P.(max prefix sum) is max(L.(max prefix sum), L.(sum)+R.(max prefix sum)). Also, P.(sum) = L.(sum)+R.(sum). Recomputing the value of a single node is therefore O(1). During an update, if we start at the leaf node and work up through the parents, we visit O(log n) nodes. Each node requires O(1) time. Thus, the total complexity of a single update is O(log n).
 » 6 months ago, # |   0 Can someone help me in my code to problem Diverse Subarray https://code.hackerearth.com/cdc08bM because i cant find my mistake ... sample test cases and my own cases are running fine.