2017 facebook hackercup round1 solution

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;
}
0%