Блог пользователя ProveMeRight

Can someone verify? that this question can be solved or it's impossble.
Автор ProveMeRight, история, 20 месяцев назад, По-английски

let's suppose the case:

k = 1, n = 1000;

arr[] = {1,3,5,7,9,11,..........1999]

For this case, the answer can be 2^N, and according to the question we have to return an integer. Is it possible?

Please help someone.

Thank you.

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
20 месяцев назад, # |
← Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
Hint1
Hint2
Hint3
→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    hint4: Read the issues mentioned in the blog first, rather than rushing to growing contribution.

    → Ответить
    • »
      »
      »
      20 месяцев назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится
      Hint5
      → Ответить
»
20 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Since n<=10^3 we can solve the problem in O(n^2) by the naive implementation of biginteger.

→ Ответить
»
20 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Yes, it is possible. $$$2^{1000}$$$, which is the largest possible answer, has roughly $$$300$$$ digits. Multiplying numbers to get to a $$$300$$$ digits number shouldn't be too slow. If you still get TLE, you can just represent bigInt using base $$$10^{9}$$$, which would bring the number of digits down to a laughable $$$34$$$. If you are using Python then time limit shouldn't be a problem as well, as Python has built-in Karatsuba multiplication algorithm, which is fast.

→ Ответить
  • »
    »
    20 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Multiplying $$$k$$$ numbers (polynomials) in the case when answer has $$$n$$$ digits is $$$O(n^2)$$$. One may prove it with a reasoning simar to the one behind $$$O(n^2)$$$ knapsack on trees.

    → Ответить