I received an email about an event.
Be careful not to provide your password there! This is a scam. After clicking on register page you are NOT getting redirected to codeforces!
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3880 |
2 | jiangly | 3669 |
3 | ecnerwala | 3654 |
4 | Benq | 3627 |
5 | orzdevinwang | 3612 |
6 | Geothermal | 3569 |
6 | cnnfls_csy | 3569 |
8 | jqdai0815 | 3532 |
9 | Radewoosh | 3522 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | adamant | 156 |
4 | maroonrk | 153 |
5 | atcoder_official | 148 |
5 | -is-this-fft- | 148 |
5 | SecondThread | 148 |
8 | Petr | 147 |
9 | nor | 144 |
10 | TheScrasse | 142 |
I received an email about an event.
Be careful not to provide your password there! This is a scam. After clicking on register page you are NOT getting redirected to codeforces!
Hello!
Some time ago I created a problem for local programming competition. Unfortunately it turned out that I had incomplete proof of one lemma, that I can not show even to this day.
Lemma: Given an increasing array of $$$N$$$ arbitrary large numbers we define its cost as sum of lengths of all non-trivial, maximal arithmetic progressions starting at the first element. The cost of any array is $$$\mathcal{O}(N\log{N})$$$.
For example for array $$$[0, 2, 3, 4, 6, 8, 9]$$$ — the total cost is $$$|[0, 2, 4, 6, 8]| + |[0, 3, 6, 9]| + |[0, 4, 8]| + |[0, 6]| + |[0, 8]| + |[0, 9]| = 5 + 4 + 3 + 2 + 2 + 2= 18$$$.
It is easy to see, that if we simply take $$$N$$$ consecutive natural numbers we get $$$\mathcal{O}(N\log{N})$$$ cost, but I was not able to prove that this is the worst case scenario.
Best complexity I can show is $$$\mathcal{o}(N^2)$$$, but still far from the goal...
Can anyone show if the lemma is true or false?
Название |
---|