The solution to Problem C : (driven by observations and stuff) quite similar to the editorial :122867887

the variables stagesa stands for mine(in problem) and stagesb stands for Iliya's stages( can be thought as pointers) !

Hope its helps !

There are some other approaches to problem D:

Maintain a set of numbers from 1 to n. This set will contain the remaining elements which can be used.

First, place all the first occurring numbers to their corresponding indexes and mark them visited. For example, if array A is : {6,6,6,1,1,1} , then after the first step our B array should look like this : {6,0,0,1,0,0} , i.e., we placed the first occurring 2 and 1 at the same index for now. Since we placed 2 and 1 so remove it from the set. Set will contain {2,3,4,5}

Now traverse from left to right, when a particular index is not visited, then we have to place some value at that index. I will take out the first element from set (you can take out any remaining element, doesn't matter) and let that be val. Now if val != index then we can simply put that value at the current index and move forward. If val == index, then first look up the position of a[cur_id] and then place val at pos[a[cur_id]] and a[cur_id] will contain the correct or initial value.

In the given example, we will go to 2nd index (as its not visited), take out first element from set which is 2 ... index==2 so check for the expected value at index 2 which is 6 and we have placed 6 at index 1. So, swap these , i.e, place 2 at index 1 and 6 at index 2. Now move forward, index 3 is not visited. Take out first element from set which is 3 ... Expected value 6 .. position of 6 : 2nd index , so place 3 at 2nd index and 6 at index 3. Now we will go to index 5, Take out first element which is 4 . Index != 5 so place 5 at that index and move right.

Hope it helps
My AC Code : https://mirror.codeforces.com/contest/1530/submission/122867049

Interesting problems, especially E.

Thanks for contest!

Another Solution for D : First, Place all the values of b[i]=a[i] where a[i] is chosen to given gift by only one member

Then, Those who are desired by more than one person give them any random person as it wont matter (Explained later).

Then, maintain of set of variables who have not yet received any gift from any person and start from index 0 and the person who hasn't chosen yet ,give him a gift not equal to itself i.e either beginning element of set and ending element of set.

Now comes the main part u should notice that there can be atmost one value equal to itself and and the person whom this index wished to give a gift must have atleast 2 person desiring him so simply just find another index with same value of a[i] and just swap the two and you will acheive the desirable state.

Solution Link

kuhn algorithm work for D in 250 ms.it is believed that asymptotics for kuhn is O(NM) howewer in practice it is quite close to liniar.

As I see in other contestants' code, most popular solution for F is some kind of DP.

I have just passed straightforward O($$$2^n \cdot n^2$$$) solution (brute force + OR-convolution).

Even with whole bunch of pragmas it 122869425 barely fits in TL :). Was it intended to catch TLE, or my implementation is bad?

UPD: I optimized brute-force part 122870796 , now it fits well, but I'm still interested if it was intended to pass or not.

For problem D, I was really glad to find a solution without using Graphs (since I am bad at Graph Theory). Hint: Try to satisfy as many wishes as you could (which is the number of different integers from the input). Then, we will have some people who do not have somebody to give a gift to. We can give them anybody who is not given yet. However, we should check if there is somebody who is matched with himself. It can be proven that in that case the optimal strategy is to satisfy the first "wish" of that person. Not really sure if you could fully understand me, tho. 122840888

Great Contest, thanks tourist. Highly appreciated

my solution to D.

It is a greedy approach and doesn't use graph. Hope it helps.

122817534

Can somebody please explain to me why this code gets accepted, but during the contest I got on the same code WA? There is only one very small difference between those 2, the AC one has a forgotten cerr into it, you can check with a diff tool :)

Problem E really required careful case analysis. My solution got wrong answer on pretest 6 just because of missing a single -1. qwq

I think it is a nice problem to test participants' carefulness！

I really liked $$$D$$$. Construct directed graph $$$G$$$ with edge from $$$i$$$ to $$$j$$$ if $$$i$$$ wants to give a gift to $$$j$$$. Now store $$$2$$$ sets: $$$Unliked$$$ and $$$Popular$$$. A element $$$i$$$ is in $$$Unliked$$$ if $$$d_G^{-}(i) = 0$$$ and in $$$Popular$$$ if $$$d_G^{-}(i) > 1$$$. Now while $$$Unliked$$$ is non empty, take a Unliked person and a person who wants to give a gift to a Popular person and is not the same as the chosen Unliked person. Now just delete the edge from this person to the Popular person and add an edge from person to Unliked person. Remove this Unliked person from Unliked, and if the Popular person, is no longer Popular remove him from Popular set as well. An implementation is here: https://mirror.codeforces.com/contest/1530/submission/122822889

