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.

Before contest

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse!

24:38:07

Register now »

Codeforces Round #647 (Div. 1) - Thanks, Algo Muse!

24:38:07

Register now »

*has extra registration

Before contest

Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!

24:38:07

Register now »

Codeforces Round #647 (Div. 2) - Thanks, Algo Muse!

24:38:07

Register now »

*has extra registration

# | User | Rating |
---|---|---|

1 | MiFaFaOvO | 3681 |

2 | Um_nik | 3544 |

3 | maroonrk | 3431 |

4 | tourist | 3409 |

5 | apiadu | 3397 |

6 | 300iq | 3317 |

7 | ecnerwala | 3260 |

7 | Benq | 3260 |

9 | LHiC | 3229 |

10 | TLE | 3223 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 193 |

2 | antontrygubO_o | 191 |

3 | vovuh | 178 |

4 | pikmike | 177 |

5 | tourist | 166 |

6 | Um_nik | 165 |

7 | McDic | 164 |

8 | ko_osaga | 163 |

9 | Radewoosh | 161 |

10 | Geothermal | 158 |

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.

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/03/2020 16:56:54 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Can anyone tell why I am not being able to click the "submit attempt" button even after selecting the language ? Please help.

If the problem still occurs, please ask on the platform, not here.

Yeah I mailed them and they told me few possible solution but alas, nothing helped .

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.

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.

Even I am not able to click the submit button. What is wrong?

If the problem still occurs, please ask on the platform, not here.

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

How to solve code-eat switcher? Is it dp or there is some greedy tricks??

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?

It turns out its wrong -- If you check the limits its 10^5 points and 10^5 queries.

How does that change anything?

Can you give a test case where it fails?

You provided an algorithm that is O(N) per query, ie. O(NQ) for the test case. When NQ = 10^10, it fails.

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.

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!

when can we submit in practice mode?

Now you can submit :)

Can someone please help in finding why my nlogn solution given TLE for (hidden test cases)Code-Eat Switcher.

Question: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050edb/00000000001707b8

Solution: https://ideone.com/awL83T

Problem 2 — Bonus: Solve for exactly (Ai, Bi) rather than at least (Ai,Bi).

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.

Codes: https://github.com/AWice/cptraining/tree/master/GoogleKickStart

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

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.

Thanks!! Didn't know about Seg Sieve.

can we apply Gauss method for solving system of linear equations in question 2 ??

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 :

Is there anything wrong here ..??

what is the complexity of your code?

in q2) where you taking the case that a slot could be partioned?aren't you taking entire slots only?

Hello, My handle on google kickstart is by the name "FIREBIRD33". The following is my code for the first problem:

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!!!

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 <bits/stdc++.h>

#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; }

}

int main() { ios_base::sync_with_stdio(false);

}

TEST CASE:

1

1000005 1000020

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.

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?

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

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

Yeah, I realized this better solution from others' comments. But I'm still curious why I got

Runtime Errorfor large dataset even though my solution passed the small dataset.N is 1e5 for large dataset.You cannot create a array of N * N size.

I see. Thanks.

Analysis has been published! You can find the Analysis tab on each problem site.