wow another solution in just a day
does anyone even read these
but anyways i did this, and it basically gives you an array of \(10^5\) elements and a target \(n \le 1000\) and then it asks you to find the smallest segment that has a subset which sums to that given target
this problem is really stupid because it asks for like this one really niche method of using two pointers
so to understand this method, let's do a simpler problem
you have some array of numbers blah blah blah find the longest
segment whose (max - min) is less than some given number
so you can just be a normal person and 2P this problem w/ a priority queue, stuff like that
but that gives you an extra \(\log N\) factor and god forbid your code have one of those
so what do we do to remove this pesky log factor?
first let's define a stack data structure that can support max and min queries in O(1)
along with the standard push and pop
coding this is pretty ez as all you need to do is define two extra stacks along with the actual stack that contain the maximums and minimums of all the numbers below them
so for example if we had a stack that was like `[3, 1, 4, 5, 2, 7]`, the max stack would be `[3, 3, 4, 5, 5, 7]` and the min stack would be `[3, 1, 1, 1, 1, 1]`
then we can do the same 2P thing but instead have 2 stacks- something like this: ``` [===================([T---B][B------T])=====================] ``` where `T` and `B` represent the top and bottom of the stack respectively
then when doing the classic 2P method, we can just push into the right stack and pop from the left stack as the
pointers direct us to do
(if the left stack is empty when we pop it,
we can just move all the elements from the right stack to the left stack then pop it)
and to get the max and min of the segment, we can just combine the max and mins of the two stacks
and that overly convoluted method is how you solve that problem in linear time
but coming off of this problem we can use the same 2-stack method to solve this subset sum problem
just store all possible sums on the stack instead of the max and min using some dp techniques
then you do the 2P method with said 2 stacks in basically the same way as the simpler problem and win
no like seriously does anyone read these
```cpp #include <iostream> #include <cassert> #include <bitset> #include <vector> #include <algorithm> using std::cout; using std::endl; using std::vector; using std::bitset; constexpr int MAX_TARGET = 1e3; class SumStack { // length is MAX_TARGET + 1 to account for 0 using SumSet = bitset<MAX_TARGET + 1>; private: const int max_sum; vector<int> stack{0}; // using raw vectors might be too slow, so i use bitsets instead vector<SumSet> sum_stack{SumSet()}; public: SumStack(int max_sum) : max_sum(max_sum) { sum_stack.back()[0] = 1; } void push(int val) { stack.push_back(val); SumSet new_sums = sum_stack.back(); // calculate the new values that can be achieved for (int i = max_sum; i >= val; i--) { new_sums[i] = new_sums[i] || new_sums[i - val]; } sum_stack.push_back(new_sums); } int pop() { sum_stack.pop_back(); int top = stack.back(); stack.pop_back(); return top; } bool empty() { return stack.size() == 1; } const SumSet top_sums() { return sum_stack.back(); } }; // reverses a bitset in [from, to) (totally not copied from stackoverflow) template<std::size_t N> void reverse(bitset<N>& b, int from=0, int to=N) { for (std::size_t i = from; i < from + (from + to + 1) / 2; i++) { bool temp = b[i]; b[i] = b[to - i - 1]; b[to - i - 1] = temp; } } /** * https://codeforces.com/edu/course/2/lesson/9/3/practice/contest/307094/problem/I * 10 100 * 14 33 22 21 11 5 13 28 61 2 should output 5 */ int main() { int size; int target; std::cin >> size >> target; assert(target <= MAX_TARGET); vector<int> arr(size); for (int& i : arr) { std::cin >> i; assert(i <= target); } SumStack left_stack(target); SumStack right_stack(target); auto achievable_sum = [&] () -> bool { // get the achievable sums of the left and right stack auto left = left_stack.top_sums(); auto right = right_stack.top_sums(); // reverse the left bitset to match up the sums with the right sums reverse(left, 0, target + 1); // now, when we combine the two, any set bit // will represent a subset that sums to the target return (bool) (left & right).count(); }; left_stack.push(arr[0]); int right = 0; int min_good = INT32_MAX; for (int left = 0; left < size; left++) { if (left > 0) { if (left_stack.empty()) { // move everything from the right to the left while (!right_stack.empty()) { left_stack.push(right_stack.pop()); } } left_stack.pop(); } // while we can't achieve the subset sum, move the pointer to the right while (right < size - 1 && !achievable_sum()) { right++; right_stack.push(arr[right]); } if (achievable_sum()) { min_good = std::min(min_good, right - left + 1); } } cout << (min_good == INT32_MAX ? -1 : min_good) << endl; } ```