- Prepare
- Algorithms
- Recursion
- Repetitive K-Sums
- Discussions

# Repetitive K-Sums

# Repetitive K-Sums

+ 0 comments This problem doesn't test the performance of your solution nearly as much as I was expecting. I was expecting to pass half of the test cases at most on my first submission, since I hadn't optimized it at all yet, but it turns out unoptimized is good enough.

+ 0 comments If there are several possible outputs you can output any of them.

The verification seems picky about which duplications are OK!?

+ 0 comments Would love an example where k > 2 and n > 1. How is 3-sum done?

n = 4 k = 3 a[1]+a[1]+a[1]? Then what? a[1]+a[1]+a[2] a[1]+a[1]+a[3] a[1]+a[1]+a[4] a[1]+a[2]+a[2] a[1]+a[2]+a[3] a[1]+a[2]+a[4] a[1]+a[3]+a[3] a[1]+a[3]+a[4] a[1]+a[4]+a[4] a[2]+a[2]+a[2] a[2]+a[2]+a[3] a[2]+a[2]+a[4] a[2]+a[3]+a[3] a[2]+a[3]+a[4] a[2]+a[4]+a[4] a[3]+a[3]+a[3] a[3]+a[3]+a[4] a[3]+a[4]+a[4] a[4]+a[4]+a[4]

+ 0 comments With T apparently only limited to 10**5 and a limit of 10**5 items in an input sequence, there's a possibility that we'd have to read in 10**10 numbers, which would almost certainly not be possible in the given time.

Though it's mostly common-sense, most problems would mention this constraint explicitly, so here goes:

None of the testcases (I've tried them all!) require you to read in more than 100000 input sequence elements totalled across all T of that testcases' input sequences (in fact, 98280 (testcase 04) seems to be the largest total number of input sequence elements you'll need to read in).

In fact (spoiler!) - no testcase has T > 100!

+ 1 comment If you use pythons itertools module this question becomes pretty simple. No more DP, recursion, or array resizing necessary!

from itertools import combinations_with_replacement as cwr if __name__ == '__main__': for _ in range(int(input())): n, k = list(map(int, input().rstrip().split())) a = sorted(list(map(int, input().rstrip().split()))) values = [a[0]//k] combinations = {} for i in a[1:]: if combinations.setdefault(i,0) > 0: combinations[i] -= 1 else: combinations[i] -= 1 new_val = i - (values[0]*(k-1)) for j in range(k): for new_comb in map(lambda x: (k-j)*new_val + sum(x), cwr(values, j)): combinations[new_comb] = combinations.get(new_comb, 0) + 1 values.append(new_val) print(*values)

Sort 27 Discussions, By:

Please Login in order to post a comment