Problem statement: You are given a number N, please find an array of length N so that, no two elements divide each other, and the total sum is minimized. N <= 1e5 Example: N = 1: arr = {1} N = 2: arr = {2, 3}
Caveat: it isn't the first N primes.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2026 06:59:23 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
that's N elements from N + 1 to 2*N
if i understand the statement correctly:
N = 5:
Output:
6 7 8 9 10
(if you want to minimize the sum, then go from N to 2*n — 1)
output:
5 6 7 8 9
I think you have to choose between that or first n primes, for example in n = 5
[5, 6, 7, 8, 9] = 35
[2, 3, 5, 7, 11] = 28
at some point maybe the former construction will be lower than first N primes as N gets larger? but I can't prove it myself just yet, though it is the only other sensible construction I can think of
isn't there also some "midway" answer (so-to-speak) as well that you have to consider?
e.g. consider [3,4,5,7,11] = 30. (It's not trivial to prove/disprove that this will always result in a worse answer than either of the two options presented)
Also, the proof of "consecutive numbers eventually beats primes" shouldn't be too hard to prove right?
The asymptotic complexity of the sum of the consecutive number construction is $$$O(N^{2})$$$ and the complexity of the prime number construction should be $$$O(N^{2} log N)$$$, so consecutive numbers should eventually end up beating out the prime numbers.
UPD: There, in fact, was some "midpoint" you had to consider.
Other people (Shisuko orz) discovered this breaks as low as $$$n = 7$$$.
$$$n = 7$$$
Consecutive = [7, 8, 9, 10, 11, 12, 13] = 70
First $$$n$$$ primes = [2, 3, 5, 7, 11, 13, 17] = 58
Better solution = [4, 5, 6, 7, 9, 11, 13] = 55
Initially with that it was theorized that a bruteforce sieve (exactly like Sieve of Erasthosthenes with trying each starting point from $$$2$$$ to $$$\lceil\frac{n}{2}\rceil$$$) works, however that also breaks as low as $$$n = 10$$$.
$$$n = 10$$$
Consecutive = [10, 11, 12, 13, 14, 15, 16, 17, 18, 19] = 145
First $$$n$$$ primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] = 129
Bruteforce sieve = [4, 5, 6, 7, 9, 11, 13, 17, 19, 23] = 114
Better than bruteforcer = [4, 6, 7, 9, 10, 11, 13, 15, 17, 19] = 111
So now the best solution seems to be heuristic? Replace the smallest value $$$x$$$ with $$$2x$$$, $$$3x$$$, $$$5x$$$, etc. and push it to a pq or something similar like that until there is enough and no greedy can improve on the value of the solution. There's a real possibility that the problem is not solvable in polynomial time.
Not smallest, but replacing all primes with p*q. Prime number remove all p*k, put (pq) remove (pq)*k (lets ignore double counting like 6=2x=3y). In you example for n=10, first 2 is replaced with 4, then 3 with 6, then 5 with 10. I'd expect at some point 2*4=8 will become best, sequence 8 9 10 11 12 13 14 15 ... has really few gaps. Feels like convex hull where lines are dominated by next are removed, but I don't see how to formalize it and exclude double counting.
For $$$[n, 2n - 1]$$$ $$$(n \geq 3)$$$, you can always remove $$$2n - 2$$$ and replace it with $$$n - 1$$$ for a lower sum. This operation can be repeated as long as there are numbers with only $$$1$$$ multiple present in the current set.
All primes doesn't work as well. Take $$$n = 7$$$, one optimal answer I believe is $$$[4, 5, 6, 7, 9, 11, 13]$$$, which is $$$3$$$ lower than the sum of the first $$$7$$$ primes. In fact, this set is the one you'll get if you repeat the operation I mentioned. This method barely works, until you get to $$$n = 17$$$ where the optimal answer is $$$[4, 6, 9, 10, 11, 13, 14, 15, 17, 19, 21, 23, 25, 29, 31, 35, 37]$$$
If I am not mistaken, you can just do this greedily. First, start by putting down $$$1$$$ then try to put down $$$2, 3, 4, 5$$$ but only put them down if there is not a divisor present in the array constructed so far. Even better, create a hashmap of all of the numbers and just check the divisors of every new number if one exists in the hashmap. Since there are only $$$O(n^{\frac{1}{3}})$$$ divisors, the time complexity could be $$$O(n^{\frac{4}{3}})$$$.
wouldn't starting with 1 just mean that you can't put any other number in the array? (all numbers are divisible by 1)
well it could be that $$$1 \le N \le 1$$$, in which case my solution would be correct
fr. Why consider the worst case when you can consider the best case?
Auto comment: topic has been updated by crowned_85 (previous revision, new revision, compare).
May consider the first N primes with 2 replaced with 4