I don’t understand the surprisingly short and simple two pointers solution to A Huge Tower. The idea in the official editorial makes some sense; removing the largest sized block results in a valid tower at each step. If C[i] is the number of valid i-length towers, and T[i] is the number of ways to add the i-th largest block, then C[i] = C[i-1] * T[i]. I don’t see how this can be implemented with a single two pointers loop, though.
If A is the next block to insert, we want to place it above a block X such that A-D \le X \le A. We can move the x pointer until X = ar[x] is at least A-D. How does the following code do that?
Given internal solution:
int main () {
int n, d;
cin >> n >> d;
vector<int> ar(n);
for (int i = 0; i < n; i++) {
cin >> ar[i];
}
sort(ar.begin(), ar.end()); //sort the blocks
int r = 0, sol = 1;
for (int l = 0; l < n; l++) {
while (r < n - 1 && ar[r + 1] - ar[l] <= d) r++;
int dist = r - l + 1; //largest tower we can built when ar[l] block is the base
sol = (sol * 1LL * dist) % MOD;
}
cout << sol << '\n';
}
What are l and r? Why do we move r for a given l – which block are we inserting? Why is T[i] = r-l+1, the length of the longest subarray with difference at most D? I would appreciate it if you can help me dissect this solution and understand the key use of two pointers.
Thank you.
@BitLegion you solved this one, care to explain?
Maybe try to rephrase the official solution to understand it better. Here’s my attempt:
The observation that you can insert blocks from low to high in size makes counting the configurations feasible. By inserting the blocks from low to high in size, the only constraint you need to check is that A-D <= X, so it actually does not matter how the blocks are currently ordered. Therefore the number of ways for each new block A is a constant, so the answer is just a product of constants.
Next subproblem is to compute this constant for each new block A. Given a current block A, you need to find blocks X such that A >= X >= A-D. After sorting the blocks, this is a standard query that can be done in O(n) with two pointers or binary search (C++ lower_bound) per query in O(nlogn). Then A could be inserted above several different blocks: the number of ways is a difference of two pointers (plus 1 for possibility that A is inserted on the very bottom of the stack).
The comment in the code seems incorrect (or is it a different way of thinking about the problem?). In any case, the code is counting for each block how many different larger blocks it can be inserted below. This is the opposite direction of what the CEOI official solution is saying, but is actually equivalent (think about why).
Sidenote: To prove correctness, you also have to check that every possible tower can be produced in this way 1 time (to prove that the mapping of insertions to towers is a bijection, i.e. one-to-one). That’s why the solution mentions inserting and removing the largest block one at a time.
1 Like
Thank you for your detailed response. Your first two paragraphs about multiplying the number of ways and finding the constants using two pointers make sense.
I don’t follow this. Say we have a block i and a larger block j. The only restriction in putting j below i is having i \le d + j, which is already true since i \le j.
If you meant putting a smaller block below a larger block, say we put X underneath A. We need A-D \le X \le A, as you said. Since we put blocks from largest to smallest, we need to iterate the X pointer from largest to smallest as well (since A-D consistently decreases). However, both l and r are monotonically increasing in the internal solution.
In the internal solution, we check whether r+1 can be included in the range starting from l. Thus we use the interval [l, r] (inclusive on both ends). Then r-l doesn’t equal the number of elements in the subrange; it should be r-l+1? I think I am not following because I don’t know what the subrange represents.
I am still unable to grasp what exactly l and r mean. Is l the bigger block and r the smaller block we can add for each l? Also, where in the code do we insert the new block once we have a valid range? And why are we iterating through the blocks in order of least to greatest size?
Thanks in advance.
Yes, in the usaco.guide solution, it’s the reverse, putting smaller below larger, going from high to low. l is the smaller block, r is the larger. It does not matter whether we iterate over l and r increasing or decreasing, we’re just multiplying a bunch of counts for each l.
In any case the example solution is kind of confusing. It’s hard to wrap your head around different ways of iterating once you focus on one way. See my code here that implements exactly the CEOI official solution: https://ideone.com/HuYJqm . In my code r is the new larger block, l is the earliest OK old smaller block. It’s often simpler in many problems to iterate over the right edge and then advance the left edge. Removes one conditional (l < n) and often simplifies the condition checking (advance only if NOT ok).
Hi. The problem was definitely a little tricky. Think about it from a combinatorics perspective. If you can generate a strategy to find a solution by hand, you can easily apply in the code; they are very similar.
Simply put r and l are two pointers that both start at 0. As we iterate through l, we check the max value such that ar[r] is valid. This can only increase as l increases, because the array is sorted. Then, we simply know that the largest tower that we can now build is r - l + 1 because that’s the number of cubes from the left pointer to the right pointer inclusive. Then we multiply this with the solution, as there are the many combinations for this.
1 Like