A. Array Balancing | Educational Codeforces Round 126

A. Array Balancing
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two arrays of length na1,a2,,an and b1,b2,,bn.

You can perform the following operation any number of times:

  1. Choose integer index i (1in);
  2. Swap ai and bi.

What is the minimum possible sum |a1a2|+|a2a3|++|an1an| + |b1b2|+|b2b3|++|bn1bn| (in other words, i=1n1(|aiai+1|+|bibi+1|)) you can achieve after performing several (possibly, zero) operations?

Input

The first line contains a single integer t (1t4000) — the number of test cases. Then, t test cases follow.

The first line of each test case contains the single integer n (2n25) — the length of arrays a and b.

The second line of each test case contains n integers a1,a2,,an (1ai109) — the array a.

The third line of each test case contains n integers b1,b2,,bn (1bi109) — the array b.

Output

For each test case, print one integer — the minimum possible sum i=1n1(|aiai+1|+|bibi+1|).

Example
input
Copy
3
4
3 3 10 10
10 10 3 3
5
1 2 3 4 5
6 7 8 9 10
6
72 101 108 108 111 44
10 87 111 114 108 100
output
Copy
0
8
218
Note

In the first test case, we can, for example, swap a3 with b3 and a4 with b4. We'll get arrays a=[3,3,3,3] and b=[10,10,10,10] with sum 3|33|+3|1010|=0.

In the second test case, arrays already have minimum sum (described above) equal to |12|++|45|+|67|++|910| =4+4=8.

In the third test case, we can, for example, swap a5 and 

b5. 


The solution to the above question is 

#include <bits/stdc++.h>

using namespace std;

#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl

inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}

template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

const int N = 200005;

void solve() {

int n;
cin>>n;

vi a(n,0),b(n,0);
for (int i = 0; i < n; i++)
{
    cin>>a[i];
}

for (int i = 0; i < n; i++)
{
    cin>>b[i];
}
int ans=0;
int noswap=0;

for (int i = 0; i < n-1; i++)
{   

    int curr=abs(a[i+1]-a[i])+abs(b[i+1]-b[i]);
    int curr2=abs(a[i+1]-b[i])+abs(a[i]-b[i+1]);
    if(curr2>curr){
        swap(a[i],b[i]);
    }
    ans+=min(curr,curr2);
}
cout<<ans<<endl;





}

int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);


  clock_t z = clock();

  int t = 1;
  cin >> t;
  while (t--) solve();



  return 0;
}

Thank you for reading this.

Post a Comment

0 Comments