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:
Now let’s see what are the other possible values by which we can replace X and still get the same C_0. As
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].
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;
}
Which constraint does it violate (I didn’t actually do this problem :p)?