Round B starts in less than 24 hours (on April 18th at 23:00 UTC).
Join our online coding competition and tackle fun problems designed by Google engineers! ➡️g.co/kickstart
→ Обратите внимание
До соревнования
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
Rayan Programming Contest 2024 - Selection (Codeforces Round, Div. 1 + Div. 2)
6 дней
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3993 |
| 2 | jiangly | 3743 |
| 3 | orzdevinwang | 3707 |
| 4 | Radewoosh | 3627 |
| 5 | jqdai0815 | 3620 |
| 6 | Benq | 3564 |
| 7 | Kevin114514 | 3443 |
| 8 | ksun48 | 3434 |
| 9 | Rewinding | 3397 |
| 10 | Um_nik | 3396 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 156 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 24.11.2024 18:24:22 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
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?
we can replace 4th integer with 4 then from second number to the end
is of length 8 arithmetic subarray
what am I missing? please help
Thanks!
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 :)
:( 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?
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$$$
For seive of eritothenes, we need to first create a boolean array of that size, right? Z = 10^18
sqrt(Z) = 10^9
So, 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.
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
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.