ARRT - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Prasant Kumar
Tester : Riley Borgard
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy

PREREQUISITES:

Observation

PROBLEM:

Given a sequence A which contains distinct elements and array B which also contains distinct elements of size N, and 1 \leq A_i, B_i \leq 2 \cdot N.

You can rotate B as many times as you want. Print lexicographically smallest array C, C is defined as C_i = (A_i + B_i) \% N, here i is i-th element from left.

If we have two arrays x and y, then x is lexicographically smaller if x_i < y_i, where i is the first index in which the arrays x and y differ.

EXPLANATION:

To find the lexicographically smallest array, one needs to find those arrays which have their starting number smallest among all possible arrays that can be formed.

Hence we need to find the such starting points of an array B which gives us C_0 = (A_0 + B_i) \% N, to be the smallest number among all possible starting points.

Claim: There can exist at most 2 starting points.

Proof

Given that all the elements of the array B lie in the range of [1,2*N] and are distinct. Let’s say some value X that lies in the array B gives us the minimum value. Then C_0 will be:

C_0 = (A_i + X)\% N
C_0 = A_i\%N + X\%N

Now let’s see what are the other possible values by which we can replace X and still get the same C_0. As

X\%N = (X+k*N)\%N

Hence we can replace X with (X+k*N). Now, what is the range of k such that (X+k*N) lies in the range of [1,2*N] such that X lies in the range of [1, N].

(X+k*N) \le 2*N

We can see that k cannot be greater than 2, hence there exists at most 2 values for which C_0 will be smallest among all possible choices and those are X and X+N.

Finally, we can find at most two arrays, and print the lexicographically smallest array out of them.

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Author
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"

bool cmp(vector<int> &a,vector<int> &b){
	
	int n=a.size();
	for(int i=0;i<n;i++){
		if(a[i]==b[i])continue;
		
		return (a[i]<b[i]);
	}
	return 1;
}

signed main(){

	ios_base::sync_with_stdio(0) , cin.tie(0);
//	freopen("nt.txt","r",stdin);
//	freopen("new_out.txt","w",stdout);
	int t;cin>>t;
	while(t--){
		int n;cin>>n;
		int arr[n],brr[n];
		for(int i=0;i<n;i++){
			cin>>arr[i];
		}
		for(int i=0;i<n;i++){
			cin>>brr[i];
		}
		int mini=1e9;
		for(int i=0;i<n;i++){
			int temp=(arr[0]+brr[i])%n;
			mini=min(temp,mini);
		}
		
		vector<int> st;
		for(int i=0;i<n;i++){
			int temp=(arr[0]+brr[i])%n;
			if(temp==mini){
				st.push_back(i);
			}
		}
		vector<vector<int>> permutations;
		
		for(int j : st){
			vector<int> temp;
			for(int i=0;i<n;i++){
				temp.push_back((arr[i]+brr[j])%n);
				j++;
				j%=n;
			}
			permutations.push_back(temp);
		}
		
		sort(permutations.begin(),permutations.end(),cmp);
		
		for(int x : permutations[0]){
			cout<<x<<" ";
		}cout<<endl;
		
	}



	return 0;
}


Tester

#include <bits/stdc++.h>

#define ll long long
#define sz(x) ((int) (x).size())
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
#define pii pair<int, int>
#define rep(i, a, b) for(int i = (a); i < (b); i++)
using namespace std;
template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

void solve() {
    int n;
    cin >> n;
    vi a(n), b(n);
    rep(i, 0, n) cin >> a[i];
    rep(i, 0, n) cin >> b[i];
    int bmod = n;
    vi best;
    rep(i, 0, n) {
        int val = (a[0] + b[i]) % n;
        if(val < bmod) {
            bmod = val;
            best.clear();
        }
        if(val == bmod) best.push_back(i);
    }
    vector<vi> vc;
    for(int i : best) {
        vi v;
        rep(j, 0, n) v.push_back((a[j] + b[(i + j) % n]) % n);
        vc.push_back(v);
    }
    vi c = *min_element(all(vc));
    rep(i, 0, n) cout << c[i] << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int te;
    cin >> te;
    while(te--) solve();
}
Editorialist
// Subtask 2

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

#define int long long

void solve()
{
	int n;
	cin>>n;

	int a[n],b[n];

	for(int i=0;i<n;i++)
	{
		cin>>a[i];
		a[i] = a[i] % n;
	}

	int mi = n-1;

	for(int i=0;i<n;i++)
	{
		cin>>b[i];
		b[i] = b[i] % n;

		mi = min(mi,(a[0]+b[i])%n);
	}

	set<vector<int>> s1;

	int co = 0;

	for(int i=0;i<n;i++)
	{
		if((a[0]+b[i])%n==mi)
		{
			co++;
			vector <int> v1;

			for(int j=0;j<n;j++)
				v1.push_back((a[j]+b[(i+j)%n])%n);

			s1.insert(v1);
		}
	}

	assert(co<=2);

	vector <int> ans = *s1.begin();

	for(auto itr: ans)
		cout<<itr<<" ";

	cout<<"\n";
}

int32_t main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
 
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

6 Likes

Editorialist OP (Wonderful solution)!!! Mind Blowing! Good Job

2 Likes

can anyone help me @ssjgz
https://www.codechef.com/viewsolution/49359321

can anyone clarify why we are replacing X with (X + k*N)?

Let’s say you get remainder r while dividing X by N. Then what are the values which gives the same remainder r. Can it be written in the form of (X+k*N)

1 Like

Ab mein itna bhi khaas nahin :crazy_face:

3 Likes

Can anyone tell me whats wrong with My solution
@cherry0697

Consider the test input:

1
12
1 2 3 4 5 6 7 8 9 10 11
19 17 18 16 15 14 13 12 11 10 9

Is it for me @ssjgz. Isn’t it against the constraints.

That was intended for you, yes :slight_smile: Which constraint does it violate (I didn’t actually do this problem :p)?

array B can have maximum of n elements( 12 in this case) here is the problem link.

1 Like

Whoops - silly me :slight_smile: Try this one:

1
12
1 2 3 4 5 6 7 8 9 10 11 12
19 17 18 16 15 14 13 12 11 10 9 8
1 Like

It fails on the following test input (hopefully I’ve gotten it right this time :)):

1
8
14 11 10 4 7 1 13 16
14 11 8 15 16 1 5 3
1 Like

If we take a[0] % n and search for n - a[0] %n if its present in array b[I] % n we can get max 2 values else we take atmost two values which is smallest among them (if a[I] is zero we search for zero)
Correct me if I’m wrong

what does the term " pairwise distinct elements " means . Cant it simply be " distinct " ?
Or its just for confusing ?

2 Likes

It means if we take any two numbers from the array it should not be same

can anyone help me with my code
https://www.codechef.com/viewsolution/49364362

Consider the test input:

1
2
2 1
2 4

Hey @cherry0697 could you please help me with the solution of mine it’s giiving WA but I am trying to do the exact same thing.
Solution link : Solution: 49364831 | CodeChef