ACCBIP - Editorial

PROBLEM LINK:

Division 1
Division 2

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;
    }
}  
11 Likes

https://www.codechef.com/viewsolution/36698394
I got WA on only one case (Sub Task 9).
Can anyone help

3 Likes

Just wanted to say, probably my favorite problem from this long contest. I’ve not solved that many geometry problems, but according to me this one had really nice observations. Also the subtasks (excl. the 1st ofc) are really sensible and useful while thinking about the logic (though my logic seems to be a fair bit different from the one described in the editorial).

13 Likes

Nice problem!

3 Likes

Sadly, infinitepro failed his re-examination, so there’s no treat. :slightly_frowning_face:
However, watch out for his next examinations (and problems!)

16 Likes

Hey, my code failed for only one test case, could you please identify the problem, thanks.
https://p.ip.fi/TxpH

1 Like

@rishup_nitdgp the solutions of the setter, tester and editorialist are not visible. Please update the editorial with the solutions.

3 Likes

Faced the same problem bro.

My solution

@rishup_nitdgp can you please check my code and tell which test case my code failing i used dp…but for 15 its failing for 1 test case and for 25 its failing one test case i have to merge my 15 points code with this to get those points but why this code failing link of solution https://www.codechef.com/viewsolution/36565477

That’s odd.
Your code (as well as @pict_tourist) gets exactly 1 test case wrong, printing 9277379 instead of 9277373).
I haven’t looked at your code tho, so I’m not sure of the cause.

2 Likes

Can you please share your code?

1 Like

Same Issue
https://www.codechef.com/viewsolution/36807761

https://www.codechef.com/viewsolution/36859893 weirdly AC solution

8 Likes

One way of story-telling :stuck_out_tongue:

1 Like

https://www.codechef.com/viewsolution/36859863
Can anyone please explain why this code is getting TLE in case 4 and 6.
As the complexity is O(N*K) it shouldn’t get TLE.

Isn’t that irritating to debug.

1 Like

@infinitepro can you look at my doubt

Well, I see that sorting isn’t the problem. Your complexity is O(N×K×T). If you put the maximum values, it is around 9×107 which is close to 1 second time limit. If the constant factors are large then it might be the cause of TLE.

Even my code was failing at the same case, Please try to inform us of the mistake

Beautiful Problem !!

1 Like