BillLee's blog

By BillLee, history, 6 weeks ago, In English

"The following content has been translated into English using AI. If you don't understand, you can refer to my original text in Chinese. I hope this gives you more context." [Your text to link here...](https://www.yuque.com/acyee/yutpdt/qlyrfvg84sefvxxa?singleDoc# 《166 (Rated for Div. 2)》) https://www.yuque.com/acyee/yutpdt/qlyrfvg84sefvxxa?singleDoc# 《166 (Rated for Div. 2)》

In the solution, there is a notable point regarding finding a position—the first suboptimal position.

This suboptimal position arises in a situation where the previous positions (which he is skilled at) are already filled, requiring him to switch to a position he is not skilled at.

However, I think the description is not quite accurate. When this position is the last position, and the previous positions are already satisfied, it does not matter what position he takes. At this point, the solution's code defines BAD=-1, etc. The solution seems to classify and discuss the last position, focusing on how to use the last position. I find it a bit confusing.

I believe this approach is different from the essential concept of "possible changes" versus "fixed positions". It seems like a workaround. For the last position, if all previous positions are satisfied, he inevitably cannot take the position he excels at. At this point, he overlaps with the definition of suboptimal (unable to take the preferred position). I can identify the suboptimal position within the entire talent sequence using the condition that he cannot take his preferred position.

Considering the solution's "possible changes in position", I call this position a "substitute". Why does a substitute exist? Because he cannot take his preferred position, which implies that his preferred position is already filled by someone before him. He and those after him can only take another type of position. Combining this with the "fixed positions" mentioned in the solution:

Before the substitute, everyone takes their preferred position based on their abilities. For the substitute, if someone ahead is absent, he will take their position if he is skilled at it; otherwise, he will continue to take the suboptimal position. For those after him, the positions are fixed and they will continue taking the substitute’s unskilled position.

This is the "fixed positions" in the solution. For the "possible change in position," the substitute is forced to take the suboptimal position. If someone ahead with the same skill is absent, the substitute will take the preferred position, and those behind him will continue taking the suboptimal positions (since the previously liked position is filled by the substitute).

Example:

3 1
4 3 3 4 1
5 5 4 5 2

In this example, the substitute position is the second one. Normally, the first four applicants satisfy the requirement.

If the first tester is absent, the substitute takes the tester's position (changing the position). Those after the substitute continue to take the programmer positions (fixed). If the second substitute is absent, those after continue with the programmer positions (fixed). If the third programmer is absent, the substitute remains a programmer, and so does the last one. If the fourth programmer is absent, the substitute remains a programmer, and so does the last one. If the fifth programmer is absent, the substitute remains a programmer.

Why do I call the suboptimal one a substitute? Because the substitute fills in for the absent position. Essentially, when the "possible change" situation occurs, he is the first one forced to take the suboptimal position. He takes the preferred position, and those after him continue with the suboptimal positions, creating the fixed positions for the rest.

  1. When he is the last person, he fills any absent position before him:
0 4
4 3 3 4 1
5 5 4 5 2
1 3
5 3 3 4 1
4 5 4 5 2
  1. When he is not the last person, he fills positions along with the last person. When someone is absent among the first n+m people, the last person will fill the position, which will be a suboptimal position because it follows the substitute. If the absent person is ahead of the substitute, he fills the position as needed. If a suboptimal position is absent, the substitute continues his suboptimal position. If the preferred position is absent, the substitute takes the preferred position. If the substitute himself is absent, it can be considered as missing the substitute, and the code handles this similarly.

If the absent person is after the substitute, the substitute remains in the suboptimal position.

------------------------------------------------------------------------------------------------------------------------ Code Implementation:

Use a structure to create a talent with programming skill, testing skill, and the preferred position type. In my code, programmers are 1, and testers are 2. A for-loop iterates through all talents with two purposes:

Find the substitute position. Sum up the "normal recruitment" total, assuming the substitute is absent. (How to sum up? If his preferred position is not full, he takes it; otherwise, he takes the suboptimal position. We know this is the case before the substitute, but after the substitute, everyone takes the suboptimal positions).

I use cnt_n and cnt_m to record the current recruitment status and check if it is full. The for-loop iterates through all talents, checking each one as absent, letting the substitute take their type. If the type changes, update the sum accordingly.

The output is the "normal recruitment" minus the absent one, plus the substitute filling in.

#include <bits/stdc++.h>
 
#define pb push_back
#define mp make_pair
#define x first
#define y second
 
using namespace std;
 
typedef long long ll;
typedef long double ld;
 
int n, m;
 
struct one {
	int p, t, ty;
} a[200005];
 
void solve() {
	cin >> n >> m;
	const int N = n + m + 1;
	for (int i = 1; i <= N; ++ i) cin >> a[i].p;
	for (int i = 1; i <= N; ++ i) {
		cin >> a[i].t;
		a[i].ty = (a[i].p > a[i].t ? 1 : 2);
	}
	int cnt_n = 0, cnt_m = 0, idx = 0;
	ll sum = 0;
	for (int i = 1; i <= N; ++ i) {
		if (!idx && (a[i].ty == 1 && n == cnt_n || a[i].ty == 2 && m == cnt_m)) {
			idx = i;
			continue;
		}
		if (a[i].ty == 1 && n == cnt_n) sum += a[i].t, ++ cnt_m, a[i].ty = 2;
		else if (a[i].ty == 2 && m == cnt_m) sum += a[i].p, ++ cnt_n, a[i].ty = 1;
		else if (a[i].ty == 1) sum += a[i].p, ++ cnt_n;
		else sum += a[i].t, ++ cnt_m;
	}
	
	for (int i = 1; i <= N; ++ i) {
		if (a[i].ty == 1) cout << sum - a[i].p + a[idx].p;
		else cout << sum - a[i].t + a[idx].t;
		cout << ' ';
	}
	cout << "\n";
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0), cout.tie(0);
	int tt; cin >> tt;
	for (int i = 1; i <= tt; ++ i) solve();
		
	return 0;
}
  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by BillLee (previous revision, new revision, compare).

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for the explanation!

  • »
    »
    6 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    A little think, haha. I mean, the solution talked a lot about the core aspects of the problem, but then it just went off the rails with clumsy case-by-case analysis, which was totally out of sync with all the insightful groundwork it laid. It's weird, and I'm convinced there's gotta be a more elegant approach that leverages the essence of the problem. I dumbly suggested something that I now have to struggle to explain, thinking there's got to be a cleaner way to do this. Anyway, thanks for your kind words. I'm questioning my existence at this point, lol.