It initially felt like a classic problem. 15 minutes in, I found a $$$O(N^2)$$$ solution, using vector insertion. The solution is as follows:

We process the $$$N$$$ students one by one. Store the current vector of the current relative order of the already processed students. Then, we attempt to insert the next student at the correct position.

Observation: If you process a student, if it is not inserted at the back, then it cannot have the highest $$$P[i]-i$$$.

Proof: Consider the element right after $$$i$$$ in the final array $$$P$$$. It will always be larger.

Observation: When processing a student, it is always better to always put the student with the highest possible $$$P[i]$$$.

Proof: When you insert at a position $$$k$$$, then all the $$$P[x]$$$ at positions $$$k, k+2, \dots, i-1$$$ will increment by 1. Thus, by keeping it as right as possible, we increase the minimum number of such positions. Although if you were to insert at a lower position, the value of $$$P[i]-i$$$ is small, but it cannot be the largest.

So, we can linear scan for the largest position you can put in: You can only put it in a location such that either all of the $$$A[x]$$$ before it are less, or all the $$$B[x]$$$ before it are less. Then, you can insert it in in $$$O(N)$$$ time using std::vector::insert.

Overall time complexity: $$$O(N^2)$$$.

vector<int> ans;
for (int i = 0; i < N; i++) {
  int best = -1;
  for (int j = 0; j < ans.size(); j++) {
    if (A[ans[j]] < A[i]) best = max(best, j);
    else break;
  }
  for (int j = 0; j < ans.size(); j++) {
    if (B[ans[j]] < B[i]) best = max(best, j);
    else break;
  }
  ans.insert(ans.begin()+best+1, i);
}
int a = 0; for (int i = 0; i < N; i++) a = max(a, i-ans[i]);
return a;

Now, we can make better use of the first observation to avoid the bottleneck of insertions (Because the scan can be done in $$$O(\log N)$$$ time using a segment tree).

We can instead only store the points that are the new largest values. Then, when processing an element, perform binary search on a segment tree to find the correct position where it can be "inserted". If this element is not at the end, notice that to accommodate for this new element, is equivalent to a point update to the segment tree, and a range increment to the values of $$$P[i]-i$$$. Otherwise, it is just add it to the end.

This gives time complexity $$$O(N \log N)$$$. This gets you 83 points, which was the score I got in contest.

Unfortunately, I cannot download my submissions to day 1 anymore, and I am unwilling to code this, so no code.

Realize that there is not a need to process from the front. Instead, we can process from the back! Here, we make the key observation:

Observation: The last person must have the highest $$$A[i]$$$ or $$$B[i]$$$ among the first $$$i$$$.

Why am I restating the problem condition? Just stimulate this from the back, line sweeping to ensure that you don't accidentally reach one that has already been taken. There, you would take the larger index, as the smaller would give a larger $$$P[i]-i$$$. This runs in $$$O(N)$$$ time. In fact, the solution code is less than 20 lines long.

int takenA[N],takenB[N],invA[N],invB[N];
memset(takenA,0,sizeof(takenA));
memset(takenB,0,sizeof(takenB));
for (int i = 0; i < N; i++) invA[A[i]]=i, invB[B[i]]=i;
int ptr1=N-1,ptr2=N-1;
int ans=0;
for (int i = N-1; i>=0;i--) {
  while (ptr1>=0 && takenA[ptr1]) ptr1--;
  while (ptr2>=0 && takenB[ptr2]) ptr2--;
  int best = -1; 
  if (ptr1 != -1) best=invA[ptr1];
  if (ptr2 != -1 && invB[ptr2] > best) best=invB[ptr2];
  if (i-best > ans) ans=i-best;
  takenA[A[best]]=1;
  takenB[B[best]]=1;
}
return ans;

