i have a problem with this task
Suppose a sequence of integer numbers is given. If there exist three or more consecutive equal numbers in this sequence, the first group of such equal numbers is removed from the sequence. Such operation is repeated with the obtained sequence until there is nothing to remove. Compute the quantity of the items that will be removed. using STL stack Complexity must be O(n).
Example 1. In sequence {2, 3, 3, 3, 1}, the first group of equal numbers is {3, 3, 3}. After groups’ removal, the sequence will be {2, 1}, and there is nothing to remove.
Example 2. In sequence {3, 2, 2, 2, 3, 3, 3}, the first group of numbers to remove is {2, 2, 2}. Then the sequence will be {3, 3, 3, 3}, hence it is possible to remove the whole sequence.
i try make smth like this, it work if group lenth is only 3, but it very slow, and tests throw TIME OUT
#include <cstdio>
#include <stack>
int main()
{
int x, res = 0;
std::stack<int> st, tmp_st;
scanf_s("%d", &x);
while (x != -1) {
st.push(x);
tmp_st = st;
while ((!tmp_st.empty()) && st.top() == tmp_st.top()) {
tmp_st.pop();
}
if (st.size() - tmp_st.size() == 3) {
res += 3;
st.swap(tmp_st);
}
scanf_s("%d", &x);
}
printf("%d", res);
return 0;
}
UPD: "static" is not needed here
about my decision: each time an item is added, I save a copy of the original stack and look at how many times the item that was added occurred before in a row, if this number is equal to 3 (to be more, I need to improve the condition) then the items are also removed from the original stack, and the number of deleted items I output at the end in the standard output stream, also in the condition in the input can only be numbers from 0 to 9
UPD2: i make it work, but its steel slow
#include <cstdio>
#include <stack>
int main()
{
int x = 0, res = 0, n = 1;
std::stack<int> st, tmp_st;
while ((x != -1)) {
scanf_s("%d", &x);
if (st.empty()) {
n = 1;
st.emplace(x);
continue;
}
if (x != st.top()) {
if (n > 2) {
res += n;
st.pop();
if (!tmp_st.empty()) {
n = tmp_st.top();
tmp_st.pop();
if (x == st.top()) ++n;
continue;
}
st.emplace(x);
n = 1;
continue;
}
tmp_st.emplace(n);
st.emplace(x);
n = 1;
}
else {
++n;
continue;
}
}
printf("%d", res);
return 0;
}
I’m going to assume an “asymmetry” in the task, in particular that reversing the input may not, in general, yield a reverse of the result:
{ 3 2 2 2 3 3 3 } → { 3 3 3 3 } → { }{ 3 3 3 2 2 2 3 } → { 2 2 2 3 } → { 3 }In other words, you are not required to backtrack for an “optimal” (by the highest number of removed items) ordering of removals, but can instead take a “greedy” approach: Remove the first “removable” (long enough) sequence and repeat.
This↑↑↑ assumption is hugely important, because it makes a difference between an O(n) problem and an O(n²) problem.
One possible approach would be a cycle that
item,item to the top of the stack, and
item to the stack,items on the stack is big enough,
removed items, and thenitem to the stack.The implementation has a few distracting technicalities, such as “pre-collapsing” using a counter (top_count). But it is easy to see that the outer loop runs O(n) times and the inner loop does not increase the complexity, because (1) it cannot pop the stack more times than the number of items read from the input and (2) all code paths that don’t pop the stack cause the inner loop to exit. (The argument is quite similar to why Aho-Corasick is linear, just way simpler in this case.)
This example lacks input error checking for the sake of brevity.
#include <cstdint>
#include <iostream>
#include <stack>
#include <tuple>
namespace {
constexpr std::size_t LIMIT{3};
std::size_t count_removed(std::istream& input) {
std::stack<std::tuple<int, std::size_t>> stack;
int item;
if (input >> item) {
stack.emplace(item, 1);
} else {
return 0;
}
std::size_t removed{};
while (input >> item) {
for (;;) {
auto& [top_item, top_count]{stack.top()};
if (item == top_item) {
++top_count;
break;
} else if (top_count >= LIMIT) {
removed += top_count;
stack.pop();
if (!stack.empty()) continue;
}
stack.emplace(item, 1);
break;
}
}
const auto& [top_item, top_count]{stack.top()};
if (top_count >= LIMIT) removed += top_count;
return removed;
}
} // namespace
int main() { std::cout << count_removed(std::cin) << '\n'; }
{ } → 0 (/0){ 1 } → 0 (/1){ 1 1 } → 0 (/2){ 1 1 1 } → 3 (/3){ }{ 1 1 1 1 } → 4 (/4){ }{ 3 2 2 2 3 3 3 } → 7 (/7){ 3 3 3 3 }{ }{ 3 3 3 2 2 2 3 } → 6 (/7){ 2 2 2 3 }{ 3 }{ 1 1 2 2 2 1 1 } → 7 (/7){ 1 1 1 1 }{ }{ 1 1 1 2 2 1 1 1 } → 6 (/8){ 2 2 1 1 1 }{ 2 2 }{ 1 1 2 2 2 1 1 1 2 2 } → 8 (/10){ 1 1 1 1 1 2 2 }{ 2 2 }{ 0 0 1 2 2 3 4 4 5 5 4 3 3 2 1 1 0 } → 0 (/17){ 0 0 1 2 2 3 4 4 5 5 5 4 3 3 2 1 1 0 } → 18 (/18){ 0 0 1 2 2 3 4 4 4 3 3 2 1 1 0 }{ 0 0 1 2 2 3 3 3 2 1 1 0 }{ 0 0 1 2 2 2 1 1 0 }{ 0 0 1 1 1 0 }{ 0 0 0 }{ }{ 0 1 1 2 2 2 3 3 3 3 2 2 2 1 1 4 4 4 4 } → 18 (/19){ 0 1 1 3 3 3 3 2 2 2 1 1 4 4 4 4 }{ 0 1 1 2 2 2 1 1 4 4 4 4 }{ 0 1 1 1 1 4 4 4 4 }{ 0 4 4 4 4 }{ 0 }{ 0 0 1 2 2 3 3 3 2 1 1 2 2 3 3 3 2 1 0 } → 15 (/19){ 0 0 1 2 2 2 1 1 2 2 3 3 3 2 1 0 }{ 0 0 1 1 1 2 2 3 3 3 2 1 0 }{ 0 0 2 2 3 3 3 2 1 0 }{ 0 0 2 2 2 1 0 }{ 0 0 1 0 }{ 1 1 2 2 3 3 3 4 3 3 3 2 1 } → 6 (/13){ 1 1 2 2 4 3 3 3 2 1 }{ 1 1 2 2 4 2 1 }{ 1 1 2 2 3 3 3 2 3 3 3 2 1 } → 9 (/13){ 1 1 2 2 2 3 3 3 2 1 }{ 1 1 3 3 3 2 1 }{ 1 1 2 1 }{ 1 1 2 3 3 3 2 3 3 3 2 1 1 } → 13 (/13){ 1 1 2 2 3 3 3 2 1 1 }{ 1 1 2 2 2 1 1 }{ 1 1 1 1 }{ }