Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) - B, C, D

D. Restore Permutation

The question
Suppose there is a full permutation $p[]$.
Given length is $n$ Sequence $s[]$, among $s_i$ by ：$p[]$ in , The first $i$ Than before $p_i$ All small elements $p_j$ The sum of .
requirement Restore the full arrangement $p[]$ And the output .

The original full permutation is unique ,$1\le n\le 2\cdot 10^5$.

Ideas
I thought so at first ：
First, the last occurrence in the sequence 0 The position of must be in full arrangement 1 The position of .1 The position of is determined .
Because the rear position is smaller than 1 Large full array elements s[i] It's all added 1, therefore ：
Put the number on all positions after this position s[i] All minus the current number 1, The last time 0 The position of must be in full arrangement 2 The position of .
Put the number on all positions after this position s[i] All minus the current number 2, The last time 0 The position of must be in full arrangement 3 The position of .
…
In this way, the original arrangement can be restored .

however , The time complexity of this idea is N^2.
Subtract a value from all the elements in the following interval , And save it and subtract it to become 0 The location of , I didn't expect any algorithm to be optimized , So let's go .

The positive solution is like this ：
Add the total permutation number All unfilled numbers Put it in a collection .
Consider each position from back to front , Then all the numbers in the set will be filled in 1~ Go to the current position . So if the current position is filled x, Then the ratio in the set x Small numbers must be in front , So the current s[i] If the sum of these numbers .
So according to the current location s[i] Then we can find the set neutralization as s[i] The minimum values of , Then the first number in the set that is larger than these values is p[i]. find p[i] Then delete it from the set , Ensure that there are unselected numbers in the set .

That is to say , Find the first satisfaction from the set every time The sum of all elements in the set less than or equal to this value is greater than s[i] The elements of , Then delete it from the set .

You can use tree arrays to maintain prefixes and , Each query logn, Delete logn.

So the time complexity is O(nlogn).

Code

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], c[N];
int ans[N];

int lbit(int x){
    
	return x & -x;
}

void add(int x, int y)
{
    
	for(int i=x;i<=n;i+=lbit(i)){
    
		c[i] += y;
	}
}

int query(int x){
    
	int sum = 0;
	for(int i=x;i>=1;i-=lbit(i)) sum += c[i];
	return sum;
}

bool check(int mid, int x)
{
    
	if(query(mid) > x) return 1;
	return 0;
}

signed main(){
    
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	for(int i=1;i<=n;i++) add(i, i);
	
	for(int i=n;i>=1;i--)
	{
    
		int l = 1, r = n;
		while(l < r)
		{
    
			int mid = l+r>>1;
			if(check(mid, a[i])) r = mid;
			else l = mid+1;
		}
		ans[i] = l;
		add(l, -l);
	}
	
	for(int i=1;i<=n;i++) cout << ans[i] << " ";
	
	return 0;
}

If you change the meaning of the topic , say ：
Give the result of finding the reverse chronology $c[]$ Array ,$c_i$ Indicates the position in the full arrangement $i$ All the following are better than $p_i$ The number of small positions .
ask , What is the original full arrangement ？

The same is true , Just walk from front to back , Then in the tree array , If a number is in the set, set it to 1, Otherwise, it is modified to 0.

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], c[N];
int ans[N];

int lbit(int x){
    
	return x & -x;
}

void add(int x, int y)
{
    
	for(int i=x;i<=n;i+=lbit(i)){
    
		c[i] += y;
	}
}

int query(int x){
    
	int sum = 0;
	for(int i=x;i>=1;i-=lbit(i)) sum += c[i];
	return sum;
}

bool check(int mid, int x)
{
    
	if(query(mid) > x) return 1;
	return 0;
}

signed main(){
    
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	for(int i=1;i<=n;i++) add(i, 1);
	
	for(int i=1;i<=n;i++)
	{
    
		int l = 1, r = n;
		while(l < r)
		{
    
			int mid = l+r>>1;
			if(check(mid, a[i])) r = mid;
			else l = mid+1;
		}
		ans[i] = l;
		add(l, -1);
	}
	
	for(int i=1;i<=n;i++) cout << ans[i] << " ";
	
	return 0;
}

Experience
I will encounter such a full array of problems in the future , You can think of putting all the undetermined numbers into a set .
For a given sequence , From front to back or from back to front , Each time you choose from this set , Delete after confirmation .

C. Magic Grid

The question
Construct a n*n Matrix , Satisfy the XOR and of each line , The XOR and of each column are the same .

$4\le n\le 1000,by4OftimesCount$

