# DISTK - Editorial

Setter: Daanish Mahajan
Tester: Tejas Pandey, Abhinav Sharma
Editorialist: Kanhaiya Mohan

Easy

None

# PROBLEM:

An array is said to be good if all its elements are distinct, i.e. no two elements of the array are equal to each other.

You are given a positive integer N and an integer K such that N \leq K \leq {N+1} \choose 2.

Construct an array A of length N that satisfies the following conditions:

• A has exactly K good (contiguous) subarrays, and
• Every element of A is an integer from 1 to N (both inclusive).

# EXPLANATION:

Observation

For different types of arrays, check the number of good subarrays present.

• Array where all elements are equal: Here, only the subarrays of length 1 are good. Thus, the total number of good subarrays is N, where N is the length of the array.
• Array where all elements are distinct: If all the elements are distinct, any possible subarray of this array is good. Thus, the total number of good subarrays is {N+1} \choose 2.
• Any other type of array would have M number of good subarrays, where N < M < {N+1} \choose 2.

The number of good subarrays can be changed by introducing/removing duplicates from certain positions.

Note that, not only the number of duplicates, but their position also matters in determining the number of good subarrays.

Solution

All subarrays of length 1 are good. Thus, we need K' = K-N good subarrays of length \geq 2. From now on, we consider subarrays of length \geq 2 only.
An array of length X having distinct elements contributes X \choose 2 to the answer. Since the total number of good subarrays is K', we build an array of length X with distinct elements such that X \choose 2 \leq K < {X+1} \choose 2.

We now need K' - X \choose 2 good subarrays. This number would be less than X.

Why?

We know that K < {X+1} \choose 2.
K - X \choose 2 < {X+1} \choose 2 - X \choose 2
K - X \choose 2 < X

For the (X+1)^{th} and subsequent elements, we can place the number at position X - ( K' - X \choose 2 ). This would contribute K' - X \choose 2 good subarrays, all ending at position X+1. Since all the subsequent elements are duplicates of (X+1)^{th} element, they would not contribute anything.

# TIME COMPLEXITY:

The time complexity is O(N) per test case.

# SOLUTION:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
#define LL long long
mt19937_64 rng(seed);
#define rand(l, r) uniform_int_distribution<LL>(l, r)(rng)
clock_t start = clock();

#define getchar getchar_unlocked

namespace IO {
long long ret = 0;
char c = getchar();
while (c != endd) {
ret = (ret * 10) + c - '0';
c = getchar();
}
return ret;
}
long long readInt(long long L, long long R, char endd) {
assert(ret >= L && ret <= R);
return ret;
}
long long readIntSp(long long L, long long R) {
}
long long readIntLn(long long L, long long R) {
}
string readString(int l, int r) {
string ret = "";
char c = getchar();
while (c == '0' || c == '?' || c == '1') {
ret += c;
c = getchar();
}
assert((int)ret.size() >= l && (int)ret.size() <= r);
return ret;
}
}
using namespace IO;

const int TMAX = 1'00'000;
const int N = (int)1e5;
const LL K = (N * 1LL * (N + 1)) / 2;

LL sum_n = 0;

void solve() {
sum_n += n;
LL k = readIntLn(n, (n * 1LL * (n + 1)) / 2);
k -= n;
int i = 0, nxt = 1, cur = 0;
while (k >= cur) {
cout << cur + 1 << " ";
++i;
k -= cur;
++cur;
}
while (i < n) {
cout << cur - k << " ";
++i;
}
cout << '\n';
}

int main() {
while (T--) {
solve();
}
assert(sum_n <= 3 * N);
assert(getchar() == EOF);
cerr << fixed << setprecision(10);
cerr << (clock() - start) / ((long double)CLOCKS_PER_SEC) << " secs\n";
return 0;
}

Tester's Solution
#include <iostream>
using namespace std;

int main() {
int t;
cin >> t;
while(t--) {
long long n, k; cin >> n >> k;
k -= n;
cout << "1 ";
int last = 1;
for(int i = 1; i < n; i++) {
if(!k) cout << last << " ";
else if(k >= last) k -= last, last++, cout << last << " ";
else cout << last - k << " ", last -= k, k = 0;
}
cout << "\n";
}
return 0;
}

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

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)

void solve()
{
ll n,k;
cin>>n>>k;

ll curr = (n*n+n)/2;
int pos = n-1;

while(curr-pos>=k && pos>0){
curr -= pos;
pos--;
}
int ans[n+1];
rep_a(i,1,pos+1) ans[i] = i;
rep_a(i,pos+1, n+1) ans[i] = pos+1;

ans[curr-k] = pos+1;

rep_a(i,1,n+1) cout<<ans[i]<<" ";
cout<<'\n';
}

