algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

commit 31b1ae169558a33b41e5de9d8cc29e80303c27e1
parent 7a9f283c717a78eafb449424dba25dbfdee0fb39
Author: Andrew Laack <andrew@laack.co>
Date:   Tue,  3 Nov 2026 00:41:08 -0600

DP with bitmask

Diffstat:
Acomp/kefa-and-dishes/ex1.in | 3+++
Acomp/kefa-and-dishes/ex2.in | 4++++
Acomp/kefa-and-dishes/main.cpp | 103+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Acomp/kefa-and-dishes/problem.txt | 81+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
Mcomp/r1131/a/main.cpp | 10++++++++++
5 files changed, 201 insertions(+), 0 deletions(-)

diff --git a/comp/kefa-and-dishes/ex1.in b/comp/kefa-and-dishes/ex1.in @@ -0,0 +1,3 @@ +2 2 1 +1 1 +2 1 1 diff --git a/comp/kefa-and-dishes/ex2.in b/comp/kefa-and-dishes/ex2.in @@ -0,0 +1,4 @@ +4 3 2 +1 2 3 4 +2 1 5 +3 4 2 diff --git a/comp/kefa-and-dishes/main.cpp b/comp/kefa-and-dishes/main.cpp @@ -0,0 +1,103 @@ +#include <iostream> +#include <cmath> +#include <vector> +#include <bitset> + +// n = 4 +// m = 3 +// k = 2 +// +// satisfactions := 1 2 3 4 +// +// [2 1 5] +// [3 4 2] +// +// 1 after 2 and 4 after 3 get bonuses +// +// order 2 (2) +// order 1 (6) +// order 4 (4) +// +// = 12 (better) +// +// order 3 (3) +// order 4 (6) +// order 2 (2) +// +// = 11 +// +// --- +// +// best selections: +// +// - max score after the current state given our prior state +// - dp with state of (selected, prior) + +using namespace std; + +long long solve(vector<long long>& dishes, vector<vector<long long>>& addedSatisfaction, int prior, bitset<20>& consumed, int step, int toEat, vector<vector<long long>>& lookup) { + + unsigned long long mask = consumed.to_ulong(); + if(lookup[mask][prior + 1] != -1) { + return lookup[mask][prior + 1]; + } + + if(step == toEat) { + lookup[mask][prior + 1] = 0; + return 0; + } + + long long best = 0; + + for(int i = 0; i < consumed.size() && i < dishes.size(); ++i) { + if(consumed[i] == 0) { + consumed[i] = 1; + long long currentSat = dishes[i]; + if(prior != -1) { + currentSat += addedSatisfaction[prior][i]; + } + + long long candidate = solve(dishes, addedSatisfaction, i, consumed, step + 1, toEat, lookup) + currentSat; + consumed[i] = 0; + + if(candidate > best) { + best = candidate; + } + } + } + + lookup[mask][prior + 1] = best; + return best; +} + +int main() { + + int n, m, k; + long long current; + + cin >> n; + cin >> m; + cin >> k; + + vector<long long> dishes {}; + + for(int i = 0; i < n; ++i) { + cin >> current; + dishes.push_back(current); + } + + vector<vector<long long>> addedSatisfaction(n, vector<long long>(n, 0)); + + for(int i = 0; i < k; ++i) { + int x, y; + long long z; + cin >> y; + cin >> x; + cin >> z; + addedSatisfaction[y - 1][x - 1] = z; + } + + bitset<20> consumed {}; + vector<vector<long long>> lookup(1 << n, vector<long long>(n + 1, -1)); + cout << solve(dishes, addedSatisfaction, -1, consumed, 0, m, lookup) << endl; +} diff --git a/comp/kefa-and-dishes/problem.txt b/comp/kefa-and-dishes/problem.txt @@ -0,0 +1,81 @@ +D. Kefa and Dishes +time limit per test +2 seconds +memory limit per test +256 megabytes + +When Kefa came to the restaurant and sat at a table, the waiter immediately brought him the menu. There were n dishes. Kefa knows that he needs exactly m dishes. But at that, he doesn't want to order the same dish twice to taste as many dishes as possible. + +Kefa knows that the i-th dish gives him ai units of satisfaction. But some dishes do not go well together and some dishes go very well together. Kefa set to himself k rules of eating food of the following type — if he eats dish x exactly before dish y (there should be no other dishes between x and y), then his satisfaction level raises by c. + +Of course, our parrot wants to get some maximal possible satisfaction from going to the restaurant. Help him in this hard task! +Input + +The first line of the input contains three space-separated numbers, n, m and k (1 ≤ m ≤ n ≤ 18, 0 ≤ k ≤ n * (n - 1)) — the number of dishes on the menu, the number of portions Kefa needs to eat to get full and the number of eating rules. + +The second line contains n space-separated numbers ai, (0 ≤ ai ≤ 109) — the satisfaction he gets from the i-th dish. + +Next k lines contain the rules. The i-th rule is described by the three numbers xi, yi and ci (1 ≤ xi, yi ≤ n, 0 ≤ ci ≤ 109). That means that if you eat dish xi right before dish yi, then the Kefa's satisfaction increases by ci. It is guaranteed that there are no such pairs of indexes i and j (1 ≤ i < j ≤ k), that xi = xj and yi = yj. + +--- + +thoughts: + +- there are n dishes and we want m dishes + - can't order same dish twice +- dish i gives a_i satisfaction +- food eating together rules + - if he eats dish x exactly before dish y, then his satisfaction level raises by c + +--- + +ex1 + +n,m,k + +n = 2 (list items) +m = 2 (to order) +k = 1 (triples) + +items := 1 1 +rules := [2 1 1] + +rules says if we eat 2 right before 1, we get 1 extra reward + +we want to do this: + +get 2, get 1 + +1 satisfaction, 1 satisfaction + 1 addl bonus = 3 + +--- + +n = 4 +m = 3 +k = 2 + +satisfactions := 1 2 3 4 + +[2 1 5] +[3 4 2] + +1 after 2 and 4 after 3 get bonuses + +order 2 (2) +order 1 (6) +order 4 (4) + += 12 (better) + +order 3 (3) +order 4 (6) +order 2 (2) + += 11 + +--- + +best selections: + +- max score after the current state given our prior state +- dp with state of (selected, prior) diff --git a/comp/r1131/a/main.cpp b/comp/r1131/a/main.cpp @@ -45,9 +45,19 @@ int main() { } int sum = 0; + bool printed = false; for(int i = 0; i < 26; ++i) { + if(pCharCounts[i] < 0) { + cout << "NO" << endl; + printed = true; + break; + } sum += pCharCounts[i]; } + + if(printed) { + continue; + } if(sum != 3) { cout << "NO" << endl;