Ideas
Consider special circumstances ：$0$
XOR property ： continuity 4 The XOR value of the number is 0.
Then construct in sequence $4\ast 4$ After the matrix, it is found that the XOR sum of each column is also 0, But sequential construction is important for $12\ast 12$,$20\ast 20$ I'm not satisfied .
So for $x,x+4,x+8,x+12$ The XOR value of such four numbers is also 0, Try to construct such data .

So you can put $n\ast n$ The matrix of is divided into several $4\ast 4$ Matrix , Take the difference between two adjacent rows of each column as 4.

For simplicity , It can be structured like this ： Every time 4 Columns are treated as part , Each part is constructed in sequence .

8
0  1  2  3  | 32 33 34 35
4  5  6  7  | 36 37 38 39
8  9  10 11 | 40 41 42 43
12 13 14 15 | 44 45 46 47
16 17 18 19 | 48 49 50 51
20 21 22 23 | 52 53 54 55
24 25 26 27 | 56 57 58 59
28 29 30 31 | 60 61 62 63

set up x = n/4,
The first i Xing di j The number of columns is ：4*(i-1) + j-1 + ((j-1)/4)*16*x - (j-1)/4*4.

Code：

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 2010, mod = 1e9+7;
int T, n, m;
int a[N][N];

signed main(){
    
	Ios;
	cin >> n;
	
	int x = n/4;
	
	for(int i=1;i<=n;i++)
	{
    
		for(int j=1;j<=n;j++)
		{
    
			a[i][j] = 4*(i-1) + j-1 + ((j-1)/4)*16*x - (j-1)/4*4;
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	
// for(int j=1;j<=n;j++)
// {
    
// int x = 0;
// for(int i=1;i<=n;i++)
// {
    
// x ^= a[i][j];
// }
// cout << x << endl;
// }
	
	return 0;
}

B. Uniqueness

The question
Given a length $n$ Sequence of numbers , To delete a continuous interval so that the numbers in the sequence are different .
ask , What is the minimum length of the deleted interval ？

$1\le n\le 2000,1\le a_i\le 10^9$

Ideas
Method 1：
Half length , then n^2 Traversal position .
use map Mark , Overtime .
Change it to sort Post traversal judgment ,$O(n^{2}logn)$.

Method 2：
Traverse every position , Then traverse the length extending back from this position , If you extend to a position and find that there are no duplicates , Then stop .
The length and answer are min.

The key is how to judge whether there is no repetition number when extending to a position ？
Use all the numbers map Mark , Record the number of duplicates sum.
Go to a position , If the current number x There are numbers in the whole sequence mp[x] Not for 1, This indicates that the number is repeated , Delete the number , The number of repetitions of this number mp[x]-1, Number of repetitions sum-1.
If sum Reduced to 0 了 , It means that there is no repetition in the whole sequence , Then you can break, The current length and answer are min.
Time complexity $O(n^2)+n^{2}TimempfuckdoConsumptionwhen$.

Code
Method 1：

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N], t[N];

bool check(int mid)
{
    
	for(int i=1;i<=n-mid+1;i++)
	{
    
		int cnt = 0, flag = 0;
		for(int j=1;j<i;j++){
    
			t[++cnt] = a[j];
		}
		for(int j=i+mid;j<=n;j++)
		{
    
			t[++cnt] = a[j];
		}
		sort(t+1, t+cnt+1);
		for(int j=2;j<=cnt;j++){
    
			if(t[j] == t[j-1]) flag = 1;
		}
		if(!flag) return 1;
	}
	return 0;
}

signed main(){
    
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	int l = 0, r = n;
	while(l < r)
	{
    
		int mid = l+r>>1;
		if(check(mid)) r = mid;
		else l = mid+1;
	}
	cout << l;
	
	return 0;
}

Method 2：

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

#define Ios ios::sync_with_stdio(false),cin.tie(0)
map<int,int> tmp, mp;

const int N = 200010, mod = 1e9+7;
int T, n, m;
int a[N];

signed main(){
    
	Ios;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i];
	
	int sum = 0;
	for(int i=1;i<=n;i++)
	{
    
		tmp[a[i]] ++;
		if(tmp[a[i]] != 1) sum ++;
	}
	
	int ans = 1e9;
	for(int i=1;i<=n;i++)
	{
    
		mp = tmp;
		int t = sum;
		
		for(int j=i;j<=n;j++)
		{
    
			if(mp[a[j]] != 1){
    
				mp[a[j]] --;
				t --;
				if(t == 0){
    
					ans = min(ans, j-i+1);
					break;
				}
			}
		}
	}
	if(ans != 1e9) cout << ans;
	else cout << 0;
	
	return 0;
}