Very weirdly, in contest, I tried coding minimum excluded from the start. (While AC is just maximum excluded from the back, note the resemblance.) This was sadly because of a careless mistake with working on the sample testcases, where I actually tried this algorithm and started to confuse myself, causing myself to reject this. This was another unfortunate circumstance of me confusing myself during contest resulting in not solving. (First was in NOI this year, confusing myself with very unorganized inequalities) I guess I should be more careful next time (or even just code it, it's like 3 line modification from my MEX sol).

When I first saw this, I actually thought the statement was funny.

I find it even funnier that we can apply this to the overall SEATST scoreboard.

This problem is a 2-part problem — first is to count the number that must be together, and the second is to count the number that can be together. (Where together means from the same country).

We will first do the first part.

Observation 1: If $$$A$$$ must be with $$$B$$$ and $$$B$$$ must be with $$$C$$$, then $$$C$$$ must be with $$$A$$$. Thus, it is only required for us to consider those of ranking $$$k-1$$$ if the ranking you are currently processing is $$$k$$$.

Then, we are essentially trying to create a matching between those with ranking $$$k-1$$$ and ranking $$$k$$$. We can first store all the possible indices that could be unmatched. Hence, if they have the same cardinality then the matching must involve all elements. Hence, we can conveniently kill off these elements with ranking $$$k-1$$$. Otherwise, there exists a possible construction involving any of the elements, so if the size is larger than 1, nothing is forced, but if size is 1, then they must be together. We can use a UFDS/DSU to store the matchings.

This gives $$$O(N)$$$ or $$$O(N\alpha (N))$$$ or $$$O(N\log N)$$$.

This idea can be brought into part 2 too, but there are more details you need to care about. Now, we should instead draw a directed graph where each node with ranking $$$k$$$ will point to the set of nodes of ranking $$$k-1$$$ that it can match with, using a similar idea to the first part. Then, the set of nodes that a certain node can be together will be the set of nodes connected to it. Thus, by running BFS on this, and processing the students in order, we can get a $$$O(N^2)$$$ solution. This was what I managed to get in contest. (And stitching the subtask where there is no one of rank 2, it is the exact same idea).

Now, this can be sped up by considering that the nodes a student can be connected to and the nodes another student with the same ranking are connected to are very close together. If you store the number of nodes that you can visit but not the previous student with the same ranking, then the final result can be easily computed. By maintaining both values, this can be cut to $$$O(N)$$$.

Final complexity: $$$O(N)$$$.

No code, I have not implemented this solution.

I had managed to tunnel-vision how simply you can just store the difference instead. I was hard thinking about how to have a difference function that can be adjusted due to the UFDS. So I guess, this is me getting too sucked into the UFDS rabbit hole. Oopsies.

I am still very unhappy that I didn't manage to AC this problem. Maybe I should go back and code binary search.

Observation 1: The worst assignment means that the furthest person gets the highest $$$C[i]$$$, and that the second furthest gets the second largest $$$C[i]$$$, etc. This can be easily seen by exchange argument.

Essentially, the easiest way to play around with this problem is to see how the answers change at different indices. If you were to sketch a graph of positions against the cost, you realize that it turns out to be convex piecewise function.

You can perform ternary search on this function for a $$$O(N \log 2e9)$$$ solution. There is a way to AC from this point by calculating worst(p) in $$$O(C\log 2e9\log N)$$$. However, I will discuss the solution I found instead.

Rather than assigning some cost to the cars one by one, we consider sweeping by $$$C[i]$$$ instead. Suppose that there are $$$K[i]$$$ such $$$C[i]$$$ where $$$C[i] \geq i$$$, then we can make it such that $$$K[1]$$$ cars have cost 1, then make $$$K[2]$$$ of these $$$K[1]$$$ cars have cost 2, and so on. This can be motivated by the strange $$$C[i] \leq 100$$$ condition. How is this useful?

Observation 2: Instead of incrementing $$$K[i]$$$ points that is a subset of $$$K[i-1]$$$, it suffices to consider incrementing $$$K[i]$$$ points.

I couldn't prove this in contest, but was a reasonable guess. It would be helpful if someone in the comments can prove this.

Now, this whole question simplifies to solving $$$C[i]\leq 1$$$ 100 times.

Observation 3: You can start with initial position to be $$$-\infty$$$. Then, as you slide to the right, the answer changes by the number of 1s to the right, subtracting the number of 1s to the left.

Observation 4 (Reallocating the locations of the 1s): Suppose that there are $$$x$$$ elements having $$$C[i]=1$$$ as prefix, and $$$y$$$ elements having $$$C[i]=1$$$ as the suffix. ($$$x+y=K[1]$$$), then the next location where this allocation will change is then the $$$x+1$$$th element is further to the point than the $$$y$$$th last element. Hence, there are at most $$$N$$$ such "Changing points".

It is now obvious that the best thing to try is to apply slope trick on this. It suffices to find the first point with slope $$$\geq 0$$$. And, the slope changing points is the average of the 2 points considered in observation 4. Note that the slope will change by 2.

However, this would also imply that you would need to store "slope changing points" at non-integer coordinates. One way to get around this is that if $$$x$$$ is the slope changing point and $$$x\not\in\mathbb{Z}$$$, then you can set the slopes to be $$$\lfloor x\rfloor$$$ and $$$\lceil x \rceil$$$, as the fractional part of $$$x$$$ is 0.5.

This would give a $$$O(N \max(C[i]) \log(N\max C[i]))$$$ solution, and 64 points. This was what I managed to get in contest.

int counts[101]; for (int i = 0; i < 101; i++) counts[i] = 0;
for (int i = 0 ;i  < N; i++) counts[C[i]]++;
for (int i = 99; i >= 0; i--) counts[i] += counts[i+1];
//store the slopes time
vector<long long> slopes;
//initially its all 0.
long long initialslope = 0;
for (int i = 1; i <= 100; i++) {
	initialslope -= counts[i];
	for (int j = 1; j <= counts[i]; j++) {
		//you have j on the left, counts[i]-j on the right
		int n = X[j-1]+X[N-(counts[i]+1-j)];
		if (n%2==0) {
			slopes.push_back(n/2);
			slopes.push_back(n/2);
		}
		else {
			if (n>0) {
				slopes.push_back(n/2);
				slopes.push_back(n/2+1);
			}
			else {
				slopes.push_back(n/2);
				slopes.push_back(n/2-1);
			}
		}
	}
}
sort(slopes.begin(), slopes.end());
for (auto i:slopes) {
	initialslope++;
	if (initialslope == 0) return i;
}
return -100;

So now, we want to essentially remove having to store all of the slope changing points. Thus, it may be a good idea to binary search for the correct one, each time counting the number of slope changing points before it. However, realize that for each layer, you can again count the number of slope changing points before it through another binary search. Beware of negative numbers, and odd numbers. It may be useful to stress test this with the previous solution with just storing the slope changing points.

Final time complexity: $$$O(N+\max(C[i])\log 2e9 \log N)$$$, with essentially negligible constant.

I am extremely unhappy that I did not get the AC on this one. I had coded the binary search for 1.5 hours, and I just couldn't get one detail right (which was when there are indeed a lot of equal car locations, and the positions are odd). :(

Personally, there should be a subtask where all car locations are even to make people getting this detail wrong still attain some points.

I was especially excited when I found the slope trick idea — I knew that I would get something very close to AC very soon. Little did I know binary search would screw me over. Very disappointing that I did not get it. I don't know why, lately I keep getting screwed over by binary search, having been screwed over by JOISC teleporter2 just a few weeks prior.