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

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




Basic Number theory


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.


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.


O(N) for each test case.


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() {

    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;

    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)
    for (int i = 1; i <= n; i++)
        cout << i * d << ' ';
    cout << '\n';
int main()
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)

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