ecnerwala Can you please upload the video the stream on youtube? Quality 1080p lags a lot with many of ours internet.

I did an overkill for C. I used an ordered_multiset. Though I feel a bit stupid, I think the template I used is pretty amazing : 122832592.
This would actually be useful in solving a more general problem: lets say instead of predicting in how many minimum moves we can win, the game continues with different scores being added to each and we need to find the move at which our score will be atleast the opponent's. In this case we would require (or atleast this is one way) order statistics on our multiset.

The promble E 1530E - 12 - Minimax, I got a wrong answer on test 2 with this checker log:

wrong answer 48th words differ — expected: 'ff', found: 'ff'

I don't know what is that means.

122886321

So I used the exact idea that the solution mentions, however I can't figure out (for literally hours) what is wrong with my code since everything I coded seems logical. Can anyone help me please, thanks in advance!

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

void solve() {
	int n;
	cin >> n;
	
	vector<int> a(n), b(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++) cin >> b[i];
	
	sort(a.rbegin(), a.rend());
	sort(b.rbegin(), b.rend());
	
	int k = n - (n / 4);
	int sa = 0, sb = 0;
	
	deque<int> mxa, mnb;
	for(int i = 0; i < k; i++) {
		sa += a[i];
		mxa.push_back(a[i]);
		
		sb += b[i];
	}
	
	for(int i = k; i < n; i++) {
		mnb.push_back(b[i]);
	}
	
	if(sa >= sb) {
		cout << 0 << '\n';
		return;
	}
	
	int curn = n;
	while(true) {
		curn++;
		if(curn % 4 != 0) {
			// only add new element
			sa += 100;
			if(!mnb.empty()) {
				sb += mnb.back();
				mnb.pop_back();
			}
		} else {
			// remove one smallest element
			if(!mxa.empty()) {
				sa -= mxa.back();
				mxa.pop_back();
			} else {
				sa -= 100;
			}
			
			sa += 100;
		}
		
		if(sa >= sb) break;
		
	}
	
	cout << curn - n << '\n';
}

int main() {
    int t; cin >> t; while(t--) solve();
}

Sad to see that simply changing long long into int can make a huge difference to not only the result but also my current rating, though my solution has a complexity of 2^nn^2 (actually it is 2^{n+2}n^2!).

TLE : 122856541

AC : 122887934

btw how to type LaTeX in Codeforces?

In problem D, my code is of order O(n) but still it took 1918ms (phew!). Can someone tell me why?

Algo

v stores the input. flag is 1 for the positions which are requested and it also stores who requested them. left stores the positions not requested by anyone. v1 stores the output. flag1 stores which numbers are used in real time.

If the requested number has not been used, then we use it. Else, we use the left array. If this number is equal to its position, we swap it with the position which has the number it requested.

Code: 122834097

PS: Sorry for such a trivial question. Just started learning STL.

My solution for problem D.

First of all we store each element's frequency in an array .

Then We traverse the array and each element that its frequency is 0 we store them in a deque (you will understand why deque in a bit).

