hemant_thakur's blog

Help needed in DP problem
By hemant_thakur, history, 22 months ago, In English

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 :)

  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
22 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?)

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply