AHAHAHAHA I THREW DEC GOLD SO HARD
only managed to cumulatively solve one problem, that's how sad i am
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 starts
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 * N^2), which is def too slow ahahahah
tbh the main reason this problem's so hard is bc it just... seems to 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 the answer in the interval of [3, 8]
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 m 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, obviously)
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 this
it still works
and now we have our final complexity of O(N + M^2)!
implementation here:
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 final 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);
}
}