ANTIKNAPSACK-Editorial

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

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); }
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