Carrot Distribution I

Intuitively, you might be doing this :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

from urllib2 import urlopen
source = urlopen("https://pastebin.com/raw/fpbCnELC")

curr = 0    # the amount of carrots you give to the current villager
prev = 0    # the amount of carrots you gave to the previous villager
villagers = 0
for i in range(1000):
    curr += int(source.readline())
    if curr >= prev:    # move to the next people, the curr becomes prev
        prev = curr
        curr = 0
        villagers += 1

print villagers

In other words, each time you give a villager the number of bags until the amount of carrots is more than or equal to the one in front, but that's not always the case. Consider the following input : 2 1 3 3 .

Using the algorithm above, you will give the first villager the first bag, the second villager the second, third and forth bag (so the sum 7 > 2). You can only satisfy 2 people.

However, the optimal solution is to give the first villager the first and second bag, the second villager the third bag and the last villager the forth bag. Like this you can satisfy 3 people.

In conclusion, you don't always greedily give the carrots until it exceeds the one in front of you. Instead, we should use Dynamic Programming.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

dp[0] = 0; last[0] = 0;
for (int i = 1; i <= N; i++) {
    for (int j = i-1; j >= 0; j--) {
        if (ps[i] - ps[j] >= last[j]) {
            dp[i] = dp[j] + 1;
            last[i] = ps[i] - ps[j];
            break;
        }
    }
}

dp[i] stores the maximum number of villagers you can satisfy until the $i$ -th bag. last[i] stores the number of carrots the $i$ -th villager got.

The transition is simple. First observe that dp[i] <= dp[j] for all $i < j$ (how can you satisfy less people when you have more bags right?). Hence when we are computing dp[k] we move down until the sum is larger than the previous one. Now, we can break because going down further will not give us a higher dp[k] but larger last[k] . Finally, print dp[N] .