viggibear's blog

By viggibear, history, 9 months ago, In English

From what I know, the problem can be solved by greedy since ceil(n) = 100000 so even O(n^2) might fail but my greedy solution has been failing due to various different reasons. Any insights appreciated!

Problem: https://open.kattis.com/problems/cardtrading

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Solved using a Greedy that sorts {buy, sell} pairs by ascending order based on buy + sell price. Subtract price of buying first K and add price of selling next T-K and return from this sorted list of pairs.

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef map<int, int> mii;
typedef map<int, bool> mib;
typedef map<string, int> msi;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;

// Use these constants so you don't need to define your own
const int SZ = 1E6;
const int INF = (1 << 29);
const double EPS = 1E-9;
const double PI = 2 * acos(0.0);
const ll MOD = 1000000007;
int dirx[8] = {-1, 0, 0, 1, -1, -1, 1, 1};
int diry[8] = {0, 1, -1, 0, -1, 1, -1, 1};

#define VALUE(x) cout << "The value of " << #x << " is " << x << endl
#define NL cout << endl;

#define FOR(a, b, c) for (int(a) = (b); (a) < (c); ++(a))
#define FORN(a, b, c) for (int(a) = (b); (a) <= (c); ++(a))
#define FORD(a, b, c) for (int(a) = (b); (a) >= (c); --(a))
#define FORSQ(a, b, c) for (int(a) = (b); (a) * (a) <= (c); ++(a))
#define FORC(a, b, c) for (char(a) = (b); (a) <= (c); ++(a))
#define FOREACH(a, b) for (auto &(a) : (b))
#define REP(i, n) FOR(i, 0, n) // for (int i = 0; i < n; i++)
#define REPN(i, n) FORN(i, 1, n) // for (int i = 1; i <= n; i++)
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define SQR(x) ((ll)(x) * (x))
#define RESET(a, b) memset(a, b, sizeof(a)) // reset an array before using
#define RESET2D(a, b) fill_n(*a, sizeof a / sizeof **a, b)
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define ALLA(arr, sz) arr, arr + sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v)) // sort an array faster
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr, sz) sort(ALLA(arr, sz))
#define REVERSEA(arr, sz) reverse(ALLA(arr, sz))
#define PERMUTE next_permutation
#define TC(t) while (t--)


int N, T, K, bp, sp, h[100001];
ll p = 0;
vii n;

int main(void) {
    cin >> N >> T >> K;
    RESET(h, 0);

    // histogram
    REP(i, N) {
        cin >> bp;
        h[bp]++;
    }

    // place into net as {buy price, sell price}
    REPN(i, T) {
        cin >> bp >> sp;
        n.pb(mp(max(2 - h[i], 0) * bp, h[i] * sp));
    }

    sort(begin(n), end(n), // Sort all pairs based on sum of buy + sell
         [](const pii &a, const pii &b) { return a.fi + a.se < b.fi + b.se; });
    REP(i, K) p -= n[i].fi; // For first K --> subtract buy from profits
    FOR(i, K, n.size()) p += n[i].se; // For remaining T-K --> add sell price to profits

    cout << p << endl;
}
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi, do you mind explaining what is the rationale of sorting by sum of buy + sell?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      For each card type, the "net cost" of making it up to a combo is the cost for buying missing card(s) plus the loss of profit for not selling card(s) of that type.