FifthThread's blog

By FifthThread, 3 years ago, In English

I was doing this Problem on codeforces. It was a dynamic programming question and I am fairly new to dynamic programming.

I wrote a code whose main part is below

n,m,b,mod = li()
a = li()
dp = [[0 for i in range(b+1)] for j in range(m+1)] 
dp[0][0]=1
for i in range(n):
    for j in range(1,m+1):
        for k in range(b+1):
            if k-a[i]>=0:
                dp[j][k]+=dp[j-1][k-a[i]]
ans = 0
for j in range(b+1):
    ans+= dp[m][j]
print(ans%mod)

This was giving the correct output. But when I move the first loop to the end, then it gives the wrong answer.

for j in range(1,m+1):
    for k in range(b+1):
        for i in range(n):
            if k-a[i]>=0:
                dp[j][k]+=dp[j-1][k-a[i]]

The above code is giving incorrect output. Can anybody help me in understanding why does the loop orientation matters in this case.

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
3 years ago, # |
Rev. 2   Vote: I like it +44 Vote: I do not like it

In the problem statement author write that $$$i-th$$$ programmer write $$$V_i$$$ lines consecutive and he write code earlier than $$$(i + 1)-th$$$ programmer, but in the second solution programmer don't write lines of code consecutive, and $$$(i + 1)-th$$$ coder can write code earlier than $$$i-th$$$ coder.

For example test:

$$$2$$$ $$$3$$$ $$$0$$$ $$$10000000$$$

$$$0$$$ $$$0$$$

Solution number 1 print 4: "1 1 2", "1 2 2", "1 1 1", "2 2 2".

Solution number 2 print 8: "1 1 2", "1 2 2", "1 1 1", "2 2 2", "2 1 1", "2 2 1", "1 2 1", "2 1 2".

We can observate that second solution count incorrect answers.