Codeforces Round #743 (Div.2) B — Swaps

Revision en8, by putong, 2021-09-19 15:21:43

I think this problem is not very hard and it's interesting.

Description:

You are given $2$ arrays $a$ and $b$ and the length of them is $n$.

• $1$, $3$, $5$, ......, $2 * n - 1$ is in $a$.

• $2$, $4$, $6$, ......, $2 * n$ is in $b$.

$\mathrm{Algorithm}\ 1:$

we use the array $mp_i$ is $i$ the distance to the $a_1$ or $b_1$.

the code is:

for (int i = 1;i <= n; ++ i) cin >> a[i], mp[a[i]] = i - 1;
for (int j = 1;j <= n; ++ j) cin >> b[i], mp[b[i]] = i - 1;


We can enumerate the $i$ and the $j$, and the answer is $mp_{a_i}\ +\ mp_{b_j}$.

the code:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <deque>
#include <ctime>
#include <sstream>
#include <list>
#include <bitset>
#include <climits>
#include <functional>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int int
#define itn int
using namespace std;
using namespace __gnu_pbds;
typedef long long ll ;
typedef pair <int, int> PII;
#define x first
#define y second
#define pq priority_queue
const double pi = acos (-1);
namespace fastIO {
template <class T>
inline void read (T &x) {
x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
if (fu) x = -x;
}
int x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
return fu ? -x : x;
}
template <class T, class... Args>
inline void read (T& t, Args&... args) {
}
char num[40];
template <class T>
inline void write (T x) {
if (x == 0) {
putchar ('0');
return ;
}
T tmp = x > 0 ? x : -x;
if (x < 0) putchar ('-');
register int ct = 0;
while (tmp) {
num[ct ++] = tmp % 10 + '0';
tmp /= 10;
}
while (ct) {
putchar (num[-- ct]);
}
}
template <class T>
inline void write (T x, char ch) {
write (x);
putchar (ch);
}
}
using namespace fastIO;
int a[100005], b[100005];
int mp[200010];
int mini[200010];
int c[100005];
signed main () {
int t;
cin >> t;
while (t --) {
memset (mp, 0, sizeof mp);
memset (mini, 0, sizeof mini);
int n;
int ans = 0x7f7f7f7f;
for (int i = 1;i <= n; ++ i) {
mp[a[i]] = i - 1;
}
for (int i = 1;i <= n; ++ i) {
mp[b[i]] = i - 1;
}
if (a[1] < b[1]) {
cout << "0" << endl;
}
else {
for (int i = 1;i <= 2 * n; i += 2) {
for (int j = 1;j <= 2 * n; j += 2) {
if (i < j) ans = min (ans, mp[i] + mp[j]);
}
}
cout << ans << endl;
}
}
return 0;
}


time: $O(tn^2)$.

$\mathrm{Algorithm}\ 2:$

we can use $mini_i\ =\ \mathrm{min}_{i=\frac{i}{2}}^{n}mp_{2i}$.

and the time is $O(tn)$.

code :

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <algorithm>
#include <utility>
#include <deque>
#include <ctime>
#include <sstream>
#include <list>
#include <bitset>
#include <climits>
#include <functional>
#include <complex>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define int int
#define itn int
using namespace std;
using namespace __gnu_pbds;
typedef long long ll ;
typedef pair <int, int> PII;
#define x first
#define y second
#define pq priority_queue
const double pi = acos (-1);
namespace fastIO {
template <class T>
inline void read (T &x) {
x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
if (fu) x = -x;
}
int x = 0;
bool fu = 0;
char ch = 0;
while (ch > '9' || ch < '0') {
ch = getchar ();
if (ch == '-') fu = 1;
}
while (ch <= '9' && ch >= '0') x = (x * 10 - 48 + ch), ch = getchar ();
return fu ? -x : x;
}
template <class T, class... Args>
inline void read (T& t, Args&... args) {
}
char num[40];
template <class T>
inline void write (T x) {
if (x == 0) {
putchar ('0');
return ;
}
T tmp = x > 0 ? x : -x;
if (x < 0) putchar ('-');
register int ct = 0;
while (tmp) {
num[ct ++] = tmp % 10 + '0';
tmp /= 10;
}
while (ct) {
putchar (num[-- ct]);
}
}
template <class T>
inline void write (T x, char ch) {
write (x);
putchar (ch);
}
}
using namespace fastIO;
int a[100005], b[100005];
int mp[200010];
int mini[200010];
int c[100005];
signed main () {
int t;
cin >> t;
while (t --) {
memset (mp, 0, sizeof mp);
memset (mini, 0, sizeof mini);
int n;
int ans = 0x7f7f7f7f;
for (int i = 1;i <= n; ++ i) {
mp[a[i]] = i - 1;
}
for (int i = 1;i <= n; ++ i) {
mp[b[i]] = i - 1;
}
mini[2 * n] = mp[2 * n];
for (int i = 2 * n - 2;i >= 2; i -= 2) {
mini[i] = min (mini[i + 2], mp[i]);
}
if (a[1] < b[1]) {
cout << "0" << endl;
}
else {
for (int i = 1;i <= 2 * n; i += 2) {
ans = min (ans, mp[i] + mini[i + 1]);
}
cout << ans << endl;
}
}
return 0;
}


#### History

Revisions

Rev. Lang. By When Δ Comment
en8 putong 2021-09-19 15:21:43 2785
en7 putong 2021-09-19 15:16:28 2852
en6 putong 2021-09-19 15:11:49 162
en5 putong 2021-09-19 15:07:30 14
en4 putong 2021-09-19 15:06:15 22
en3 putong 2021-09-19 15:05:46 22
en2 putong 2021-09-19 15:04:51 79
en1 putong 2021-09-19 15:04:16 358 Initial revision (published)