signed main()
{

#ifndef ONLINE_JUDGE
freopen("input.txt", "r" , stdin);
freopen("output.txt", "w" , stdout);
#endif
fast;

int t = 1;

cin>>t;

for(int i=1;i<=t;i++)
{
solve();
}

}

7 Likes

Can anyone tell where does my code fail.

Code link: Solution: 58140974 | CodeChef

This was a nice problem!!
Found so many different approaches from different submissions

8 Likes

Can anyone please tell me what’s wrong in my solution. It is failing only on 2nd testcase ;(

My basic idea is I go on adding the input value n uptil it comes in a interval i.e
suppose if n=5 and k=15
then number will be 1 2 3 4 5
for k=14, one ‘5’ gets added
5 2 3 4 5
now it goes on shifting till it reaches 4
1 5 3 4 5 ===> 13
1 2 5 4 5 ====>12
1 2 3 5 5 ====> 11
Now again this process will repeat till it goes to 3 at the end
5 2 3 5 5 ===>10
1 5 3 5 5 ===>9
1 2 5 5 5 ====>8
So i just loop over like remove 4 , then 3 and lastly if it comes in a interval , check where should the extra 5 to be added if needed.
Please guys help, its passing local testcases.

3 Likes

Can also solve using recursion, and repeating subproblems

#include <bits/stdc++.h>
#define int long long int

void helper(int n, int k){
int val = (n*(n+1))/2;
if(k > val-n){
for(int i=1; i<n; i++){
std::cout << i << " ";
}
if(val == k){
std::cout << n;
}
else{
std::cout << val-k;
}
return;
}
else{
std::cout << "1 ";
helper(n-1, k-1);
}
}

void solve(){
int n,k;
std::cin >> n >> k;
helper(n, k);
std::cout << "\n";
}

signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int t = 0;
std::cin >> t;
while(t--){
solve();
}
}

4 Likes

Can Anyone Explain how the alternate approach mentioned in the editorial work for n = 5 and k = 14 ?

The alternate approach is not correct. I have removed that. Thanks a lot for pointing out.

1 Like

Alternate approach, and intuition behind it,

1. For sake of uniformity we will fix n as 5 in all the examples, Lets say we have n=5 and k=5 then 11111 is our solution, similarly for n=5 k = 15 our solution is 12345 so we can initiate array with all 1s to start with and figure rest of stuff out

2. Next lets try to make k=6, it can be done by replacing 12222(we will use this pattern to build our solution) or 21111 etc, now similarly we can get k=7 as 12111. Similarly, we can get k=8 by 12333, k=9 by 12322 & k=10 by 12311

3. This pattern repeats for k=11,12…15, something like this-
1 1 1 1 1 for k=5
1 2 2 2 2 for k=6
1 2 1 1 1 for k=7
1 2 3 3 3 for k=8
1 2 3 2 2 for k=9
1 2 3 1 1 for k=10
1 2 3 4 4 for k=11
1 2 3 4 3 for k=12
1 2 3 4 2 for k=13
1 2 3 4 1 for k=14
1 2 3 4 5 for k=15

4. See another pattern for k=11-14,we’ve 1234 followed by 4,3,2,1 in descending order at 5th place

5. Just find a way to build this pattern and problem is solved, I used prefix sum and some trial and error to come up with this condition-

a[0]=1;
int ps=0;
for (int i = 1; i <n; i++)
{
ps+=i;
//if we have element that is below the prefix sum
if(ps+n<=k)
a[i]=a[i-1]+1;
else
{
//below we break the loop after we set a[i] as per observation 4
a[i]=a[(int) ((ps+n)-k-1)];
break;
}
}


1. We’re done just fill rest of zeroes in array with array[i-1]
for (int i = 1; i < a.length; i++) {
if(a[i]==0)
a[i]=a[i-1];
}

1. Closing note- use long for storing K and prefixSum.

Solution link- Solution: 58149892 | CodeChef

5 Likes

Yes, this was the first approach which came to mind and then I tried it for this case (n = 5 and k = 14) but it didn’t worked and then I realized that we need to have overlapping good subarrays (like for n = 5 and k = 14) we will get 1 2 3 4 1 where 1 2 3 4 and 2 3 4 1 are overlapping good subarrays

My approach was to iterate from index = 1 to N, and check if ith element should be a distinct element or an existing element.

All good subarrays are considered of length >=2 from here, as good subarrays of length =1 are already considered.

