Help Needed with this problem!

Will anyone help me with this problem I am getting TLE in this problem.

Problem

Given an integer array of length n and q queries.

Each query has a form a b, where a and b are numbers of elements in the array to be swapped. Your task is to tell after each query if the array is sorted by non-decreasing order.

Input format

The first line of the input contains two integers n and q (2≤n≤2⋅10^5, 1≤q≤10^5) — length of the given array and number of the queries respectively.

The second line contains n positive integers, does not exceed 10^9 — initial values of the array elements.

Then q lines follow, each containing two distinct integers a and b (1≤a,b≤n) — indices of elements to be swapped at the current query.

Output format

For each query, print in the new line “Sorted!” if the array is sorted in non-decreasing order after that query, or “Unsorted!” otherwise.

Sample 1

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

Output

Unsorted!
Sorted!
Unsorted!
Sorted!

Sample 2

Input
2 3
2 10
1 2
1 2
1 2

Output

Unsorted!
Sorted!
Unsorted!

My Solution:

#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b) for (int i = (a); i < (b); i++)

bool arraySortedOrNot(int a[], int n)
{
     
    if (n == 1 || n == 0)
    {
        return true;
    }
    return a[n - 1] >= a[n - 2] &&
     arraySortedOrNot(a, n - 1);
}


void solve();

int main(){ 
cin.tie(0);
cout.tie(0);
solve();
return 0;
}

// Write CODE here without Test case---#
void solve(){
  int n,q;
  scanf("%d %d",&n,&q);
  int arr[n];
  FORN(i,0,n)scanf("%d",&arr[i]);
  FORN(i,0,q){
    int a,b;
    scanf("%d %d",&a,&b);
    swap(arr[a-1],arr[b-1]);
    if(arraySortedOrNot(arr,n)) {printf("Sorted!\n");}
    else {printf("Unsorted!\n");}
  }
}

CODE with no TLE: :slight_smile: :slight_smile:

#include <bits/stdc++.h>
using namespace std;
#define FORN(i, a, b) for (int i = (a); i < (b); i++)


void solve();

int main(){ 
cin.tie(0);
cout.tie(0);
solve();
return 0;
}

// Write CODE here without Test case---#
void solve(){
  int n,q;
  scanf("%d %d",&n,&q);
  vector <int> arr;
  vector <int> brr;
  int temp;
  FORN(i,0,n){
    scanf("%d",&temp);
    brr.push_back(temp);
    arr.push_back(temp);
    }
  sort(brr.begin(), brr.end());
  reverse(brr.begin(), brr.end());
  reverse(arr.begin(), arr.end());
  FORN(i,0,q){
    int a,b;
    scanf("%d %d",&a,&b);
    swap(arr[n-a],arr[n-b]);
      if(arr==brr) {
      printf("Sorted!\n");
        }
      else {
      printf("Unsorted!\n");
        }
    }
  }

Do you have link to the problem ? And can you format your code using ` 3 times

2 Likes

Ur code shouldn’t have worked actually as the time complexity is

O(N*Q)

which must have timed out ig it passed because of weak test case.

Thanks! but the problem was on Yandex Contest under a course so other would not be able to access it.

The correct approach to this problem should be using the concpet of INVERSIONS.

Pre-Processing Part:

Pre-Processing:

Since the elements as such don’t have significance as only the order matters we can replace the elements with 1,2,3…n this can be done in O(NLogN) and we can also find the number of inversion in O(NLogN).

Processing query update Part:

Query:

For every query of the form a b the number of inversions can either decrease or increase based on the corresponding value of arr[a] and arr[b]. If the arr[a] < arr[b] then on swapping the number of inversions would increase else it would decrease. The number by which it increases or decreases remains constant which is equal to abs(b-a-1)+abs(arr[a]-arr[b]). So, if the number of inversions is greater than 0 its Unsorted else it is Sorted.
This query update overall would take only O(1) time.

Therefore, the overall time complexity becomes O(NLogN+Q).

1 Like

Sorry the formulae should be:

abs(b-a) + abs(arr[b]-arr[a]) - 1

Thanks! Will you Pls share the code for your suggested approach? :slight_smile:

can you plz code it ?
and any blog or post for inversion technique

I have an easier solution , make another array and call it brr and store the array arr in sorted form in it , then create a set S and store the indices in it for which arr_i != brr_i . Then start processing the queries for a and b , Now if a is in S erase it , if b is in S erase it , Now swap arr[a] and arr[b] , now if arr[a]!=brr[a] insert a in set , same goes for b . Whenever S is empty the list is sorted . We need to check of only a and b in each query because those are the only things which are changing . Time Complexity O (NLogN+QLogN)

Can you tell me why u sorted brr array in descending order and arr just reversed
and why u did n-a and n-b

1.Why u sorted array brr in descending order and just reversed array arr?
→ I have reversed Both the array arr and brr as I had observed the most of the swapping in the test cases of this problem were done on the larger indices and I have sorted the array brr to compare it with array arr after every query to check if arr is sorted or not.

2. Why u did n-a and n-b?
→ As I had reversed the array arr so (n-a) and (n-b) are the indices of elements that need to be swap according to the query.

  • I know it’s not a much-optimized approach but worked for me. I want to know more different approaches to this problem that’s why I created this discussion post.