ANTIKNAPSACK-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: TheScrasse
Tester: Manan Grover, Abhinav sharma
Editorialist: Devendra Singh

DIFFICULTY:

2566

PREREQUISITES:

Basic Number theory

PROBLEM:

You are given two integers N and K.

Construct an array A_1, A_2, \dots, A_n consisting of distinct positive integers. The following conditions should be met:

  • 1 \leq A_i \leq 2 \cdot 10^4;
  • there isn’t any subset of A with sum K.

We can show that the answer always exists.

EXPLANATION:

Consider an integer d that does not divide K and take the first N multiples of d. It is obvious that no subset has a sum equal to K( the sum of each subset is divisible by d which does not divide K). The constraints on K allow us to find such d\leq 19 (2*3*5*7*11*13*17*19>10^6). Thus, iterate from d= 2\: to\: 19 and if d does not divide K take the first N multiples of d.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> t;
    while (t--) {
        cin >> n >> k;
        for (i = 1;; i++) {
            if (k % i != 0) {
                for (j = 1; j <= n; j++) cout << i * j << ' ';
                cout << nl;
                break;
            }
        }
    }

    return 0;
}
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n, k;
    cin >> n >> k;
    int d = 1;
    while (d++)
        if (k % d)
            break;
    for (int i = 1; i <= n; i++)
        cout << i * d << ' ';
    cout << '\n';
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
4 Likes

For n = 3, k = 6.
your algorithm will give d = 5.

hence the first n (=3) multiples of 5 are 5, 10, 15.

But clearly 5+10+15 = 30 is divisible by 6.

Am I missing something here?

1 Like

We don’t want a subset with sum = K, we can have a subset sum divisible by K

1 Like

oh, my bad

Why is this sufficient? I mean how do you prove that we can’t achieve the solution by some other way like mixing up different d and taking some other multiples of d instead of first N multiples of d?

He is not claiming that this is the only solution.
He is providing one of the correct solution.

1 Like