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

Help needed in DP problem
Автор hemant_thakur, история, 2 года назад, По-английски

Can someone please help, what am I doing wrong ? Or on what test cases my solution is failing. It passes 12/19 test cases.

Here is the atcoder question link : LINK

Here is my solution:

Code

Thanks in advance :)

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

»
2 года назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

6

4 4 5 7 8 9

Suppose when you are at index 5 (1-based indexing) , elements you picked were: 4 5 ( let's call it way 1) and in another recursive call at index 5 you picked elements 4 7 ( way 2) , now it may be possible that in way 1 you get an integer average value but it may not be possible with way 2(but your program will return the answer calculated in way 1) , because sum of elements differ in both ways.

Try to visualize the whole process now and change your code accordingly.

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

    Ohh.. Got it man. You are a saviour. Thanks.

    Can't we take another state of 'sum' instead of 'average' ? (integer overflow might be the case or ?)

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

      Sorry my bad, actually we can't take either of them as a state because both of them range from 1 to 1e9 and we can't store that many values even in a 1-D vector.

      I edited my previous comment, please read it now. Sorry again

      → Ответить