corpo-rat's blog

Help me out on this love problem.
By corpo-rat, history, 3 months ago, In English

I was trying to figure this out on my own for some time but i could not so I need your help.

2072E - Do You Love Your Hero and His Two-Hit Multi-Target Attacks?

So the question wants you to find pairs where either |deltax| or |deltay| is zero. At first, i tried to find two numbers a and b such that a(a-1) / 2 + b(b-1) / 2 = k but there are numbers that are not a sum of two triangular numbers. Famously gauss proved that any number can be expressed as a sum of upto 3 triangular numbers a, b, c.

So this question boils down to find non-negative integers a, b, c such that a(a-1)/2 + b(b-1)/2 + c(c-1)/2 = k and a+b+c <= 500.

Since, k <= 10^5, a + b + c will be less than 500, because if we solve for k = 10^5, we get a = 12 and following my code b will be 23 and c will be 447, hence 447 + 23 + 12 is 482 which is <= 500.

I implemented this below:

#include <bits/stdc++.h>

#define peace "\n"
#define ll long long
#define vi vector<int>
#define vl vector<long long>
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>

using namespace std;

const int MAXN = 1e5;

vi Tri;

vi bestl(MAXN+1, -1);
vi bestr(MAXN+1, -1);
vector<bool> hasrep(MAXN+1, false);

void precompute() {
    for (int i = 0; (i*(i-1)/2) <= MAXN; i++) {
        Tri.push_back(i*(i-1) / 2);
    }

    for (int l = 0; l < Tri.size(); l++) {
        for (int r = l; r < Tri.size(); r++) 
        {
            int s = Tri[l] + Tri[r];
            if (s > MAXN) break;
            if (!hasrep[s] || (l+r) < (bestl[s]+bestr[s])) {
                hasrep[s] = true;
                bestl[s] = l;
                bestr[s] = r;
            }
        }
    }
}

int main()
{
    precompute();

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while(t--)
    {
        int k; cin >> k;

        int a = -1, b = -1, c = -1;
        bool found = false;

        for (int i = 0; i < Tri.size(); i++) 
        {
            if (Tri[i] > k) break;
            int target = k - Tri[i];

            if (!hasrep[target]) continue;

            int l = bestl[target];
            int r = bestr[target];

            if (i + l + r <= 500) { 
                a = i;
                b = l;
                c = r;
                break; 
            }
        }

        cout << a + b + c << peace;

        for (int i = 0; i < a; i++) cout << (int)1e8 << " " << i << peace;
        for (int i = 0; i < b; i++) cout << (int)4e7 << " " << i + (int)1e4 << peace;
        for (int i = 0; i < c; i++) cout << i + (int)-1e4 << " " << (int)-1e8 << peace; 
    }
    return 0;
}

Its getting wrong answer on test case 5 with verdict wrong answer Integer parameter [name=n] equals to -3, violates the range [0, 500] (test case 11) Test Case 11 — k = 99011

Link to the submission — 378264114

  • Vote: I like it
  • -11
  • Vote: I do not like it

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

Auto comment: topic has been updated by corpo-rat (previous revision, new revision, compare).

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by corpo-rat (previous revision, new revision, compare).

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

so it seems like the sum of 3 smallest triangle numbers that sum up to $$$99011$$$ (the testcase you're failing) is larger than $$$500$$$.

I suggest you solve by greedily taking the largest triangle number $$$ \lt n$$$

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hey! I've been looking for like-minded people to grow with in competitive programming. It would be great to connect, practice together, share progress, and help each other stay consistent. Looking forward to learning and improving together!

→ Reply
»
3 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Your approach tries to represent k as a sum of exactly 3 triangular numbers, but the problem does not require using only 3 groups. For some values like k = 99011, the best representation with 3 groups may need more than 500 points, so a + b + c > 500, and your variables stay -1.

A simpler solution is greedy:

At each step, take the largest s such that:

s * (s - 1) / 2 <= k

Then create s points on the same vertical line. These s points generate exactly:

s * (s - 1) / 2

valid pairs, because every pair has the same x.

Then subtract that value from k, move to another x, and repeat until k = 0.

Example idea:

while (k > 0) {
    int s = 1;
    while ((s + 1) * s / 2 <= k) s++;

    // put s points with same x
    for (int i = 0; i < s; i++) {
        p.push_back({x, y});
        y++;
    }

    k -= s * (s - 1) / 2;
    x++;
}

Each group has a different x, so pairs from different groups do not accidentally add extra pairs. Inside one group, all points share the same x, so they contribute exactly the triangular number.

This avoids the issue of forcing the answer into only 3 groups.

→ Reply