Next We traverse the array (doesn't matter from left to right or from right to left) and we look for some cases:

1. If the frequency of whom person i wants to gift is 1 , then we give him it , OR there is only 1 number left in the deque , and it equals to i , then we give i a[i] .

2. if the above cases are not satisfied , then we look to the deque.

if the first element in the deque is equal to i , then We give him the last element , else we give him the first element .

Finally the answer is the number of elements in the array (n) minus the number of elements from 1 to n that there frequency is 0 .

CODE

A solution for problem C. Simple and Easy to understand, Hope it helps ! Submission Link — 122895932

Just did D a little different so I thought I'd comment how out here (in the loving memory of my multiple wrong submissions prior to the AC UwU)

Do correct me if I'm wrong anywhere, and I apologize if it's a really inferior approach to be explaining and/or very poorly explained.

Okay so what we do know is that the numbers appearing more than once in the array need to be replaced with the ones between $$$1$$$ to $$$n$$$ that are not appearing at all (since everyone must get a gift). It is given that no employee initially is assigned to themselves as secret santa, so the only self assignments that can potentially be caused would be because of us replacing repeated numbers with the absent ones. This self assignment can be easily avoided as shall be discussed in the approach:

Intuition:

Let the given array be called $$$a$$$. Firstly we make a list of numbers that are absent in $$$a$$$ (let's name it $$$se$$$) and also maintain an array to count the number of appearances of the integers $$$1$$$ to $$$n$$$ in $$$a$$$ (say $$$b$$$). Now we traverse $$$a$$$ starting from index $$$0$$$ (iterator of $$$se$$$ starting also from the first element of $$$se$$$) and each time the number we encounter in $$$a$$$ has more than $$$1$$$ appearances indicated by $$$b$$$ we replace it with a number from $$$se$$$ and update its count in $$$b$$$ decrementing it by $$$1$$$ and moving the iterator of $$$se$$$ to the next unused number in it.

Carrying out the Replacement:

Since as has been explained in the editorial, the maximum fulfilled wishes will always be the equal to the number of different integers in the given array, the order of replacement is not of any consequence as long as we are cautious (while replacing repeated numbers with those form $$$se$$$) about not assigning the employee as his own secret santa, i.e. the number we choose from $$$se$$$ for the replacement must not be equal to number of the employee.

Among the numbers in $$$se$$$, there will at most only be one such number for each employee that could result in self assignment. Thus while iterating through $$$a$$$ (suppose we're at index $$$i$$$) and $$$se$$$ (suppose the iterator points to $$$j$$$-th element), if the number of appearances of $$$a_i$$$ are more than $$$1$$$ in $$$b$$$ we can encounter two possibilities:

1. Employee number is equal to $$$j$$$-th element of $$$se$$$.

2. Employee number is different than $$$j$$$-th element of $$$se$$$.

In case of the second possibility, we can replace $$$a_i$$$ with the $$$j$$$-th element of $$$se$$$ and increment $$$j$$$, thus eliminating the possibility of assigning the same number initially absent in $$$a$$$ to more than one employees. In case of the first possibility however, we replace $$$a_i$$$ with $$$j+1$$$-th element of $$$se$$$, since $$$j$$$-th element remains unused, we swap the $$$j$$$-th and $$$j+1$$$-th elements of $$$se$$$ and increment $$$j$$$. This results in the next element we encounter through the iterator of $$$se$$$ being the originally $$$j$$$-th element hence prevented from being skipped.

Code:

122890172 (my very unclean submission I suppose.)

Time Complexity:

It would take this $$$O(n)$$$ to reach an answer as the maximum number of runs the inner while loop performs is 2, a constant. (I sure do hope I'm not wrong)

Problem B simple explanation Putting Plates

Problem A Simple Explanation Problem A

Short code for B (Perl) — 122869086

Can some tell me what is wrong with my code I am getting a WA on C.

#include<bits/stdc++.h>
using namespace std;
#define     all(x)          x.begin(),x.end()
#define     rall(x)         x.rbegin(),x.rend()
#define     ll              long long
#define     ld              long double
#define     precise(x)      fixed<<setprecision(x)
#define     mb              make_pair
#define     pb              push_back
#define     ub              upper_bound
#define     lb              lower_bound
#define     t()             int t;cin>>t;
#define     pll             pair<ll,ll>
#define     vl              vector<ll>
#define     vll             vector< pll >  
#define     fast            ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define     ff              first
#define     ss              second
#define 	pf 				push_front
#define     pq              priority_queue
int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; 
int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1};

string yes = "YES";
string no = "NO";
ll mod = 1000000007;
ll MAXN = 100001;

void print(vector<ll> &a)
{
	for(auto i:a)
		cout<<i<<" ";
	cout<<endl;
}

void print(vll &a)
{
	for(auto i:a)
		cout<<i.first<<" "<<i.second<<endl;
}

void print(vector<vl> &a)
{
	ll n = a.size();
	ll m = a[0].size();
	for(ll i=0; i<n; i++)
		{
			for(ll j=0; j<m; j++)
			{
				cout<<a[i][j]<<" ";
			}
			cout<<endl;
		}
}

bool isprime(ll x)
{
	for(ll i=2; i*i<=x; i++)
	{
		if(x%i == 0)
			return false;
	}
	return true;
}

void factor(vl &fac, ll n)
{
	ll temp = n;
	for(ll i=2; i*i<=temp; i++)
	{
		if(n%i == 0)
		{
			fac.pb(i);
			while(n%i == 0)
				n /= i;
		}
	}
	
	if(n>1)
		fac.pb(n);
}

void solve()
{
	ll n;
	cin>>n;
	
	vl a(n,0), b(n,0);
	ll sa = 0, sb = 0;
	
	for(int i=0; i<n; i++)cin>>a[i];
	for(int i=0; i<n; i++)cin>>b[i];
	
	sort(rall(a));
	sort(rall(b));
	
	int k = n-n/4;
	for(int i=0; i<k; i++)
	{
		sa += a[i];
		sb += b[i];
	}
	
	if(sa>sb)
		{
			cout<<"0"<<endl;
		}
	else
	{
		int temp = n-k;
		int index = k;
		int ans = 0;
		while(sa<sb)
		{
			sa += 100;
			if(temp>0)
			{
				sb += b[index];
				index++;
				temp--;
			}
			ans++;
		}
		cout<<ans<<endl;
	}
}

int main()
{
	fast;
	bool test_case = true;
	
	if(test_case)
	{
		ll t;
		cin>>t;
		
		for(ll i=1; i<=t; i++)
			{
				solve();
			}
	}
	else
		solve();
	
	return 0;
}

For problem C, it's also possible to do a binary search on how many exams are needed. It's O(n) complexity to answer "Take X more exams, if I can have a no-lower score or not"

Can anyone please help with problem C, what's wrong with my solution submission ?

I've tried many times, couldn't find the issue.

My simple solution for D , without using any sort of graphs: First try to assign each person, his choice if that choice has not been assign yet, maintain a bool vector to store the gifts which have been assigned and index array to store indexes which have not been assigned any gifts yet. Now construct a set containing gifts which have not been assigned. Now iterate for each index, if that index has not been assigned gift,then,there are two cases (i) first element of set is not equal to current index ,then assign that gift and erase it from set. (ii) Its equal to current index , since atmost 1 gift can be equal to current index,then we will assign next gift to current index and erase it .Now if set contains only 1 element and its equal to current index ,then we will swap the gifts of current index and index which has been assigned the choice of the current index ,this will not affect the final answer

Actually we can brute force C: 122875589

tourist Any updates on the editorial for the problems F,G,H?

I have different solution for D:
First of all, lets construct bipartite graph with edges from i (left side) to a[i] (right side)
It is clear, that answer is maximum matching in this graph + some extra edges
Lets find maximum matching and fill $$$answer$$$ with it
Now we have some people, who doesn't give and who doesn't recieve gifts
Lets assign them to each other and if we got collision that $$$i$$$ should give to $$$i$$$, then just swap that $$$i$$$ gives to $$$a[i]$$$ and someone who gives to $$$a[i]$$$ gives to $$$i$$$
It works in $$$O(MaximumMatching) + O(n)$$$. My $$$O(nm)$$$ Khun implementation (based on this Burunduk1's article) works under 400ms: 122962186.

Please update editorial for problem F. Or can someone help me with it ?

:3

Can anyone explain their DP solution for F ? The one which is $$$O(2^{n} n^{2})$$$

In problem F, to optimize the solution to $$$O(2^n \cdot n)$$$ using the first way described, how to actually achieve that complexity? Wouldn't updating the products and rolling back (in $$$O(n)$$$) for each possible state of $$$f(i, S)$$$ calculated recursively (for which there are $$$(n + 2) * 2^{(n + 2)}$$$ states) take $$$O(2^n \cdot n^2)$$$ in total?

Can anyone explain the thought process of reducing problem F from 2^(2n+2) to 2^(n+2) if one is following the basic inclusion-exclusion process?

does E really **** interesting ???

Greedy solution for problem D:

First, iterate through a[i] and greedily assign giftees. If a[i] is already taken, do nothing. Additionally, the maximum number of satisfied people is simply the number of unique elements, so we can calculate that here too.

This leaves a lot of people that still need to find a person to gift to. We can again greedily assign them using a 2 pointers method.

Now everyone should be paired up, but we run the risk of pairing someone up with themself. We will iterate through the current answer to find such scenarios. Let's call a person who gives a gift to himself x. If that occurs, we can simply swap him with the person who had originally taken his intended giftee. Let's call the person who took x's intended giftee y. This swap will always retain the optimal answer, because we are now satisfying x's requirement, and breaking y's so there is a net change of 0 requirements met. The construction of this candidate solution via the previous 2 steps also guarantees it contains no duplicate elements, so the swap also cannot make another self-match.

This process can continue until all self-matches are eliminated, and we are left with a valid, optimal answer.