D. Plus Minus Permutation | Codeforces Solution | Codeforces Round 895 (Div. 3)
You are given 3 integers β π , π₯ , π¦ . Let's call the score of a permutationβ π1,β¦,ππ the following value: (π1β π₯+π2β π₯+β¦+πβππ₯ββ π₯)β(π1β π¦+π2β π¦+β¦+πβππ¦ββ π¦) In other words, the score of a permutation is the sum of ππ for all indices π divisible by π₯ , minus the sum of ππ for all indices π divisible by π¦ . You need to find the maximum possible score among all permutations of length π . For example, if π=7 , π₯=2 , π¦=3 , the maximum score is achieved by the permutation [2,6β―β―,1β―β―,7β―β―,5,4β―β―β―β―,3] and is equal to (6+7+4)β(1+4)=17β5=12 .
memory limit per test: 256 megabytes
You are given 3 integers β n, x, y. Let's call the score of a permutationβ p1, β¦, pn the following value:
(p1β x + p2β x + β¦ + pβn/xββ x) β (p1β y + p2β y + β¦ + pβn/yββ y)
In other words, the score of a permutation is the sum of pi for all indices i divisible by x, minus the sum of pi for all indices i divisible by y.
You need to find the maximum possible score among all permutations of length n.
For example, if n = 7, x = 2, y = 3, the maximum score is achieved by the permutation [2, 6, 1, 7, 5, 4, 3] and is equal to (6 + 7 + 4) β (1 + 4) = 17 β 5 = 12.
β A permutation of length n is an array consisting of n distinct integers from 1 to n in any order. For example, [2, 3, 1, 5, 4] is a permutation, but [1, 2, 2] is not a permutation (the number 2 appears twice in the array) and [1, 3, 4] is also not a permutation (n = 3, but the array contains 4).
The first line of input contains an integer t (1 β€ t β€ 104) β the number of test cases.
Then follows the description of each test case.
The only line of each test case description contains 3 integers n, x, y (1 β€ n β€ 109, 1 β€ x, y β€ n).
For each test case, output a single integer β the maximum score among all permutations of length n.
8 7 2 3 12 6 3 9 1 9 2 2 2 100 20 50 24 4 6 1000000000 5575 25450 4 4 1
12 -3 44 0 393 87 179179179436104 -6
The first test case is explained in the problem statement above.
In the second test case, one of the optimal permutations will be [12, 11, 2, 4, 8, 9, 10, 6, 1, 5, 3, 7]. The score of this permutation is (9 + 7) β (2 + 9 + 1 + 7) = β3. It can be shown that a score greater than β3 can not be achieved. Note that the answer to the problem can be negative.
In the third test case, the score of the permutation will be (p1 + p2 + β¦ + p9) β p9. One of the optimal permutations for this case is [9, 8, 7, 6, 5, 4, 3, 2, 1], and its score is 44. It can be shown that a score greater than 44 can not be achieved.
In the fourth test case, x = y, so the score of any permutation will be 0.
Solution
Explanation:
The solution maximizes the score by calculating the number of positions divisible by x (to add large numbers) and y (to subtract small numbers), accounting for overlaps using their LCM (via GCD). It uses a helper function to compute the sum of integers in ranges, assigning the largest n/x numbers to x-divisible positions, excluding overlaps, and the smallest remaining n/y - n/LCM numbers to y-divisible positions, then outputs the difference.
int helper(int st, int end)
{
int e = (end * (end + 1)) / 2;
--st;
int s = max(0LL, (st * (st + 1)) / 2);
return e - s;
}
void solve()
{
int n, x, y;
cin >> n >> x >> y;
int gcd = __gcd(x, y);
gcd = (x * y) / gcd;
int common = n / gcd;
int cpy = common;
int tot = n / x;
int mn = n / y;
int res = 0;
int st = n;
st -= tot;
res += helper(n - tot + 1, n);
res -= helper(st + 1, st + common);
mn -= cpy;
st = 1;
mn = abs(mn);
res -= helper(1, mn);
cout << res << endl;
}
#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
#define scanit(a, n) \
for (ll indexaa = 0; indexaa < n; indexaa++) \
cin >> a[indexaa];
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;
int helper(int st, int end)
{
int e = (end * (end + 1)) / 2;
--st;
int s = max(0LL, (st * (st + 1)) / 2);
return e - s;
}
void solve()
{
int n, x, y;
cin >> n >> x >> y;
int gcd = __gcd(x, y);
gcd = (x * y) / gcd;
int common = n / gcd;
int cpy = common;
int tot = n / x;
int mn = n / y;
int res = 0;
int st = n;
st -= tot;
res += helper(n - tot + 1, n);
res -= helper(st + 1, st + common);
mn -= cpy;
st = 1;
mn = abs(mn);
res -= helper(1, mn);
cout << res << 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;
}
Raunit Verma
Technical Writer at CodingKaro
