### kostka's blog

By kostka, 9 months ago, ,

I haven't seen any post, so let me announce that the Round E of Google Kick Start 2019 is happening this Sunday (August 25) at 5:00UTC. Get ready and register now at g.co/kickstart.

.

• +69

 » 9 months ago, # |   +8 Can anyone tell why I am not being able to click the "submit attempt" button even after selecting the language ? Please help.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 If the problem still occurs, please ask on the platform, not here.
•  » » » 9 months ago, # ^ |   0 Yeah I mailed them and they told me few possible solution but alas, nothing helped .
•  » » » » 9 months ago, # ^ |   0 I didn't know what was the problem. However when I logged in from my windows instead of ubuntu, I was able to submit the solutions.
•  » » » » » 9 months ago, # ^ |   0 I think it is the clock issue in the laptop. Clock is correctly set for me in windows but it was wrongly set in ubuntu.
 » 9 months ago, # | ← Rev. 2 →   0 Even I am not able to click the submit button. What is wrong?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 If the problem still occurs, please ask on the platform, not here.
 » 9 months ago, # |   -13 Not sure if I like this "Results hidden until end of round".What am I supposed to do with it. Sit arround and ask myself, "Huh, is it really fast enough?"
 » 9 months ago, # |   +32 How to solve code-eat switcher? Is it dp or there is some greedy tricks??
•  » » 9 months ago, # ^ |   0 That's how I did it:Sort the days in decreasing order of eating units.Sort slots by the ratio of coding to eating units.Initially, use all slots for 100% eating. Days with more required eating units than that, are 'N' obviously.Iterating over the days, while our current number of eating units is higher than needed, in the sorted order of slots, exchange the eating into coding (So that we get the highest possible amount of coding units for the needed number of eating units). If possible coding units are greater than required, it's a 'Y'.I got WA on large tests though, not sure if because of precision issues, or maybe my solution is actually wrong, is it?
•  » » » 9 months ago, # ^ |   -8 It turns out its wrong -- If you check the limits its 10^5 points and 10^5 queries.
•  » » » » 9 months ago, # ^ |   0 How does that change anything?Can you give a test case where it fails?
•  » » » » » 9 months ago, # ^ |   0 You provided an algorithm that is O(N) per query, ie. O(NQ) for the test case. When NQ = 10^10, it fails.
•  » » » » » » 9 months ago, # ^ | ← Rev. 3 →   +8 No, its complexity is O(N log N + Q log Q), and if you read carefully, I got WA, not TLE.We keep an iterator on the last slot, that is not fully changed from eating to coding units in the order of the best coding to eating ratios. We sweep through the queries in an offline order.
•  » » » » » » » 9 months ago, # ^ |   +8 Maybe you have already found the issue, but I think your approach is correct.I also got WA on large test set and my problem was an integer overflow at some point in the code. In particular, it was when interpolating the value of coding units for a given value of eating units. After performing this operation using 64-bit integers, I got AC.Hope this is useful for you!
 » 9 months ago, # |   0 when can we submit in practice mode?
•  » » 9 months ago, # ^ |   0 Now you can submit :)
 » 9 months ago, # |   0 Can someone please help in finding why my nlogn solution given TLE for (hidden test cases)Code-Eat Switcher.Solution: https://ideone.com/awL83T
 » 9 months ago, # |   -25 Problem 2 — Bonus: Solve for exactly (Ai, Bi) rather than at least (Ai,Bi).
 » 9 months ago, # | ← Rev. 2 →   +18 Quick editorial:Q1 SpoilerGreedily place 1 cost edges any time it reduces the number of connected components (we can use a DSU structure). Afterwards, we need to add 2 cost edges equal to the number of connected components minus 1.Q2 SpoilerSuppose you always eat. Now you would like to start coding: clearly, you want to choose the slot that is most productive (ie. has the best code / eat ratio) first. You can plot this as a polyline from (0, Y) to (X, 0), where X is the most you can code in a day and Y is the most you could eat in a day.Now you want to answer queries: is (a, b) under this polyline? You can binary search for the two points that border the line, then interpolate.Q3 (method 1) SpoilerLet's try to calculate for each L <= x <= R, how many odd divisors and even divisors it has. Using a sieving approach, for each prime we can find all numbers x in [L, R] that divide that prime, and find that primes' contribution to x's number of divisors. Then ignoring the 2^e part of the number, we can find the odd divisors too, and use even = all — odd to finish.Q3 (method 2) SpoilerLet's try to find out whether x in [L, R] is interesting. Suppose the prime factorization of x is 2^e1 * 3^e2 * 5^e3 * ... Let K = (e2+1) * (e3+1) * ... K is the number of odd divisors, and so the number of even divisors is e1 * K. So, a number is interesting iff abs((e1 — 1)) * abs(K) <= 2.Let's go into cases: If e1 = 0 or e1 = 2, then abs(K) <= 2, so the number x must be prime. If e1 = 1, then its always interesting. If e1 = 3, then K must be 1 (ie. x = 8) If e1 > 3, then its always not interesting.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 for Question 3 I thought and implemented the same strategy as mentioned by you in method 2 but for the case e1==0 or e1==2 while finding whether K is prime or not I think I got TLE on larger set. What can be the fastest way to find it? Using sieve for every number upto 10^9 will give MLE and even TLE
