PROBLEM LINK:
Author: Adithya
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta
DIFFICULTY:
Medium
PREREQUISITES:
Dynamic Programming, Combinatorics
PROBLEM:
You are given N lines with slope a_i, intercept b_i and colour C_i. Every colour has a strength value of V_i associated with it. You are also given an erase with power equal to K.
A triangle is called good if it is constructed by the same colour lines and has a positive area. You have to minimise the count of such good triangles formed by given N lines. To do so you can use the eraser to erase any line you want but if you want to erase some line with colour C_i then the power of eraser decreases by V_i.
QUICK EXPLANATION:
Let’s try to solve the problem step by step:
- First we have to pay attention to the constraints of K.
- If K = 0 then we know that we need to solve the problem for each colour independently.
- If K > 0 then can we still use the same approach and merge the answer to solve the problem. As possibilities are a lot so we should use dynamic programming to merge the answer.
- Two parallel lines can not participate in the formation of any triangle. So, for each colour, we should club the parallel lines and then it is just to remove some of them based on the value of K and find the answer.
- If there are X groups of parallel lines for some colour then the answer would be the sum of the product of the frequency of all unordered triplets from X.
- As V is unique for some colour then deleting any line for any particular does not affect the power of K but if there are X groups of parallel lines with the same colour then it is always optimal to delete the one from the group that has less number of lines. We’ll explain the proof later in the editorial.
- Now, if we can precompute the answer for each K for each colour then merging the answer is only a simple knapsack problem.
EXPLANATION:
Observation: As only those triangles are going to be considered who are formed with the same colour of lines and all the lines of that colour have the same strength so we can easily solve the problem for each colour independently.
Lemma: If two lines are parallel then they never participate in the generation of any triangle.
Lemma: If there are two parallel lines X and Y with the same colour then the number of good triangles formed from both them is the same.
Lemma: If there are X groups each containing f_1, f_2, ... , f_X lines such that f_1 \le f_2 \le … \le f_X then we should delete from the minimum size group means first delete lines from f_1, then f_2, and so on…
Mathematical Problem: Given a set of non-negative integers A_1, A_2, ... A_N, you have to compute the sum of the product of all unordered triplets of this set after performing K operations. In one operation, select any positive integer from the set, and subtract 1 from its value. Find the minimum possible sum of the product of all unordered triplets.
Claim: For each operation, select the minimum integer from the set and apply the operation on this integer.
Proof: Let’s assume A_1 \le A_2 \le ... \le A_N and any optimum solution for this is B_1 \le B_2 \le ... \le B_N. It is guaranteed that B_i \le A_i for each valid i (1 <= i <= N).
Now, suppose there exists some i < j such that 0 < B_i and B_j < A_j (if there doesn’t exist any, it is already under our claim). Now, we can add 1 to B_j and subtract 1 from B_i, with that difference between previous sum and the current sum being positive which is more optimal and we still have a valid solution, since 0 \le B_i \le A_i for each valid i(1 <= i <= N) which has better total value than the previous optimal solution.
Let’s divide the optimal answer B in three-set:
- P_1 = sum of all numbers from B except B_i and B_j
- P_2 = sum of the product of two numbers from B except for B_i and B_j
- P_3 = sum of the product of three numbers from B except for B_i and B_j
Previous sum = P_3 + P_2 * (B_i + B_j) + P_1 * B_i * B_j
Current sum = P_3 + P_2 * (B_i - 1 + B_j + 1) + P_1 * (B_i - 1) * (B_j + 1)
Current sum = P_3 + P_2 * (B_i + B_j) + P_1 * B_i * B_j + P_1 * (B_i - B_j - 1)
Difference = Previous sum - Current sum
Difference = P1 * (B_j - B_i + 1)
As B_i <= B_j which implies that Difference should be positive that again implies that it is a better solution than the optimal one which is a contradiction.
Now, let’s use these to solve the problem. So, we can first partition the lines according to their colour and for each colour, we are going to partition them according to a_i value(we are creating parallel line groups as a_i is the slope) according to lemma 1 and 2.
Now, for each colour, we have the groups of parallel lines which need to be sorted first according to lemma 3 and with this lemma, we try to find the answer by removing the lines according to increasing order of the size of the group.
Then the problem is simply applying knapsack over the colours and keeping in my mind the value of K.
TIME COMPLEXITY:
TIME: O(N*K)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
Not available
Tester's Solution
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define mp make_pair
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
const int MAX = 3005;
int V[MAX];
int a[MAX], b[MAX], c[MAX];
map<int, int> groups[MAX];
ll ans[MAX][MAX];
int sz[MAX];
ll dp[MAX];
ll newDp[MAX];
ll get(vector<ll> &freq)
{
ll s = 0 , s2 = 0, s3 = 0;
for(auto x : freq)
{
s += x;
s2 += x * x;
s3 += x * x * x;
}
assert((s * s * s - 3 * s2 * s + 2 * s3) % 6 == 0);
return (s * s * s - 3 * s2 * s + 2 * s3) / 6;
}
int main() {
ios_base::sync_with_stdio(0);
int T;
cin >> T;
assert(1 <= T && T <= 10);
while(T--)
{
int n, C, k;
cin >> n >> C >> k;
assert(1 <= n && n <= 3000);
assert(1 <= C && C <= n);
assert(0 <= k && k <= 3000);
for(int i = 0; i < n; i++)
{
cin >> a[i] >> b[i] >> c[i];
assert(a[i] >= 0 && a[i] <= INF);
assert(b[i] >= 0 && b[i] <= INF);
/*assert(a[i] || b[i]);
ll gcd = __gcd(a[i], b[i]);
a[i] /= gcd;
b[i] /= gcd;*/
assert(c[i] >= 1 && c[i] <= C);
c[i]--;
groups[c[i]][a[i]]++;
}
for(int i = 0; i < C; i++)
{
cin >> V[i];
assert(V[i] >= 0 && V[i] <= k);
}
for(int i = 0; i < C; i++)
{
vector<ll> freq;
for(auto x : groups[i])
freq.pb(x.y);
sort(freq.begin(), freq.end());
int ptr = 0 , ptr2 = 0;
while(ptr < sz(freq))
{
ans[i][ptr2++] = get(freq);
freq[ptr]--;
if(!freq[ptr])
ptr++;
}
ans[i][ptr2] = 0;
sz[i] = ptr2;
}
dp[0] = 0;
for(int i = 1; i <= k; i++)
dp[i] = INF * (ll) INF;
for(int i = 0; i < C; i++)
{
for(int j = 0; j <= k; j++)
newDp[j] = INF * (ll) INF;
for(int j = 0; j <= k; j++)
for(int del = 0; del <= sz[i]; del++)
{
int nxt = j + del * V[i];
if(nxt <= k)
newDp[nxt] = min(newDp[nxt] , dp[j] + ans[i][del]);
}
for(int j = 0; j <= k; j++)
dp[j] = newDp[j];
}
ll ans = INF * (ll) INF;
for(int j = 0; j <= k; j++)
ans = min(ans , dp[j]);
cout << ans << endl;
for(int j = 0; j < C; j++)
groups[j].clear();
}
}
Editorialist's Solution
#include <bits/stdc++.h>
#define int long long
#define mod 1000000007
using namespace std;
const int N = 5010;
const int M = mod;
int ans[N][N], sz[N];
int dp[N], dp1[N];
int32_t main()
{
int t;
cin >> t;
while(t--)
{
int n, c, k, x, y, z;
cin >> n >> c >> k;
for(int i=0;i<=k;i++)
{
dp[i] = 0;
if(i > 0)
dp[i] = M * M;
}
vector <int> v, v1;
map<int, int> m[N];
for(int i = 0; i < n; i++)
{
cin >> x >> y >> z;
m[z-1][x]++;
}
for(int i=0;i<c;i++)
{
cin >> x;
v.push_back(x);
for(auto x : m[i])
v1.push_back(x.second);
sort(v1.begin(), v1.end());
y = 0;
for(int j=0;j<v1.size();j++)
{
while(v1[j] > 0)
{
int cnt1,cnt2,cnt3;
cnt1 = cnt2 = cnt3 = 0;
for(auto z : v1)
{
cnt1 += z;
cnt2 += z*z;
cnt3 += z*z*z;
}
ans[i][y++] = (cnt1*cnt1*cnt1 + 2*cnt3 - 3*cnt2*cnt1) / 6;
v1[j]--;
}
}
ans[i][y] = 0;
sz[i] = y;
v1.clear();
}
for(int i=0;i<c;i++)
{
for(int j=0;j<=k;j++)
dp1[j] = M * M;
for(int j=0;j<=k;j++)
{
for(int l=0;l<=sz[i];l++)
{
x = j + l*v[i];
if(k < x)
break;
dp1[x] = min(dp1[x] , dp[j] + ans[i][l]);
}
}
for(int j = 0; j <= k; j++)
dp[j] = dp1[j];
}
int ans = dp[0];
for(int i=0;i<=k;i++)
ans = min(ans , dp[i]);
cout << ans << endl;
}
}