let cur be the current number of good subarrays added till now.
cur=0

Observation:

1. If a distinct element is added at ith position, that means, it adds x to cur.
where , x refers to (number of suffixes from i-1)

2. If an existing element is added at ith position, that means, it adds y to cur.
where ,y refers to (number of suffixes from i-1) till (j+1)th index.
where, j is the index of first occurrence of existing element.

Now, for every i from 1 to N,

Check if cur+(x)<=(K-N),
If above condition satisfies, assign a[i]=distinct element.
If above condition fails, assign a[i]=existing element.

Which existing element should be assigned?
let r be the number of good subarrays which are left to be found when we are at ith position. So, count r suffixes from (i-1)th index. let, at jth index r suffixes got completed from (i-1)th index.

So, assign a[i]=a[j-1]
This way, you added r to cur.
This completes our (K-N) good subarrays.
Note: (r<x) Always.

If some elements are yet to be filled after completion of (K-N) good subarrays, then assign the last filled element to all the unfilled indexes, because we don’t need more good subarrays.

Example of above approach (1 based indexing):
N=5, K=10
(K-N)=5
let r be number of good subarrays left to be found.
r=(K-N)

All good subarrays are considered of length >=2 from here, as good subarrays of length =1 are already considered.

At i=1,
cur=0, x=0, cur+(x) <=(K-N),
So, a[1]=1 (Distinct element assigned)

Array till now - [1]

At i=2,
cur=0, x=1, cur+(x) <=(K-N),
So, a[2]=2 (Distinct element assigned)

Array till now - [1,2]

At i=3,
cur=1, x=2, cur+(x) <=(K-N),
So, a[3]=3 (Distinct element assigned)

Array till now - [1,2,3]

At i=4,
cur=3, x=3, cur+(x) >(K-N),
Existing element should be assigned here,
r=(K-N)-cur =5-3 = 2
After counting r=2 suffixes from (i-1)th index, At j=2, r suffixes got counted from (i-1)th index.

So, a[4]=a[j-1]=a[2-1]=a[1]
a[4]=1

Array till now - [1,2,3,1]

This completes our 5 good subarrays. So, assigning the last filled element to all the unfilled indexes, because we don’t need more good subarrays.

At i=5,
a[5]=a[4]
a[5]=1

Final Array- [1,2,3,1,1]

4 Likes

Nice problem. I wonder how they wrote a Validator that runs in less than O(N^2) time.
Any idea @notsoloud ?

Bro I am unable to run your code it is giving this error
at java.util.StringTokenizer.(StringTokenizer.java:199)
at java.util.StringTokenizer.(StringTokenizer.java:236)
at Main$FastReader.next(Main.java:32) at Main$FastReader.nextInt(Main.java:41)
at Main.run(Main.java:94)

and I am not familiar with java >
I would suggest you try and run your program for all test cases from 5 5 to 5 15 and check your
I find my mistake this way only after the contest

I think they just counted number of contiguous distinct elements that would result in some number of good sub arrays, and then summed up those figures, which wouldn’t require O(N^2).

2 Likes

It can be easily solved with two pointer technique .

1 Like

Thanks bro, I will check it out.

can you explain Plz

Can someone tell me what’s wrong in my approach ?
Its giving wa on test 2

https://www.codechef.com/viewsolution/58156740

Output for 5 5 to 5 15

1 1 1 1 1
1 2 2 2 2
1 2 1 1 1
1 2 3 3 3
1 2 3 2 2
1 2 3 1 1
1 2 3 4 4
1 2 3 4 3
1 2 3 4 2
1 2 3 4 1
1 2 3 4 5

My solution also failed on the same test case with same approach

CPP Code
// CPP Program to find number of sub-arrays
// having distinct elements in O(N)
// Resource: https://www.geeksforgeeks.org/subarrays-distinct-elements/

#include<bits/stdc++.h>
using namespace std;

int number_of_subarrays(vector<int>& arr, int n) {
unordered_set<int> s;
int j = 0;
long long int ans = 0;
for(int i = 0; i < n; i++) {
while(j < n && s.find(arr[j]) == s.end()) {
s.insert(arr[j++]);
}
ans += j - i;
s.erase(arr[i]);
}
return ans;
}

int main() {
int t = 0;
cin >> t;
for(; t > 0; t--) {
int N = 0;
cin >> N;
vector<int> A(N);
for(int i = 0; i < N; i++) {
cin >> A[i];
}
cout << number_of_subarrays(A, N) << '\n';
}
return 0;
}



K can be as big as 5000050000, which will not fit in an integer. Use long instead of int.