2232 C2. Seating Arrangement (Hard Version)

Problem Overview

Alice wants to seat as many friends as possible at her party. The friends are lined up and must be seated in the exact order they arrive. Each table has $s$ seats, and there are $x$ tables.

Friends have one of three personalities:

• Introverts (I): Must sit at an empty table.
• Extroverts (E): Must sit at a non-empty table.
• Ambiverts (A): Can sit anywhere.

Once a person is seated, they cannot be moved.

The Problem with Strict Greed

If we try to process the line strictly greedily, we will run into issues when we have an Extrovert (E) but all current tables are full or empty.

Imagine a table has $s=2$ seats, and our line is A, A, E, E.

Total seated: 2

However, we could have done better! If the second A had sat at a new empty table instead of joining the first A, both Es could have joined them!

Total seated: 4.

But we are forced to process friends in order, and we can't look into the future. How do we know when an A should join an existing table versus open a new one?

Greedy with Regret

We can solve this using a powerful technique called Greedy with Regret. We will always seat people as compactly as possible, but we will keep track of a "regret" state—specifically, how many Ambiverts (A) we can conceptually "move" to a new table later if we desperately need to open one for an Extrovert (E).

The Core Invariants

1. Waitlisting Introverts: Since Is require an empty table, their only real purpose (other than just taking up a seat) is to serve as table-openers for Es. So when we see an I, we don't seat them immediately. We add them to an introvert_count waitlist. If we ever need to open a table for an E (or an A), we pull an I from the waitlist and seat them together!

2. The Ambivert Move (Regret): If an A joins a table that already has someone at it, we increment an ambivert_count. Why? Because if we ever need to open a new table for an E, we can conceptually pull this A away from their current table and use them to open the new table! Since the A wasn't the first person at their old table, leaving it will not leave the old table empty, so no rules are broken!

   Before: Stored Regret

   Table 0 has two Ambiverts. The second 'A' joined a non-empty table, so they are marked as movable (ambivert_count = 1).

   0

   A

   1

   A

   2

   E

   After: Executing the Regret

   An Extrovert needs a table! We conceptually move the second 'A' to Table 1 so the 'E' can sit with them. Table 0 still has the first 'A', so no rules were broken!

   0

   A

   1

   A

   2

   E

The Step-by-Step Logic

For each person in the line, we look at the current active table j:

• If 'I': Add them to the waitlist (introvert_count++).

• If 'E':

  1. Join: If the current table is not empty and not full, seat them.
  2. Pair with I: If the table is empty and we have an I waitlisted, seat the I and E together.
  3. Regret an A: If the table is empty and we have an A we can move (ambivert_count > 0), conceptually move the A to the new table, and seat the E with them.
  4. Otherwise, kick them out.

• If 'A':

  1. Join: If the current table is not empty and not full, seat them. This A can be moved later, so ambivert_count++.
  2. Pair with I: If the table is empty and we have an I waitlisted, seat the I and A together. This A can be moved later, so ambivert_count++.
  3. Sit Alone: If the table is empty and no Is are waiting, sit the A alone. They cannot be moved later (since they are the only person at the table).

After processing everyone, any Is left on the waitlist can safely take any remaining empty tables!

Pseudocode

Before writing the final code, here is exactly how we maintain our state:

1. Initialize counters:
   - introvert_count = 0
   - ambivert_count = 0
   - seated = 0
   - j = 0 (our current table index)
   - chairs = array of size x, all 0s

2. Loop through each person in the string:
   - If 'I': introvert_count++

   - If 'E':
     - If chairs[j] > 0 and chairs[j] < s:
       Seat E. (chairs[j]++, seated++)
     - Else if chairs[j] == 0 and introvert_count > 0 and s > 1:
       Seat I and E. (introvert_count--, chairs[j] += 2, seated += 2)
     - Else if chairs[j] == 0 and ambivert_count > 0:
       Move A and seat E. (ambivert_count--, chairs[j]++, seated++)

   - If 'A':
     - If chairs[j] > 0 and chairs[j] < s:
       Seat A. (chairs[j]++, seated++, ambivert_count++)
     - Else if chairs[j] == 0:
       - If introvert_count > 0 and s > 1:
         Seat I and A. (introvert_count--, chairs[j] += 2, seated += 2, ambivert_count++)
       - Else:
         Seat A alone. (chairs[j]++, seated++)

   - After every successful seating, if chairs[j] == s, move to the next table (j++).

3. Clean up:
   - While introvert_count > 0 and we have empty tables left, seat the I's alone.

Solution Code

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void solve() {
int n, x, s;
cin >> n >> x >> s;
string arr;
cin >> arr;

    vector<int> chairs(x, 0);
    int j = 0;
    int introvert_count = 0;
    int ambivert_count = 0;
    int seated = 0;

    for (int i = 0; i < n; i++) {
        if (arr[i] == 'I') {
            introvert_count++;
        } else if (arr[i] == 'E') {
            if (j < x && chairs[j] != 0 && chairs[j] < s) {
                chairs[j]++;
                seated++;
                if (chairs[j] == s && j < x - 1) j++;
            } else if (j < x && chairs[j] == 0 && introvert_count > 0 && s > 1) {
                introvert_count--;
                chairs[j] += 2;
                seated += 2;
                if (chairs[j] == s && j < x - 1) j++;
            } else if (j < x && chairs[j] == 0 && ambivert_count > 0) {
                ambivert_count--;
                chairs[j]++;
                seated++;
                if (chairs[j] == s && j < x - 1) j++;
            }
        } else if (arr[i] == 'A') {
            if (j < x && chairs[j] != 0 && chairs[j] < s) {
                chairs[j]++;
                seated++;
                ambivert_count++;
                if (chairs[j] == s && j < x - 1) j++;
            } else if (j < x && chairs[j] == 0) {
                if (introvert_count > 0 && s > 1) {
                    introvert_count--;
                    chairs[j] += 2;
                    seated += 2;
                    ambivert_count++;
                    if (chairs[j] == s && j < x - 1) j++;
                } else {
                    chairs[j]++;
                    seated++;
                    if (chairs[j] == s && j < x - 1) j++;
                }
            }
        }
    }

    while (introvert_count > 0 && j < x) {
        if (chairs[j] == 0) {
            introvert_count--;
            seated++;
        }
        j++;
    }

    cout << seated << "\n";

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
if (cin >> t) {
while (t--) solve();
}
return 0;
}