BatchSystemRoulette.cpp

#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define pi pair<int,int>
#define all(x) x.begin(), x.end()
#define allr(x) x.rbegin(), x.rend()
#define sz(x) ((int)x.size())
#define ln(x) ((int)x.length())
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define endl '\n'
#define dbg(x) cout << #x << ": " << x << endl
#define clr(x,v) memset(x, v, sizeof(x))
#define dblout(x) cout << setprecision(x) << fixed;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;
const double eps = 1e-9;
const double PI = acos(-1.0);
const ll mod = 1e9 + 7;
const int MAXN = 1e6 + 5;

class BatchSystemRoulette
{
public:
    vector <double> expectedFinishTimes(vector <int>, vector <string>);
};

vector <double> BatchSystemRoulette::expectedFinishTimes(vector <int> duration, vector <string> user)
{
    int n = sz(duration);
    vector<double> ans(n);
    map<string, ll> sum_of_duration;
    for(int i = 0; i < n; i++)
        sum_of_duration[user[i]] += duration[i];

    for(int i = 0; i < n; i++)
    {
        // All users who have total duration < me must be processed before me
        // All users who have same duration as me must be picked with equal probability
        double before = 0;
        int eqn = 0;
        ll D = sum_of_duration[user[i]];
        for(auto x : sum_of_duration)
            if(x.ss < D)
                before += x.ss;
            else if (x.ss == D)
                eqn++;
        // We have a total of 'eqn' positions where our users's tasks can be processed
        // _ _ _ _ _
        // Our tasks can be at position 0...eqn-1 and have 0...n - 1 users before me
        // so the expected excess time we get is
        // (0D + 1D + 2D + ... + eqn-1*D) / eqn
        // sum_upto(eqn-1) * D / eqn
        // excess = (eqn - 1) * 0.5 * D
        // This excess is common for all the tasks of our current user
        double excess = (eqn - 1) * 0.5 * D;

        // Now as for all the tasks of our current user, we have to process the current task
        // Each of the tasks that our current user has has an equal probability of 1/2 of occuring before
        // the current task, so the excess we get is 1/2 * task1 + 1/2 * task2 + ...
        // same as (total duration - current task) / 2

        // Of course this all that will happen before me
        // We need duration[i] time to actually complete the task
        excess += (D - duration[i]) / 2.0;
        ans[i] = before + excess + duration[i];
    }

    return ans;
}
// BEGIN KAWIGIEDIT TESTING
// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
bool KawigiEdit_RunTest(int testNum, vector <int> p0, vector <string> p1, bool hasAnswer, vector <double> p2)
{
    cout << "Test " << testNum << ": [" << "{";
    for (int i = 0; int(p0.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << p0[i];
    }
    cout << "}" << "," << "{";
    for (int i = 0; int(p1.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << "\"" << p1[i] << "\"";
    }
    cout << "}";
    cout << "]" << endl;
    BatchSystemRoulette *obj;
    vector <double> answer;
    obj = new BatchSystemRoulette();
    clock_t startTime = clock();
    answer = obj->expectedFinishTimes(p0, p1);
    clock_t endTime = clock();
    delete obj;
    bool res;
    res = true;
    cout << "Time: " << double(endTime - startTime) / CLOCKS_PER_SEC << " seconds" << endl;
    if (hasAnswer)
    {
        cout << "Desired answer:" << endl;
        cout << "\t" << "{";
        for (int i = 0; int(p2.size()) > i; ++i)
        {
            if (i > 0)
            {
                cout << ",";
            }
            cout << p2[i];
        }
        cout << "}" << endl;
    }
    cout << "Your answer:" << endl;
    cout << "\t" << "{";
    for (int i = 0; int(answer.size()) > i; ++i)
    {
        if (i > 0)
        {
            cout << ",";
        }
        cout << answer[i];
    }
    cout << "}" << endl;
    if (hasAnswer)
    {
        if (answer.size() != p2.size())
        {
            res = false;
        }
        else
        {
            for (int i = 0; int(answer.size()) > i; ++i)
            {
                if (fabs(p2[i] - answer[i]) > 1e-9 * max(1.0, fabs(p2[i])))
                {
                    res = false;
                }
            }
        }
    }
    if (!res)
    {
        cout << "DOESN'T MATCH!!!!" << endl;
    }
    else if (double(endTime - startTime) / CLOCKS_PER_SEC >= 2)
    {
        cout << "FAIL the timeout" << endl;
        res = false;
    }
    else if (hasAnswer)
    {
        cout << "Match :-)" << endl;
    }
    else
    {
        cout << "OK, but is it right?" << endl;
    }
    cout << "" << endl;
    return res;
}
int main()
{
    bool all_right;
    all_right = true;

    vector <int> p0;
    vector <string> p1;
    vector <double> p2;

    {
        // ----- test 0 -----
        int t0[] = {3, 2, 4, 1};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"Gil Grissom", "Sarah Sidle", "Warrick Brown", "Catherine Willows"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        double t2[] = {6.0, 3.0, 10.0, 1.0};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 1 -----
        int t0[] = {3, 2, 4, 1};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"mac taylor", "Mac Taylor", "Mac Taylor", "Peyton Driscoll"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        double t2[] = {4.0, 8.0, 9.0, 1.0};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
        // ------------------
    }

    {
        // ----- test 2 -----
        int t0[] = {13, 14, 15, 56, 56};
        p0.assign(t0, t0 + sizeof(t0) / sizeof(t0[0]));
        string t1[] = {"Tim Speedle", "Tim Speedle", "Tim Speedle", "Horatio Caine", "YEEEAAAAAAAAAAH"};
        p1.assign(t1, t1 + sizeof(t1) / sizeof(t1[0]));
        double t2[] = {27.5, 28.0, 28.5, 126.0, 126.0};
        p2.assign(t2, t2 + sizeof(t2) / sizeof(t2[0]));
        all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
        // ------------------
    }

    if (all_right)
    {
        cout << "You're a stud (at least on the example cases)!" << endl;
    }
    else
    {
        cout << "Some of the test cases had errors." << endl;
    }
    return 0;
}
// END KAWIGIEDIT TESTING



//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!