Subtask 1: ~1 \leq n \leq 3~.

Nếu số lượng số lẻ lớn hơn ~1~ thì đáp án là ~\min(L, R)~. Độ phức tạp: ~O(1)~.

Subtask 2, 3: ~1 \leq n \leq 1000~

Ta chỉ quan tâm đến các số lẻ, gọi tập ~S = \{i_1, i_2, \dots, i_k\}~ là vị trí các số lẻ, ~o~ là số lượng số lẻ.

Ta chỉ truyền kẹo cho hai người lẻ bên cạnh, do đó gọi ~f(S)~ là tổng chi phí để truyền kẹo từ người ~i_j~ sang người ~i_{j+1}~ ~\forall j \in \{1, 3, 5, \dots\}~

• Nếu ~o~ chẵn: đáp án là ~g(S) = \min(f(S), f(S'))~ với ~S' = \{i_2, i_3, \dots, i_k, i_1\}~.
• Nếu ~o~ lẻ: Ta lựa một vị trí ~i_j~ để số kẹo ở đó cuối cùng là số lẻ. Tạo một tập ~S'~ không chứa ~i_j~, đáp án là ~\min(g(S'))~ ~\forall 1 \leq j \leq o~.

Độ phức tạp: ~O(n^2)~.

Vì sao với tập ~S~, không cần xét mọi hoán vị xoay vòng để tính, hay chứng minh tính đúng đắn của hàm ~g(S)~:

• Vì hàm ~f(S)~ chỉ xét các vị trí ~j~ chẵn, do đó khi xoay hoán vị đi ~1~ đơn vị thì sẽ làm thay đổi tính chẵn lẻ.
• Do đó với mọi hoán vị xoay vòng cũng chỉ tạo ra đúng hai tổ hợp cần tính, đó là ~f(S)~ và ~f(S')~.

Subtask 4: ~1 \leq n \leq 10^5~.

Ta cần tối ưu trường hợp ~o~ lẻ. Dựng ~S'~ gồm ~2.o~ phần tử và dùng prefix sum để tính trường hợp bỏ từng ~i_j~. Độ phức tạp: ~O(n)~.

Ta chỉ xét ~f(S')~ của prefix sum do giả sử ta muốn bỏ ~i_k~ và ghép ~i_{k-1}~ với ~i_{k+1}~ thì vô lý, vì rõ ràng truyền từ ~i_k~ đến ~i_{k+1}~ luôn tốt hơn.

Code tham khảo:

#define FOR(i,a,b) for(int i=(a); i<=(b); ++i)
#define REP(i, n) for(int i=0; i<(n); ++i)

int dist(int i, int j) {}

int numOdd = (int)odd.size();
auto calc = [&](vector<int> &odd) {
    ll res = 0;
    for(int i = 0; i < numOdd - 1; i += 2)
        res += dist(odd[i], odd[i + 1]);
    return res;
};

if (numOdd % 2 == 0) {
    ll tmp = calc(odd);
    odd.pb(odd[0]);
    odd.erase(odd.begin());
    cout << min(tmp, calc(odd));
} else {
    REP(i, numOdd) odd.pb(odd[i]);
    pref[1] = dist(odd[1], odd[0]);
    FOR(i, 2, 2 * numOdd - 1) pref[i] = pref[i - 2] + dist(odd[i], odd[i - 1]);
    ll res = INF;
    REP(notChoose, numOdd) minimize(res, pref[notChoose + numOdd - 1] - pref[notChoose]);
    cout << res;
}