### kostka's blog

By kostka, 4 weeks ago, Round B starts in less than 24 hours (on April 18th at 23:00 UTC).  Comments (29)
 » What an ugly problem set. Extremely easy A, tedious casework in B, find and copy primality test in C (turns out it wasn't actually required lol), only D is good...
•  » » I didn't find problem B particularly tedious. Calculated results using a recursive formula (is this DP?). My solution in Ruby — https://pastebin.com/n8AMQu2i What's your code for this problem?Except that I initially messed up and forgot to handle the reversed array case. Then tried to implement a simple bruteforce solution, but Ruby code wasn't fast enough. Converted this bruteforce solution to C++ and confirmed that it's accepted for the small data set. Then generated random input data and identified a broken testcase. Wasted more than 1 hour on this debugging. Looks like I need more practice to do it much faster.Is Google Kick Start very unpopular? Seems like there were only around 7500 participants (including those who didn't manage to solve any problem).
•  » » » The main reason for less participation was that most of the participants are from India every time, but as this time for Indian students the time was a bit off, that was 4 in the morning, that's why participation was less.
 » In problem B, can someone explain why the answer isn't 8? 9 5 5 4 5 5 5 4 5 6 we can replace 4th integer with 4 then from second number to the end 5 4 5 4 5 4 5 6 is of length 8 arithmetic subarraywhat am I missing? please helpThanks!
•  » » I think you expect the difference between the adjacent elements to be either -1 or +1. But you should pick only one of them. The sign matters :)
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   :( Oh!, Thanks They should have made the problem statement clear by specifying how they are taking difference...just said the adjacent difference is the same but not specified the order :| This problem ruined my day ＞﹏＜
•  » » » » "For example, $[9,10], [3,3,3],$ and $[9,7,5,3]$ are arithmetic arrays, while $[1,3,3,7], \color{red}{[2,1,2]}, and [1,2,4]$ are not."
 » Problem C judge was very weird, it was sometimes giving Sample Failed: MLE for no reason,this problem submissions need to be rejudged. kostka
•  » » What's your solution?
 » Some people have sort of brute forced in test 3 of C, i.e. they just found the square root of the no and used a linear search to find its nearest primes and then some small casework. Shouldn't that give a TLE due to linear search of primes?
•  » » 3 weeks ago, # ^ | ← Rev. 4 →   I tried the same and got the wrong answer in test 3 for some reasons https://pastebin.com/QHTPhaeXCan someone please tell me why it is not enough to check the range of about 2e6 numbers around the square root? During the contest, I thought it should be enough as there will be enough primes covered also primes difference will be not more than ~2000 for numbers of the order 1e18FUCK!!!!!!!!!!!!!!!!!! I got my mistake (T_T) I wrote ll r=l+1000000; instead of ll r=tmp+1000000; :'(
•  » » The limit is 15 seconds bruh so if 10^8 iterations run in 1 second then 10^9 would run in 10 seconds :(
•  » » 3 weeks ago, # ^ | ← Rev. 2 →   There is a theorem in number theory that says something like the first prime equal or bigger the $N$ is in the order of $N +O(ln(n))$, so the search is in order of $O(ln(n))$, so if you use a fast primality test, this solution should pass
•  » » Use bitset
•  » » The largest gap between two prime numbers for primes <=10^9 is 282. (According to this).
•  » » I think it's perfectly fine to linear search for finding 2-3 nearest primes around $\sqrt{Z}$ if each number in neighbourhood of $\sqrt{Z}$ is compared against a list of primes smaller than $10^5$, to be deemed as prime. This list can be generated one time, using sieve of eratosthenes, and it will contain $9592$ values. Time Complexity = $\mathcal{O}(gap\cdot|list|)\;$ per test case, where $gap\sim300,\; |list|\sim10000$
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   For seive of eritothenes, we need to first create a boolean array of that size, right? Z = 10^18sqrt(Z) = 10^9So, if we need to know if sqrt(Z) is prime or not the list should be of size 10^9. But that will give runtime error. How can we check for sqrt(Z) if list is only of size 10^5?What am i missing?
•  » » » » You can check if numbers lying in the neighbourhood of $\sqrt{Z}\;(\leq10^9)$ are prime or not by knowing whether any prime less than $10^5$ divide them. $seive[1...10^5]$ is sufficient to generate a list of all such primes which are less than $10^5$
•  » » » » $10^9$ is OK if you use a boolean array.
•  » » » » » Filling it will take $\mathcal{O}(n\log\log n)$ time and for $n=10^9$ it will be significantly slow. It may pass if this is done only once per test set where the time limit is 15 seconds, but it is not the intended solution.
•  » » » » » » It's $\mathcal{O}(n)$ time if you use Euler sieve.
 » Good contest, enjoyed it. Just a suggestion in problem B, test cases were weak. My solution was O(n) only, but it had a minor bug, still passed for small test cases and got WA on the large test case.
 » It was a good contest!
 » kostka I understand that I'm probably asking too much. But is there any chance for Google Kick Start 2021 round B participants to qualify for the upcoming Google Code Jam 2021 rounds 1B and 1C? Or is waiting a year until the next Google Code Jam 2022 the only possible option right now?
•  » » Kick Start has nothing to do with Code Jam.
 » I uploaded my screencast of getting 1st place + explanations of my solutions to my YouTube: https://www.youtube.com/watch?v=HVISmqzgIq8
 » Check out my screencast if you are interested in how I got full marks: https://youtu.be/q036CmAYgfg
 » Approach for the problem C is easy for me but the implementation was difficult for me As the problem said we need to find the maximum product of the two prime number that should not be greater then z ................................................................................................................. So the answer behind this we first take the sqrt(z) and iterate to the left of sqrt(z) then for the first prime number from the left side consider that as num1 then divide that by z for the second prime number if the product of that second num with previously num1 is greater then z then leave that second number find the left prime number of num1 this is how we do
•  » » The problem C was really easy and I feel embarrassed that I didn't even try to read its description during the contest because of wasting too much time on debugging problem B.Checking primes in the neighbourhood of sqrt(z) is really fast. And Ruby programming language even supports primality test in the standard library. C++ users had to find some good primality test implementations from the Internet and copy/paste these implementations into their code, which probably ended up being a huge headache for the Google people responsible for plagiarism checks (the round B results are still "In review" right now).The only minor pitfall is that the minimal allowed value of z is 6 and its integer square root is only 2. There are no prime numbers on the left side of it and a buggy implementation may fail with a TLE verdict unsuccessfully trying to find primes among negative numbers.