My Observation for C — Arrange the Numbers in a Circle

Solved C in today's Div2 and wanted to share my observation/approach.

Let:

• ones = number of values equal to 1
• others = total count of all values greater than 1
• cap = maximum number of 1s we can safely insert

The key observation is:

If a value appears x times (x > 1), then while keeping the condition valid, we can place at most

[ \left\lfloor \frac{x-2}{2} \right\rfloor ]

ones between its occurrences.

Why?

Because every triple of consecutive cards must contain at least two equal values.

So between separating 1s, we need at least two equal numbers together.

For example:

6 6 1 6 6 1

works because every consecutive triple contains at least two 6s.

But:

6 1 6 1 6

does NOT work, since triples like:

6 1 6

break the condition.

So each number contributes some "capacity" for accommodating ones.

For every a[i] > 3, we add:

(a[i] - 2) / 2

to the total capacity.

Case 1

Total usable cards are less than 3.

ones + others < 3

Answer = 0

Case 2

We have enough capacity to place all ones.

cap >= ones

Then we can use every card.

Answer:

others + ones

Case 3

We do NOT have enough capacity.

Then some ones cannot be used.

Normally answer becomes:

others + cap

But there is one important circular edge case.

If all values except one are 1s, we can actually fit one extra 1 because the arrangement is circular.

Example:

Counts:

1 1 4

Possible arrangement:

1 3 3 1 3 3

Now check the wraparound triples too:

3 1 3
3 3 1
1 3 3

All valid.

Circularly it looks like:

        1
     /     \
    3       3
    |       |
    3       1
     \     /
        3

This extra placement only works because the starting and ending values connect through the circle.

So when:

ones == n - 1

we add one extra.

Final answer:

others + cap + 1

Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int multTestQ;
    cin >> multTestQ;

    while (multTestQ--) {
        ll n, ones = 0, cap = 0, others = 0;
        cin >> n;

        vector<ll> a(n);

        for (int i = 0; i < n; i++) {
            cin >> a[i];

            if (a[i] == 1) {
                ones++;
            }
            else {
                others += a[i];

                if (a[i] > 3) {
                    cap += (a[i] - 2) / 2;
                }
            }
        }

        if (ones + others < 3) {
            cout << 0 << '\n';
        }
        else if (cap < ones) {
            if (ones == n - 1) {
                cout << others + cap + 1 << '\n';
            }
            else {
                cout << others + cap << '\n';
            }
        }
        else {
            cout << others + ones << '\n';
        }
    }

    return 0;
}