UWCOI21B - Array Swaps - Editorial

PROBLEM LINK:

Contest
Practice

Author: Leo Lee
Tester: Daanish Mahajan
Editorialist: Leo Lee

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

You are given an array A of size N and an array B of size M. While B is not empty, you perform the following operations:

  • Remove and store the leftmost element off of B (let’s call this element X).
  • Place X at the start of A.
  • Keep swapping X and the element to the right of it repeatedly until X is at the rightmost position of A or X is greater or equal to the element to the right of it.

Before performing the operations, you can rearrange both A and B in any order once. Determine the minimum possible amount of operations.

Subtask 1 [15 points]: A[i] = B[i] = 1 for all i
Subtask 2 [30 points]: N, M \le 10^3
Subtask 3 [55 points]: N, M \le 2*10^5

QUICK EXPLANATION:

The answer is equal to the number of elements in B that are smaller than the smallest element in A, times N.

EXPLANATION:

Subtask 1:

If all A[i], B[i] are equal, there won’t be any swaps since X will always be equal to the element to the right of it. Note that rearranging A or B won’t do anything. Since there are no swaps, the answer is always 0.

Subtask 2:

We can observe that the most optimal arrangement for A and B is to sort both in ascending order.

For A, the most important thing is for the smallest element in A to be at the front. If it isn’t, there is a possibility of an element to exist that are between the smallest element and the first element, causing extra swaps. Also note that, if a swap is required with the smallest element in A, that means a swap is required for every element in A as it will all be greater than or equal to the smallest element.

For B, notice that if it is in ascending order, any element X that is put into A won’t end up at a position farther than the one previously, which is optimal. On the contrary, assume there are two adjacent elements which are not in sorted order. This means that there is a possibility of the two elements meeting after being merged into A. If they meet, it will cause an extra swap, which is undesired.

Therefore, we can sort both in ascending order and simulate the process. This has a time complexity of O(NM), which is enough to pass this subtask.

Subtask 3:

From the previous subtask, we can observe that, when elements are sorted in optimal order, the only elements in B being swapped are the ones that are smaller than the smallest element of A. Also, note that since no element in B will be swapped with any other element in B and will be swapped with every element in A, it will cost N swaps each.

This means that we can calculate the total number of swaps easily by getting the product of N and the number of elements in B that are smaller than the smallest element in A. This gives us a time complexity of O(N + M).

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;

#define int long long

int n, m, a, mini = INT_MAX, ans;

signed main() {
    cin >> n >> m;
    for (int i=0; i<n; i++) {
        cin >> a;
        mini = min(mini, a);
    }
    for (int i=0; i<m; i++) {
        cin >> a;
        if (a < mini) ans++;
    }
    cout << ans*n << endl;
}
Tester's Solution
import java.util.*;
import java.io.*;
public class Main{
    static PrintWriter out;
    static InputReader in;
    public static void main(String args[]){
        out = new PrintWriter(System.out);
        in = new InputReader();
        new Main();
        out.flush(); out.close();
    }   
    Main(){
        solve();
    }
    void solve(){
    	int n = in.nextInt(), m = in.nextInt();
    	int a[] = new int[n], b[] = new int[m];
    	for(int i = 0; i < n; i++)a[i] = in.nextInt();
		for(int i = 0; i < m; i++)b[i] = in.nextInt();
		Arrays.sort(a); //Arrays.sort(b);
		long ans = 0;
		for(int i = 0; i < m; i++){
			if(b[i] < a[0])
				ans += n;
		}
		out.println(ans);
    }
    public static class InputReader{
        BufferedReader br;
        StringTokenizer st;
        InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        public int nextInt(){
            return Integer.parseInt(next());
        }
        public long nextLong(){
            return Long.parseLong(next());
        }
        public double nextDouble(){
            return Double.parseDouble(next());
        }
        public String next(){
            while(st == null || !st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch(IOException e){}
            }
            return st.nextToken();
        }
    }
}
2 Likes

The problem statement was really hard for me to understand during the contest.

11 Likes

Thanks for your valuable explaination :slight_smile:

it says swap until its at rightmost of A or if ‘X’ is greater or equal to right one.
so ‘1’ will be swapped len(A) times since 1 is always equal to rightmost elements isn’t it?

1 Like

Problem statement was really hard, I think the problem setter should care about such things.

2 Likes

If someone has a video solution for this problem then please share a link here, finding a little bit difficult to understand Editorial.

1 Like

Hi everyone, sorry for the confusion in the problem statement. I think a lot of people interpreted ‘until’ as ‘while’ in the statement, but what we intended to say was that you stop swapping the elements when X is greater or equal to the element to the right of it.

It would’ve been much clearer if it was written with while, like this:

Keep swapping X and the element to the right of it repeatedly while X isn’t the last element of A and X is strictly smaller than the element to the right of it.

This issue hadn’t come up during testing and in the onsite contest, but it definitely could’ve been written better. I am sorry for this.

1 Like

Can anyone please explain how both below statements are saying same thing?

Keep swapping X and the element to the right of it repeatedly until X is at the rightmost position of A or X is greater or equal to the element to the right of it.

Keep swapping X and the element to the right of it repeatedly while X isn’t the last element of A and X is strictly smaller than the element to the right of it.

If you do something until a condition is met, that means you stop when it is true.
If you do something while a condition is met, that means you stop when it is false.

The second statement states that we are swapping while X isn’t the last element of A and X is strictly smaller than the element to the right of it. If this condition is not met (i.e it is false), then the swapping stops.

If this condition is false, then that means X is the last element of A or X is not strictly smaller than the element to the right of it. If X is not strictly smaller, X must be greater or equal. Therefore the two statements are equal.

1 Like

I don’t see any issues with problem statement. I really liked the problem and the contest was good.

yes i suffered a very huge loss yesterday just because of this problem statement … for 2 hours i was not even to understand the question…

yes, took a huge chunk of time just to understand it

Well, I didn’t participate in the contest last night but now I am trying to solve the questions. The problem description is really tough to understand though the logic is so simple. Nice question though!!.

Someone pls explain the sample input given in the question!
since 1 is smaller than all elements in the array A number of min swaps will definitely be equal to the length of A(atleast).

That is right!!! I was confused that we have to place the elements of array B in A after counting but now i came to know that we have to just count the swaps. Confusing statement and the example as well.