Here is the link to the problem: https://ioi2019.az/source/Tasks/Day1/Shoes/NGA.pdf
Here is a brief explanation about the problem statement:
You are given an integer n in the range 1≤n≤1e5 which will be representing the amount of positive integers inside of the array, as-well as the amount of negative integers in an array(so the total size of the array will be 2n).
The problem wants you to find the minimum number of swaps needed in the array such that the negative value of a number and the absolute value of that negative number are adjacent to each other(such that -x is to the right of x)
Example:
n = 2;
the array inputed = {2, 1, -1, -2}
The minimum number of operations will be four:
2,1,-1,-2: 0 swaps
2,-1,1,-2: 1 swap(swapping 1 and -1)
2,-1,-2,1: 2 swaps (swapping 1 and -2)
2,-2,-1,1: 3 swaps (swapping -1 and -2)
-2,2,-1,1: 4 swaps (swapping 2 and -2)
The final answer will be four.
Another example:
the array inputed = {-2, 2, 2, -2, -2, 2}
The minimum swaps is one. Because we can just swap elements at index 2 and 3.
Final array: {-2,2,-2,2,-2,2}
When doing this question I got wrong answer and I decided to look at someones source code on git hub.
Here is the source code:
#include "shoes.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 200005;
struct bit{
int tree[MAXN];
void add(int x, int v){
for(int i=x; i<MAXN; i+=i&-i) tree[i] += v;
}
int query(int x){
int ret = 0;
for(int i=x; i; i-=i&-i) ret += tree[i];
return ret;
}
}bit;
lint count_swaps(vector<int> s) {
int n = sz(s) / 2;
lint ret = 0;
vector<pi> v;
vector<pi> ord[MAXN];
for(int i=0; i<sz(s); i++){
ord[abs(s[i])].emplace_back(s[i], i);
}
for(int i=1; i<=n; i++){
sort(ord[i].begin(), ord[i].end());
for(int j=0; j<sz(ord[i])/2; j++){
int l = ord[i][j].second;
int r = ord[i][j + sz(ord[i])/2].second; //confusion starts here all the way to the buttom
if(l > r){
swap(l, r);
ret++;
}
v.emplace_back(l + 1, r + 1);
}
}
for(int i=1; i<=2*n; i++) bit.add(i, 1);
sort(v.begin(), v.end());
for(auto &i : v){
ret += bit.query(i.second - 1) - bit.query(i.first);
bit.add(i.first, -1);
bit.add(i.second, -1);
}
return ret;
}
However, I dont think I understand the this code too well.
I understand what the functions add and query in BIT do I'm just confused on where I commented on the code all the way to the bottom. I dont understand what it does and what the purpose of that is.
Can someone walk through what this code is doing? Or give any suggestions to how I should properly and efficiently approach this problem(even maybe your solutions?). Thank you.
int r = ord[i][j + sz(ord[i])/2].second;
We've sorted the tuples of one shoe size in a vector of <size, idx>, which means all the negatives of this size take up the first half of ord[i], and all the positives are in the second half.
if (l > r){
swap(l, r);
ret++;
}
After our sort on size, the indexes of each corresponding pair may not be ordered with the negative before the positive. Each one of those costs a swap.
v.emplace_back(l + 1, r + 1);
insert into v our interval for the corresponding pair of shoes of size i.
for(int i=1; i<=2*n; i++) bit.add(i, 1);
sort(v.begin(), v.end());
Add the value of 1 in our segment-sum tree for each index location of a shoe. Sort the shoe intervals.
for(auto &i : v){
ret += bit.query(i.second - 1) - bit.query(i.first);
For each pair of shoes in v, the number of swaps needed is the number of shoes left in between them, expressed in the sum of the segment.
bit.add(i.first, -1);
bit.add(i.second, -1);
Remove the pair of shoes from the tree so a new segment sum won't include them. We can do this since the shoe intervals are processed left to right, which means no "inner" pair of shoes gets processed before an outer pair.