Can anyone recommend resources for preparing for the Distributed Code Jam on June 14th? Some past problems of a similar nature would be really helpful.
→ Обратите внимание
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 21.05.2026 04:03:11 (f1).
Десктопная версия, переключиться на мобильную.
При поддержке
One problem which appeared in AE last year was to compute LCS of two strings up to 105 characters.
Some Simple Problems :
Problem 1
Given a Sequence A of integers , find i and j such that A(i) + A(i+1) ...+ A(j) is Maximum/Minimum , where length of A can be upto 10^10 . TL : 1 sec
Idea
Basically , we divide A into say 10^8 lengthed 100 segments , and then process each of them on different machines and later combine the information to find the answer .
Problem 2
Given a number N as large as say 10^20 , find it`s number of divisors .
Idea
Divide the set of possible divisors <= 10^10 , into 100 groups and then add the result from each of them.
But problem 2 can be solved on a single computer, there is probabilistic
algo
By the way, I always wonder why people don't multiply the complexity by log(n) which goes from finding gcd on every step? Let alone multiplying it once again when we work with big numbers and every operation consumes not constant, but logarithmic amount of time.
Because on average gcd will not really be log, and with sensible limits big numbers is just a constant
Because on average gcd will not really be log
How to prove it? If I got you right, you say that there is an upper bound for
that is better than log(n).
It's indeed O(log(n)) number of steps on average. About Pollard's rho algorithm, probably textbooks usually mention only expected number of iterations to avoid analyzing complexity for different arithmetic operations implementations.
Thank you for the link!
Yeah, your claim is correct for elimination of the second log(n), but after reading the wiki article I still have no idea why they don't mention the first one in the expected complexity.
Problem
Given a sequence of N(<=10^10) integers , find if there exists a Majority element.
Idea
Divide sequence into say K segments , then we process each of them individually to find candidates of Majority element and then the Majority element itself , if any .
So Complexity reduces to O( N / k )