SLOWSOLN-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Abhinav Gupta
Tester: Satyam, Jatin Garg
Editorialist: Devendra Singh

DIFFICULTY:

1003

PREREQUISITES:

Basic Maths

PROBLEM:

Chef is trying to solve a problem having T test cases, where, for each test case he is given a single integer N.

Chef has an algorithm which takes exactly N^2 iterations for a test case with value N.

The constraints of the problem are as follows:

  • 1 \leq T \leq maxT
  • 1 \leq N \leq maxN
  • Sum of N over all test cases does not exceed sumN.

Given the values maxT, maxN, and sumN, determine the maximum number of iterations Chef’s algorithm can take for any valid input file satisfying all the constraints.

Formally speaking, find the maximum value of N_1^2 + N_2^2 + \dots + N_T^2 for:

  • 1 \leq T \leq maxT
  • 1 \leq N_i \leq maxN
  • N_1 + N_2 + N_3 +\dots +N_T \leq sumN

EXPLANATION:

Observation: There can be at most one test case in which N<maxN in the optimal answer.
Proof: Let us suppose in the optimal answer there are more than one test case in which N<maxN. Let two of such test cases have values x and y where 1\leq x<N, 1\leq y<N and x\leq y. We can decrease x by 1 and increase y by 1. This won’t change the sum of the elements but sum of squares of the elements increases by (y+1)^2-y^2+(x-1)^2-x^2 = 2\cdot y+1+1-2\cdot x = 2\cdot (y-x)+2 > 0. If x becomes 0 we simply remove that test case. In this way at the end either all values become equal to maxN or at most one value remains which is less than maxN.

Let us calculate the maximum value of N_1^2 + N_2^2 + \dots + N_T^2 when all values are equal to maxN. Maximum number of test cases that can have N= maxN is min(maxT,floor(sumN/maxN)). Therefore maximum value in all such cases is maxN^2\cdot min(maxT,floor(sumN/maxN)).

If maxT is at least ceil(sumN/maxN) (otherwise we can have maxT testcases all with N=maxN) then we can have one test case in which N<maxN. To maximize the result we will take the last value as sumN % maxN. So that the total sum of N values in all testcases becomes sumN.
Therefore the maximum value for such cases is floor(sumN / maxN) \cdot maxN^2 + (sumN % maxN)^2.
The maximum of both these values is the answer to the problem.

TIME COMPLEXITY:

O(1) for each test case.

SOLUTION:

Setter's solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
using namespace std;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
vector <int> adj[N];
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);

            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
void solve()
{
    ll maxT=readInt(1,10000,' ');
    ll maxN=readInt(1,10000,' ');
    ll sumN=readInt(1,10000,'\n');
    assert(maxT<=maxN && maxN<=sumN);
    if(maxT*maxN<=sumN)
    {
        cout<<(maxN*maxN*maxT)<<'\n';
        return;
    }
    ll tmp=(sumN/maxN);
    ll ans=tmp*maxN*maxN;
    ll left=(sumN-tmp*maxN);
    ans+=(left*left);
    cout<<ans<<'\n';
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(false);
    cin.tie(NULL),cout.tie(NULL);
    int T=readInt(1,1000,'\n');
    while(T--)
        solve();
    assert(getchar()==-1);
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    ll maxT, maxN, sumN, maxcalc = 0;
    cin >> maxT >> maxN >> sumN;
    maxcalc = max(maxcalc, min((sumN / maxN), maxT) * maxN * maxN);
    if (maxT >= (sumN + maxN - 1) / maxN)
    {
        maxcalc = max(maxcalc, (sumN / maxN) * maxN * maxN + (sumN % maxN) * (sumN % maxN));
    }
    cout << maxcalc << '\n';
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}

1 Like