USACO 2022 February Contest Bronze Division - Sleeping in Class

Problem link: here

Solution Author: Stefan Dascalescu

Problem Solution

We can try each divisor of the sum and see the maximum number of equal groups we can obtain, while also being careful to not miss out on groups of people who form less time than the threshold.

In order to check the validity of a split in groups, we can apply a relatively simple greedy algorithm.

Source codes

The source codes in C++ and Python can be seen below.

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

int main() 
{
    int t;
    cin >> t;

    while(t--)
    {
        int n;
        cin >> n;
        vector<int> v(n+1);
        int sum = 0;
        for(int i = 1; i <= n; i++)
            cin >> v[i], sum += v[i];
        int ans = n-1;
        if(sum == 0)
        {
            cout << 0 << '\n';
            continue;
        }
        for(int i = 1; i <= 1000000; i++)
        {
            if(sum % i == 0)
            {
                int cnt = 0;
                bool ok = 1;
                int sum = 0;
                for(int j = 1; j <= n; j++)
                {
                    sum += v[j];
                    if(sum > i)
                    {
                        ok = 0;
                        break;
                    }
                    if(sum == i)
                        sum = 0, cnt++;
                }
                if(ok)
                    ans = min(ans, n - cnt);
            }
        }
        cout << ans << '\n';
    }

    return 0;
}

t = int(input())
for _ in range(t):
    n = int(input())
    v = list(map(int, input().split()))
    total = sum(v)
    ans = n - 1
    if total == 0:
        print(0)
        continue
    for i in range(1, 1000001):
        if total % i == 0:
            cnt = 0
            ok = True
            current_sum = 0
            for j in range(n):
                current_sum += v[j]
                if current_sum > i:
                    ok = False
                    break
                if current_sum == i:
                    current_sum = 0
                    cnt += 1
            if ok:
                ans = min(ans, n - cnt)
    print(ans)