We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Prepare
- Algorithms
- Recursion
- Repetitive K-Sums
- Discussions
Repetitive K-Sums
Repetitive K-Sums
+ 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)
+ 0 comments what is the running time for this problem ?
+ 1 comment I think the note on the max. number of number on any line is at most should be stated in the 'constraints' section. Currently, the constraints section doesn't impose constraints that allow realistic runtimes (i.e. is a possible runtime).
+ 0 comments Not the prettiest code, but it gets the job done:
import java.util.Arrays; import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class RepetitiveKSums { private static int nextIndex(Map<Long, Long> expectedCounts, int currentIndex, long[] values) { long currentValue = values[currentIndex]; long previousValue = currentValue; while (true) { if (expectedCounts.containsKey(previousValue) && expectedCounts.get(previousValue) != 0L) { currentIndex += expectedCounts.get(previousValue); expectedCounts.put(previousValue, 0L); } else { break; } if (previousValue == values[currentIndex]) { break; } previousValue = values[currentIndex]; } return currentIndex; } private static void solve(long[] values, long[] sequence, long kSums, int sequenceIndex, int valueIndex, Map<Long, Long> expectedCounts) { if (sequenceIndex >= sequence.length) { return; } int index = nextIndex(expectedCounts, valueIndex, values); if (sequenceIndex == 0) { sequence[sequenceIndex] = values[index] / kSums; } else { sequence[sequenceIndex] = values[index] - (sequence[0] * (kSums - 1)); } addExpectedCounts(sequence, sequenceIndex, expectedCounts, kSums - 1, sequence[sequenceIndex], 0); sequenceIndex++; solve(values, sequence, kSums, sequenceIndex, index, expectedCounts); } public static void addExpectedCounts(long[] sequence, int sequenceIndex, Map<Long, Long> expectedCounts, long numberInSum, long sumSoFar, int startIndex) { if (numberInSum == 0) { long expect = expectedCounts.containsKey(sumSoFar) ? expectedCounts.get(sumSoFar) + 1 : 1; expectedCounts.put(sumSoFar, expect); return; } for (int i = startIndex; i <= sequenceIndex; i++) { long innerSum = sumSoFar + sequence[i]; addExpectedCounts(sequence, sequenceIndex, expectedCounts, numberInSum - 1, innerSum, i); } } public static void main(String[] args) { Scanner scn = new Scanner(System.in); int cases = scn.nextInt(); for (int i = 0; i < cases; i++) { int numberInSequence = scn.nextInt(); long kSums = scn.nextLong(); scn.nextLine(); long[] values = Arrays.stream(scn.nextLine().trim().split(" ")).mapToLong(Long::valueOf).toArray(); Arrays.sort(values); long[] sequence = new long[numberInSequence]; solve(values, sequence, kSums, 0, 0, new HashMap<>()); for (long val : sequence) { System.out.print(val + " "); } System.out.println(); } scn.close(); } }
+ 0 comments A small test case to clarify certain misconception:
input:
2 3 2 2 4 5 6 7 8 3 2 2 4 6 8 10 14
output:
1 3 4 1 3 7
Load more conversations
Sort 28 Discussions, By:
Please Login in order to post a comment