Diamond Collector (Silver)

Debugging Help
#1

Problem Info

Diamond Collector (Silver) USACO

My Work

# Load data
diamonds = []
with open("diamond.in", "r") as input:
    n, k = list(map(int, input.readline().split()))
    for line in input:
        diamonds.append(int(line))

diamonds.sort()
diamonds.append(1000000001)
groups = []
max1 = 0
max2 = -1
set = 1
tester = diamonds[0]


# Iterate through the diamonds and find the 2 biggest groups where the difference between all the diamonds is less than k

for diamond in diamonds[1:]:
    if diamond - tester <= k:
        set += 1
    else:
        if max1 > max2:
            max2 = max(max2, set)
        else:
            max1 = max(max1, set)
        set = 1
        tester = diamond


# Add the 2 biggest group sizes together and write the answer to diamond.out
def write_answer(answer):
    with open("diamond.out", "w") as output:
        output.write(str(answer))


write_answer(max1 + max2)

My solution works by iterating through a sorted list of all the diamonds and checking if the current diamond minus the first diamond is greater than or equal to k and if so the program adds the length of the group so far to a list and starts a new group and then it returns the sum of the top two groups. Can someone please help me figure out what I did wrong?

What I’ve Tried

My solution only passes through the first two test cases and I tried downloading the test data but my program’s output seems to be lesser than the actual answer. I also tried to find a small dataset which it fails but was unable to.

Question

I am wondering if my logic behind my solution is wrong or if my implementation of it is wrong

#2

I don’t see you using the groups variable anywhere in your code. Is this intentional?

#3

Oops, yes this is intentional I was originally using it but later replaced it to optimize the code

#4

Try your code on this test case:

7 5
1
2
3
10
20
21
22
23

The answer should be 7, if I’m not mistaken.

#5

Oh my code outputs 4 instead of 7. This is actually really helpful, thanks!

1 Like
#6

Ok, I’ve updated my code and found that it forgets to count the very last group. This lets it solve test case 6 but still fails the others.