# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Editorial of Codeforces Round #701 (Div. 2)
Suppose that you can use $$$x$$$ operations of type $$$1$$$ and $$$y$$$ operations of type $$$2$$$. Try to reorder operations in such a way that $$$a$$$ becomes the minimum possible.
How many operations do you need in the worst case? ($$$a = 10^9$$$, $$$b = 1$$$)
Iterate over the number of operations of type $$$2$$$.
Notice how it is never better to increase $$$b$$$ after dividing ($$$\lfloor \frac{a}{b+1} \rfloor \le \lfloor \frac{a}{b} \rfloor$$$).
So we can try to increase $$$b$$$ to a certain value and then divide $$$a$$$ by $$$b$$$ until it is $$$0$$$. Being careful as not to do this with $$$b<2$$$, the number of times we divide is going to be $$$O(\log a)$$$. In particular, if you reach $$$b \geq 2$$$ (this requires at most $$$1$$$ move), you need at most $$$\lfloor \log_2(10^9) \rfloor = 29$$$ moves to finish.
Let $$$y$$$ be the number of moves of type $$$2$$$; we can try all values of $$$y$$$ ($$$0 \leq y \leq 30$$$) and, for each $$$y$$$, check how many moves of type $$$1$$$ are necessary. This is a $$$O(\log^2 a)$$$ solution.
If we notice that it is never convenient to increase $$$b$$$ over 6, we can also achieve a solution with better complexity.
2000C - Numeric String Template
Rev. | Lang. | By | When | Δ | Comment | |
---|---|---|---|---|---|---|
en39 | TheScrasse | 2022-03-31 23:37:35 | 107 | |||
en38 | TheScrasse | 2021-02-12 21:06:06 | 270 | Tiny change: 'oiler>\n\n[probl' -> 'oiler>\n\nOfficial solution: [submission:107232596]\n\n[probl' | ||
en37 | TheScrasse | 2021-02-12 20:24:27 | 10 | Tiny change: 'xity: $O(n\log ' -> 'xity: $O(n)$ or $O(n\log ' | ||
en36 | TheScrasse | 2021-02-12 20:01:06 | 0 | (published) | ||
en35 | TheScrasse | 2021-02-12 19:59:22 | 48 | |||
en34 | TheScrasse | 2021-02-08 22:44:20 | 375 | |||
en33 | TheScrasse | 2021-02-07 02:22:26 | 1 | Tiny change: 'nswer is $max(dp_i)$' -> 'nswer is $\max(dp_i)$' | ||
en32 | TheScrasse | 2021-02-07 02:19:14 | 49 | |||
en31 | TheScrasse | 2021-02-07 02:17:14 | 537 | |||
en30 | TheScrasse | 2021-02-06 00:51:44 | 30 | |||
en29 | TheScrasse | 2021-02-06 00:46:24 | 479 | |||
en28 | TheScrasse | 2021-02-03 23:40:39 | 474 | |||
en27 | TheScrasse | 2021-02-03 23:27:44 | 22 | |||
en26 | TheScrasse | 2021-02-03 23:24:21 | 8 | Tiny change: 'exity: $O(t \cdot \sqrt x)$.' -> 'exity: $O(\sqrt x)$.' | ||
en25 | TheScrasse | 2021-02-03 20:20:22 | 3 | Tiny change: '$O(n^2\log(n))$.\n</spo' -> '$O(n^2\log n)$.\n</spo' | ||
en24 | TheScrasse | 2021-02-03 20:15:03 | 77 | Tiny change: 'h that $dp[j]$ correspo' -> 'h that $dp_j$ correspo' | ||
en23 | TheScrasse | 2021-02-03 20:08:31 | 479 | |||
en22 | TheScrasse | 2021-02-03 19:59:23 | 55 | |||
en21 | TheScrasse | 2021-02-03 19:56:35 | 192 | |||
en20 | TheScrasse | 2021-02-03 19:53:54 | 2809 | |||
en19 | TheScrasse | 2021-02-03 19:49:44 | 354 | |||
en18 | TheScrasse | 2021-02-03 19:43:40 | 42 | |||
en17 | TheScrasse | 2021-02-03 19:41:56 | 1068 | |||
en16 | TheScrasse | 2021-02-03 19:18:14 | 283 | |||
en15 | TheScrasse | 2021-02-03 19:14:41 | 9 | |||
en14 | TheScrasse | 2021-02-03 19:13:33 | 8 | Tiny change: ' y)$ is $min(y,x/k-1) - k$. The res' -> ' y)$ is $max(0, min(y,x/k-1) - k)$. The res' | ||
en13 | TheScrasse | 2021-02-03 19:11:31 | 32 | Tiny change: '\leq \sqrt x). For ea' -> '\leq \sqrt{x). For ea' | ||
en12 | TheScrasse | 2021-02-03 19:04:23 | 3 | Tiny change: '\leq \sqrt{x}). For eac' -> '\leq \sqrt x). For eac' | ||
en11 | TheScrasse | 2021-02-03 19:03:37 | 470 | |||
en10 | TheScrasse | 2021-02-03 18:52:18 | 458 | |||
en9 | TheScrasse | 2021-02-03 18:50:08 | 4 | Tiny change: 'o reorder operation' -> 'o reorder the operation' | ||
en8 | TheScrasse | 2021-02-03 18:48:26 | 537 | |||
en7 | TheScrasse | 2021-02-03 18:42:39 | 16 | |||
en6 | TheScrasse | 2021-02-03 18:41:53 | 52 | |||
en5 | TheScrasse | 2021-02-03 18:41:21 | 869 | |||
en4 | TheScrasse | 2021-02-03 18:38:39 | 2 | Tiny change: ' $b$ over 6, we can a' -> ' $b$ over $6$, we can a' | ||
en3 | TheScrasse | 2021-02-03 18:34:23 | 853 | Tiny change: 'til it is 0.\nBeing c' -> 'til it is $0$.\nBeing c' | ||
en2 | TheScrasse | 2021-02-03 18:22:34 | 410 | |||
en1 | TheScrasse | 2021-02-03 18:16:53 | 153 | Initial revision (saved to drafts) |
Name |
---|