Codeforces: B. Taxi

The problem is from codeforces http://www.codeforces.com/problemset/problem/158/B

Solution is easy: First you need to sort the group numbers in desending order. You create two index pointers, pointing to the start and the end. These two pointers move towards each other. Every time you check if there is more room for other groups, you do this by looping the other pointer from the end towards the start. Every loop you increment the answer by one. This is what is called [Greedy Algorithm]. Always pick the smallest (or largest). You first put the biggest group and use the remaining room to put as many smaller groups as possible.

The python solution is as follows, The first time I forgot to put the range check on the second pointer, which leads to a runtime error.

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

n = int(raw_input())
s = raw_input().split(" ")
s.sort(reverse = True)
ans = 0
i = 0
j = len(s) - 1
 
while i <= j:
    ans += 1
    four = 4 - int(s[i])
    while (int(s[j]) <= four) and (j >= i):
        four -= int(s[j])
        j -= 1
    i += 1
 
print ans

n = int(raw_input())
s = raw_input().split(" ")
s.sort(reverse = True)
ans = 0
i = 0
j = len(s) - 1

while i <= j:
    ans += 1
    four = 4 - int(s[i])
    while (int(s[j]) <= four) and (j >= i):
        four -= int(s[j])
        j -= 1
    i += 1

print ans

You probably notice that it is a bit awkward to convert a list of string to a list of integers on the fly, as presented in the python solution above. Well, you can use the following for conversion.

1
2

s = [int(i) for i in s]
s = map(int, s)

s = [int(i) for i in s]
s = map(int, s)

The improved solution in python is thus:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

n = int(raw_input(""))
s = raw_input("").split(" ")
s.sort(reverse=True)
 
s = [int(i) for i in s]
# or use below
# s = map(int, s)
 
ans = 0
i = 0
j = len(s) - 1
 
while i <= j:
    ans += 1
    four = 4 - s[i]
    while (s[j] <= four) and (j >= i):
        four -= s[j]
        j -= 1
    i += 1
 
print ans

n = int(raw_input(""))
s = raw_input("").split(" ")
s.sort(reverse=True)

s = [int(i) for i in s]
# or use below
# s = map(int, s)

ans = 0
i = 0
j = len(s) - 1

while i <= j:
    ans += 1
    four = 4 - s[i]
    while (s[j] <= four) and (j >= i):
        four -= s[j]
        j -= 1
    i += 1

print ans

–EOF (The Ultimate Computing & Technology Blog) —