2017 facebook hackercup round1 solution

Posted on In Disqus:

Actually, I unfortunately failed in round1. But I find algorithm hacker cup interesting. I wrote some codes as the solutions for this round. Hope you enjoy it.

Pie Progress

  • We can see that, if he buy pie number $n$ on one day, then he have to pay another $n^2$ money.

    Then according to $\sum (2k + 1) = k^2$, we know that we can sort the every day’s pie price, then add odd number to it.

    When buying the pies, since it is pre-sorted by the code, adding odd number in growing order to it does not influence the sequence.

  • Another point need to remember is that: one can not buy a pie that is preceding his day.

    For example: if he is on the first day, then he should only buy pies on the first day, rather than pies on the second day or even later.

So here is the code. Hope you enjoy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
using namespace std;
int main() {
    // input redirection
    freopen("pieprogress.in", "r", stdin);
    freopen("pieprocess_cache.out", "w", stdout);
    // some testcase number input
    int testcase; cin >> testcase;
    for (int tes = 0; tes < testcase; tes++) {
        // given the days and the pie number every day
        int days, pies_per_day; cin >> days >> pies_per_day;
        deque<int> prices[300];
        for (int i = 0; i < days; i++) {
            // take in the money of each pie
            for (int j = 0; j < pies_per_day; j++) {
                int temp; cin >> temp;
                prices[i].push_back(temp);
            }
            // sort them
            sort(prices[i].begin(), prices[i].end());
            // then add 1 3 5 7 9... to make n^2
            for (int j = 0; j < pies_per_day; j++)
                prices[i][j] += (2 * j + 1);
        }
        // total result
        long long total_price = 0;
        for (int i = 0; i < days; i++) {
            // find the min price
            // if it is the current min and in the current day
            // add to total price and pop out
            int min_price = 0;
            while (prices[min_price].empty())
                min_price++;
            for (int j = 0; j <= i; j++)
                if (!prices[j].empty())
                    if (prices[min_price][0] > prices[j][0])
                        min_price = j;
            total_price += prices[min_price][0];
            prices[min_price].pop_front();
        }
        cout << "Case #" << tes + 1 << ": " << total_price << endl;
    }
    return 0;
}