| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3690 |
| 2 | jiangly | 3647 |
| 3 | Benq | 3581 |
| 4 | orzdevinwang | 3570 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | Radewoosh | 3509 |
| 8 | ecnerwala | 3486 |
| 9 | jqdai0815 | 3474 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | awoo | 165 |
| 3 | adamant | 161 |
| 4 | TheScrasse | 160 |
| 5 | nor | 158 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 152 |
| 8 | orz | 146 |
| 9 | SecondThread | 145 |
| 9 | pajenegod | 145 |
I was trying to solve this problem 27E - Число с заданным количеством делителей, it was said in the editorials that this is a dynamic programming problem,
but i tried to solve it using only back tracking with pruning and i got AC 19429925.
could anyone tell what is the complexity of this solution?! or how to measure the complexity of bt solutions in general?!
thanks in advance :)
1) Look at maximal possible depth of recursion for each divisor. They don't go so deep, and this is upper bound.
2) The main speed-up is
if (divs <= n)statement becausen <= 1000and thereforedivscannot be greater than nine, which is reached only when we take each of the divisors once.In general it's very hard to give some good upper bound for backtracking solutions like that and all you can do is to say: "OK, we have these rough estimates that are not so helpful, let's add some optimisations and hope that this'll give us AC".