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

Can someone help me find mistake in my code?
Автор VandanRogheliya, история, 5 лет назад, По-английски

While solving this question I came up with this solution. I was getting WA. I checked my code 5 times, I was not able to find a mistake. Then Finally I checked the editorial, it was the same dp but in an iterative form. Can someone point out the mistake?

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think this line is wrong else Max = max(Max, recFun(dp,j));. Why is it there?

i.e. Let $$$P_{smax}$$$ be the position of the max S values. If this is in the first half of the array you will have $$$dp[P_{smax}]=2$$$ at some point of time, which is not correct.

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

    If I do not put else Max = max(Max, recFun(dp,j)); then for the test cases where $$$s[0]$$$ is not included will fail.

    And I did not get your 2nd point. You are trying to say if max from array S is in the first half then code would fail? If so, I checked, the code works for that test case.

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

      I modified your code, this works. 80869160

      Still I think the else Max = max(Max, recFun(dp,j)); is wrong. Imaging s[100] there is the max value of all s[]. At dp[200] there is some value!=1, say 42. In this case you will have dp[100]=42, too. And mayby dp[50]=43, what is completly wrong.

      So, after I removed that line it still not worked. The reason is that then not all dp states get calculated. Imagine the max s[] value at idx=1, then there is no recusion at all. So I changed the code that the recFun() is called for every index starting at n backwards to 1.

      → Ответить
»
5 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

The mistake is that it fails test case 2.

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

Maybe this is not the simplest test case, but here it goes:

1
16
4 5 6 1 6 6 6 2 6 6 6 6 6 6 6 3

(The only positions that matter here are the ones that don't contain 6)

Your output is 4, but answer is 3.

The reason is (I think)

else Max = max(Max, recFun(dp,j))

→ Ответить