•  » » » 9 months ago, # ^ |   +1 If e1==0 then it just segmented sieve on [L,R] to find interesting numbers with e1==2 then just precalculate segmented sieve on [L/4,R/4] as done above and use this result.
•  » » » » 9 months ago, # ^ |   0 Thanks!! Didn't know about Seg Sieve.
•  » » 9 months ago, # ^ |   0 can we apply Gauss method for solving system of linear equations in question 2 ??
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 For Q1 : To make each pair connected directly or indirectly and make minimum possible sugar content we reduce it to tree where edges have sugar content 1 or 2 such that black + red (total no. of edges) = no. of cherries — 1 (no. of vertices — 1). So two cases are possible : if( black > no. of cherries -1 ) : here answer = 1*black. else if( black <= no. of cherries -1 ) : here answer = 1*black + 2*(no. of cherries — 1 — black). Is there anything wrong here ..??
•  » » 9 months ago, # ^ |   0 what is the complexity of your code?
•  » » 7 months ago, # ^ |   0 in q2) where you taking the case that a slot could be partioned?aren't you taking entire slots only?
 » 9 months ago, # | ← Rev. 3 →   0 Hello, My handle on google kickstart is by the name "FIREBIRD33". The following is my code for the first problem: from collections import * def find(a): while a!=l[a]: l[a]=l[l[a]] a=l[a] return a def printgoogle(a,b): print("Case #",a+1,": ",b,sep="") for _ in range(int(input())): n,m=[int(i) for i in input().split()] l=[i for i in range(n)] # print(l) for i in range(m): x,y=[int(i) for i in input().split()] x-=1 y-=1 x,y=find(x),find(y) if l[x]>l[y]:x,y=y,x l[y]=x visited=[False for j in range(n)] for j in range(n-1,-1,-1): # if not visited[j]: l[j]=find(j) # visited[j]=True # print(l) cnt=Counter(l) tot=0 totsame=0 diff=0 for i in cnt: if cnt[i] > 1: tot+=cnt[i]-1 tot+=(len(cnt)-1)*2 printgoogle(_,tot) After the contest ended I submitted the same solution from my competitve submissions and it got accepted for both the test subsets.But during the contest only first test subset was passed.Please look into this!!!!! Thanks!!!
 » 9 months ago, # | ← Rev. 3 →   0 Hello, I want to raise an issue towards Google's Test sets.I checked the below submitted solution by a user whose HANDLE is "frextrite" . The third code submitted by this user is accepted by Google but when i debugged it with the below test case it showed TLE. Are google's test case strong enough!!!!!CODE:#include #define MAX ll(1e5)using namespace std;typedef long long ll;vector primes(1e9+5, true);void sieveOfErastosthenes() { for(int i = 2; i <= MAX; i++) { if(primes[i]) { for(int p = 2*i; p <= 1e9; p+=i) { primes[p] = false; } } } }bool solve(ll x) { ll temp = x; int even_fact = 0; while((temp & 1) == 0) { even_fact++; temp /= 2; } if(temp == 1) { return (even_fact-1 <= 2); } return (even_fact == 1) || (even_fact == 2 && primes[temp]) || (even_fact == 0 && primes[temp]);}int main() { ios_base::sync_with_stdio(false); int t; cin >> t; sieveOfErastosthenes(); for(int c = 1; c <= t; c++) { ll l, r; cin >> l >> r; int count = 0; for(ll i = l; i <= r; i++) { if(solve(i)) { count++; } } cout << "Case #" << c << ": " << count << "\n"; } return 0;}TEST CASE:11000005 1000020
•  » » 9 months ago, # ^ |   0 I've never thought of this, but maybe it can pass the test, since it only needs to run one sieve across all test cases.
 » 9 months ago, # |   +5 Maybe I am thinking of Code Jam, but didn't the analysis for the round and problems used to be ready very soon after the round?
 » 9 months ago, # |   0 Hi, I'm new to Kick Start. For problem A, I used Kruskal's algorithm to find the cost of minimum spanning tree. I AC the small dataset but I got Runtime Error for large dataset. I have no clue why I got Runtime Error. Could anyone give me a hint? Thanks.My solution
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 You don't need Kruskal for this problem just find connected components and there size mst of each component will be n-1 then connect components with components -1 edge of weight 2
•  » » » 9 months ago, # ^ |   0 Yeah, I realized this better solution from others' comments. But I'm still curious why I got Runtime Error for large dataset even though my solution passed the small dataset.
•  » » » » 9 months ago, # ^ |   +1 N is 1e5 for large dataset.You cannot create a array of N * N size.
•  » » » » » 9 months ago, # ^ |   0 I see. Thanks.
 » 9 months ago, # |   +8 Analysis has been published! You can find the Analysis tab on each problem site.