DISTK - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

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

DIFFICULTY:

Easy

PREREQUISITES:

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
LL seed = chrono::steady_clock::now().time_since_epoch().count();
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 readInt(char endd) {
    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) {
    long long ret = readInt(endd);
    assert(ret >= L && ret <= R);
    return ret;
}
long long readIntSp(long long L, long long R) {
    return readInt(L, R, ' ');
}
long long readIntLn(long long L, long long R) {
    return readInt(L, R, '\n');
}
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() {
    int n = readIntSp(1, N);
    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() {
    int T = readIntLn(1, TMAX);
    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 ;(
Code link - https://www.codechef.com/viewsolution/58136319

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. :frowning:

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 :smiley:

  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 :slight_smile: 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.

As N good subarrays are already added to the answer. So, We will further add (K-N) good subarrays.

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]

My AC Solution - Click Here

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
Exception in thread “Main” java.lang.NullPointerException
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)
at java.lang.Thread.run(Thread.java:745)

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. :slight_smile:

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

He was probably talking about this.

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.