my friends kept on asking me for help on this one silver problem, and to be fair, it is pretty hard the fact that benq's editorial reads like some post-college math paper doesn't help either
(my solution requires knowledge of prefix sums tho)
but without further ado, here's my solution
we have a crap ton of intervals (between 0 and 5000, this will come in use later)
and for...each number in the range...0 to 10k, we want...the number of pairs of intervals whose
start values sum to at most that number and ends sum to at least that number? wth, benq?
now the pleb's method would be a standard brute force to iterate through each number and then legit go through all pairs of intervals to see what the answer is- that's \(O(M \cdot N^2)\), which is def too slow ahahahah
tbh the main reason this problem's so hard is bc it just... seems too abstract, yknow?
so let's try and make it, well, not so abstract.
let's first think about it from the interval pair's perspective
we'll use the sample input's `[1, 3]` and `[2, 5]` as our example
they sum to the interval `[3, 8]`
notice! that this pair contributes exactly 1 to every answer within `[3, 8]`
what this means is that because this interval exists,
every \(k\) value in `[3, 8]` is now 1 greater
and this is exactly the case for all the other interval pairs
try it yourself, i swear it works
now we can just iterate through all interval pairs and do a prefix sum thing at the end to
get all the numbers we need in one fell swoop in ...\(O(M + N^2)\)? that's kinda better? i guess?
look i swear this works, we just need to iterate through all pairs w/o iterating through all the pairs
i know it's hard, but there is a method to do it
this is where the intervals being less than 5000 comes into play
ok so first of all, we just need to increment the start & end (because it's prefix sums)
because of this, let's try processing multiple start-pairs and multiple end-pairs at the same time!
this code below has `startNum` and `endNum`- the first keeps track of the number
of intervals that start at a given location while the second does the same for the endings
now we can just iterate through all pairs of starting locations and all pairs of
ending locations and increment our prefix sums array accordingly
note that this does treat the start and end of each interval almost like completely separately,
but it still works
and now we have our final complexity of O(N + M^2)!
implementation here:
```java import java.io.*; import java.util.*; /** * 2021 dec silver * 2 5 * 1 3 * 2 5 * should output these numbers, each on a new line: * [0, 0, 1, 3, 4, 4, 4, 3, 3, 1, 1] */ public class ConvIntervals { public static void main(String[] args) throws IOException { long start = System.currentTimeMillis(); BufferedReader read = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer initial = new StringTokenizer(read.readLine()); int intervalNum = Integer.parseInt(initial.nextToken()); int maxMag = Integer.parseInt(initial.nextToken()); int[] startNum = new int[maxMag + 1]; int[] endNum = new int[maxMag + 1]; for (int i = 0; i < intervalNum; i++) { int[] interval = Arrays.stream(read.readLine().split(" ")).mapToInt(Integer::parseInt).toArray(); if (interval[0] > interval[1]) { throw new IllegalArgumentException("invalid interval i hate you"); } startNum[interval[0]]++; endNum[interval[1]]++; } long[] coveredNum = new long[2 * maxMag + 2]; for (int i = 0; i <= maxMag; i++) { for (int j = 0; j <= maxMag; j++) { coveredNum[i + j] += (long) startNum[i] * startNum[j]; coveredNum[i + j + 1] -= (long) endNum[i] * endNum[j]; } } // get the actual array from the initial stuff we constructed long currAmt = 0; for (int i = 0; i <= 2 * maxMag; i++) { currAmt += coveredNum[i]; coveredNum[i] = currAmt; } StringBuilder ans = new StringBuilder(); for (int i = 0; i <= 2 * maxMag; i++) { ans.append(coveredNum[i]).append('\n'); } System.out.print(ans); System.err.printf("it took %d ms, i hope you're happy", System.currentTimeMillis() - start); } } ```