Idea: BledDest, preparation: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
t = int(input())
for i in range(t):
x, y = map(int, input().split())
xc = -1
yc = -1
for j in range(0, 51):
for k in range(0, 51):
if 2 * (j + k) == x + y and 2 * (abs(x - j) + abs(y - k)) == x + y:
xc, yc = j, k
print(xc, yc)
```

Idea: MikeMirzayanov, preparation: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
t = int(input())
for i in range(t):
n, a, b = map(int, input().split())
p = [a]
for j in range(n, 0, -1):
if j != a and j != b:
p.append(j)
p.append(b)
if(len(p) == n and min(p[0:n//2]) == a and max(p[n//2:n]) == b):
print(*p)
else:
print(-1)
```

Idea: vovuh, preparation: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
long long get(int x) {
return x * 1ll * (x + 1) / 2;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
int k;
long long x;
cin >> k >> x;
long long l = 1, r = 2 * k - 1;
long long res = 2 * k - 1;
bool over = false;
while (l <= r) {
int mid = (l + r) >> 1;
if (mid >= k) {
over = (get(k) + get(k - 1) - get(2 * k - 1 - mid) >= x);
} else {
over = (get(mid) >= x);
}
if (over) {
res = mid;
r = mid - 1;
} else {
l = mid + 1;
}
}
cout << res << endl;
}
return 0;
}
```

Idea: vovuh, preparation: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
bool get(long long a, long long b, long long x) {
if (a == x || b == x) return true;
if (a < b) swap(a, b);
if (b > a - b) b = a - b;
if (x > max(a, b) || a == 0 || b == 0) return false;
long long cnt = max(1ll, (a - max(x, b)) / (2 * b));
return get(a - b * cnt, b, x);
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
int t;
cin >> t;
while (t--) {
long long a, b, x;
cin >> a >> b >> x;
if (get(a, b, x)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
return 0;
}
```

Idea: BledDest, preparation: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 200043;
const int K = 20;
vector<int> idx[N];
int m[N], k[N];
bool frac_greater(pair<int, int> a, pair<int, int> b)
{
return a.first * b.second > a.second * b.first;
}
int main()
{
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++)
{
scanf("%d %d", &m[i], &k[i]);
idx[m[i]].push_back(i);
}
vector<int> cert;
pair<int, int> ans = {0, 1};
for(int i = 1; i <= K; i++)
{
vector<int> score(N);
for(int j = 0; j < n; j++)
score[m[j]] += min(i, k[j]);
vector<pair<int, int>> aux;
for(int j = 0; j < N; j++)
aux.push_back(make_pair(score[j], j));
sort(aux.rbegin(), aux.rend());
pair<int, int> cur_ans = {0, i};
vector<int> cur_cert;
for(int j = 0; j < i; j++)
{
cur_ans.first += aux[j].first;
cur_cert.push_back(aux[j].second);
}
if(frac_greater(cur_ans, ans))
{
ans = cur_ans;
cert = cur_cert;
}
}
cout << cert.size() << endl;
shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));
for(auto x : cert) cout << x << " ";
cout << endl;
}
```

Idea: BledDest, preparation: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
int n, m;
#define x first
#define y second
typedef pair<int, int> comb;
comb norm(const comb& a)
{
return make_pair(min(a.x, n), min(a.y, m));
}
bool good(const comb& a)
{
return a.x == n || a.y == m;
}
bool comp(const comb& a, const comb& b)
{
if(a.x != b.x)
return a.x > b.x;
return a.y > b.y;
}
int main()
{
scanf("%d %d", &n, &m);
int v;
scanf("%d", &v);
set<comb> s;
for(int i = 0; i < v; i++)
{
int x, y;
scanf("%d %d", &x, &y);
s.insert(make_pair(x, y));
}
int steps = 0;
vector<comb> cur;
cur.push_back(make_pair(1, 1));
while(true)
{
if(cur[0] == make_pair(n, m))
break;
vector<comb> ncur;
for(auto x : cur)
{
int sum = x.x + x.y;
if(s.count(x))
sum++;
comb z = x;
z.x = sum;
ncur.push_back(norm(z));
z = x;
z.y = sum;
ncur.push_back(norm(z));
}
sort(ncur.begin(), ncur.end(), comp);
int mx = 0;
vector<comb> ncur2;
for(auto x : ncur)
{
if(x.y <= mx) continue;
mx = max(mx, x.y);
ncur2.push_back(x);
}
cur = ncur2;
steps++;
}
printf("%d\n", steps);
}
```

Idea: adedalic, preparation: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
template<class A, class B> ostream& operator <<(ostream& out, const pair<A, B> &p) {
return out << "(" << p.x << " " << p.y << ")";
}
template<class A> ostream& operator <<(ostream& out, const vector<A> &v) {
fore(i, 0, sz(v)) {
if(i) out << " ";
out << v[i];
}
return out;
}
const int INF = int(1e9);
const li INF64 = li(1e18);
const int MOD = int(1e9) + 7;
int norm(int a) {
while (a >= MOD)
a -= MOD;
while (a < 0)
a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
const int MX = int(1e6) + 55;
int n;
li total;
int cnt[MX];
inline bool read() {
if(!(cin >> n))
return false;
total = 0;
fore (i, 0, n) {
int k; cin >> k;
cnt[k]++;
total += k;
}
return true;
}
int fact[MX];
inline void solve() {
fact[0] = 1;
fore (i, 1, MX)
fact[i] = mul(fact[i - 1], i);
int ansSum = 0;
int ansCnt = 1;
for (int lvl = MX - 1; lvl > 1; lvl--) {
ansCnt = mul(ansCnt, mul(fact[cnt[lvl]], fact[cnt[lvl]]));
//each color gives (lvl - 1) * (r_i - l_i)
// or (lvl - 1) * (sum r_i - sum l_i)
// l_i is permutation of [0,..., cnt[lvl]), so sum l_i = (cnt[lvl] - 1) * cnt[lvl] / 2
// r_i is permutation of [total - cnt[lvl],..., total), so sum = cnt[lvl] * (total - cnt[lvl]) + (cnt[lvl] - 1) * cnt[lvl] / 2
ansSum = norm(ansSum + mul(mul(lvl - 1, cnt[lvl]), (total - cnt[lvl]) % MOD));
total -= 2 * cnt[lvl];
cnt[lvl - 2] += cnt[lvl];
}
ansCnt = mul(ansCnt, fact[cnt[1]]);
cout << ansSum << " " << ansCnt << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
```

The root of cf is math.

How drastically does problem F change if the game allows Monocarp to buy armor with a level greater than $$$n$$$ and weapons with a level greater than $$$m$$$? While it reduces the maximum number of hours needed to the ballpark of $$$O(\log(nm)),$$$ it also eliminates the clause that a point $$$(x,y)$$$ is always better than a point $$$(x', y')$$$ if $$$x' \leq x$$$ and $$$y' \leq y,$$$ requiring some degree of strategic planning.

i misread the problem and tried to solve this version for an hour lmao

Here is a slightly different approach for problem G which I think is easier. (Sorry if my explanation is not good.) It would seem that many other people have this approach too.

First, let's ask ourselves, given an array, how can we find the total sum of distances between all pairs of equal elements? For each element, we will need to add to the answer the sum of absolute values between each pair of indexes where it exists. This is a very well known problem, and can be easily understood by looking at an example.

Let's say an element exists at the indices $$$[1, 4, 5, 6, 8]$$$. Then, we will need to add $$$(4-1)+(5-1)+(6-1)+(8-1)+(5-4)+(6-4)+(8-4)+(6-5)+(8-5)+(8-6)$$$ to the answer. Overall, 1 has been subtracted 4 times, 4 has been subtracted twice, 5 does not contribute towards the sum, 6 is added twice, and 8 is added 4 times. So we will add to the sum $$$(-4)*1+(-2)*4+(0)*5+(2)*6+(4)*8$$$. In general, for a sorted array $$$[p_1, p_2, \dots, p_x]$$$, we will add to the answer $$$p_1*(1-x)+p_2*(3-x)+p_3*(5-x)+...+p_x*(x-1)$$$. We can think of this as assigning multiplying each index by a coefficient and finding the total sum of indexes, such that the coefficients assigned to indexes with the same element are a $$$[1-x, 3-x, \dots, x-1]$$$ in ascending order.

We can now move on to maximising the answer. We will generate a coefficient array. For each $$$c_i$$$, we will add the elements $$$[1-c_i, 3-c_i, \dots, c_i-1]$$$ to the coefficient array. Then, we want to obtain a permutation of this coefficient array $$$[p_1, p_2, \dots, p_n]$$$ such that $$$\sum_{i=1}^{n} ip_i$$$ is maximised. By the rearrangement inequality, this sum is maximised when $$$p$$$ is sorted, and it is easy to see that such a permutation is possible.

For more clarity, consider the case where $$$c = [3, 3, 2]$$$. We will generate the coefficient array $$$[-2, 0, 2]+[-2, 0, 2]+[-1, 1]=[-2, -2, -1, 0, 0, 1, 2, 2]$$$. Then the maximum answer will be $$$(-2)*0+(-2)*1+(-1)*2+(0)*3+(0)*4+(1)*5+(2)*6+(2)*7=27$$$, and this is achievable for example by choosing $$$a=[1, 2, 3, 1, 2, 3, 1, 2]$$$.

Now, how do we do this fast? Instead of actually generating the coefficient array, we will simply create a frequency map storing how many times each element exists in the coefficient array. We can create this map quickly using a difference array (or you can visualise this as a sweepline). We will then iterate through this map in ascending order. For each element $$$e$$$ which occurs $$$num$$$ times in the coefficient array, we will assign $$$e$$$ as the coefficient of the $$$num$$$ lowest indexes which we haven't assigned yet, and increment our answer by ($$$e *$$$ sum of chosen indexes). Remember that of the distinct elements in $$$a$$$, exactly $$$num$$$ of these elements will have contributed $$$e$$$ to the coefficient array, so these indexes will correspond to some permutation of these $$$num$$$ elements in $$$a$$$. We will therefore multiply the number of possible arrays by $$$num!$$$, as this is the number of permutation of these $$$num$$$ elements in $$$a$$$.

See https://mirror.codeforces.com/contest/1612/submission/136599117 for implementation details. If an array is used instead of a map, the overall complexity of this algorithm is $$$O(m+max(c_i))$$$.

Elegant !!!

can't understand solution of E since "iterate the number of message".

You can check my commented solution it explains the idea as well as the code. My solution

C can also be solved by calculating root of the quadratic equation x(x+1)/2 — c = 0. Not sure if this solution is more optimal though

Its giving wrong answer for my submission, maybe because I am using the sqrt() function. So without using it is there any other method to calculate square root optimally?

You can check my submission as it also uses sqrt, it passed tests. You can have rounding problems so you have check root +-1.

yes — use

`sqrtl()`

and`ceill()`

instead of`sqrt()`

and`ceil()`

— the first two uses`long double`

which will not lose precision for integers up to`9*10^18`

while the second two uses`double`

which loses precision for integers above`2*10^15`

can pls anyone explian me A problem solution

You can almost brute force all possible points $$$C$$$, since we know that $$$0 \le C_x, C_y \le 100$$$. However, trying all $$$101^2$$$ points won't work. We notice that $$$C_x + C_y = \frac{|x| + |y|}{2},$$$ so if we fix $$$C_x$$$ we can find $$$C_y$$$. That is, brute force all possible points $$$C_x \in [0, 100],$$$ find the corresponding $$$C_y = \frac{|x| + |y|}{2} - C_x$$$ to check if that point is valid.

EDIT: Actually, trying all possible points will work; I overcomplicated

Why wouldn't trying all points work? It takes around 3 * 10^7 operations which is perfectly fine.

For problem E, I did the ternary search and got AC. But I have no idea if it can be proved XD. I just assumed that the expectation of number of messages that Monocarp should pin has a maximum, and then checked the expectation in ternary search. somehow it worked (I failed at test 167. turns out it could be optimum when you just only pin one message, and then I fixed it) my code: 136675859

I'm an idiot XD. now I read the tutorial. Don't reply, ignore me

reply quq

For those who are struggling like me in problem E, why don't we need for t > 20, here is why

For simplicity

assumethatk[i] <= 2, and the sorted list for each message is something like thisa > b > cAll we have to prove that

(a / 2 + b / 2) > (a / 3 + b / 3 + c / 3)We know that

a > b > c, so theaverage of a and b = (a + b) / 2and

((a + b) / 2) > basa > bso

((a + b) / 2) > c as b > c=> 3 * ((a + b) / 2) — 2 * ((a + b) / 2) > c=> 3 * ((a + b) / 2) > 2 * ((a + b) 2 ) + c=> 3 * ((a + b) / 2) > a + b + c=> ((a + b) / 2) > (a + b + c) / 3=> (a / 2 + b / 2) > (a / 3 + b / 3 + c / 3)So many might ask so why is it not the case when t <= 20, because it contains non-linearity as well as sorted messages list might change as the

tincreases but its not the case when t > 20, all the value decreases when t > 20in C you can find answer in

`O(1)`

by finding the smallest integer number exceeding sum of emojes: we know that sum from 1 to n is equal to`n(n+1)/2`

, so if`k(k+1)/2 > x`

: we just solve this quadradic equation, if`k(k+1)/2 + (k-1)k/2 > x`

we need to use backwards sum formula:`n(k+1) - n(n+1)/2`

. for n=1, 2, 3, ... it gives k, k+(k-1), k+(k-1)+(k-2), ... and here we need to solve this quadric equation:`n(k+1) - n(n+1)/2 >= x-k`

. But in large numbers we get big error, more than 0.5, so we need to check a few surrounding numberssolving quadratic equation in O(sqrt(n)) i think

For Problem D:

No, you don't have to bother:

Remember how GCD works?

We use

`a%b`

to speed up`a-b-b-b.....`

So we can do the same thing here!

Assume

`a >= b`

, and let's call`a%b`

the left-over part,If

`x`

can be represented by using`a`

and`b`

Since we can only get

`a`

,`a-b`

,`a-b-b`

, all the way down to the left-over part (`a%b`

)Then

`x- the left-over part`

should be able to divided up by b,In other word,

`(x - a % b) % b == 0`

.So we can judge if we can get

`x`

by modding GCD:If

`(x - a % b) % b == 0`

then that's a big YES, otherwise continue doing GCD.And here's my code 136836057

I believe this line in the model solution is left from the previous version of the problem, where we asked for the minimum number of moves to obtain $$$x$$$.

Hello,

I did not participate in the contest, but i have some solution implemented for D, an observation is that you always pick max(a,b) then subtract max(a,b) — min(a,b) * K where K is max(a,b)/min(a,b), solution exists if (max(a,b)-x)%min(a,b)==0. Note that if you got min(a,b) as zero or max(a,b) < x then you can't find the solution.

Wow dude, that's neat!

shuffle(cert.begin(), cert.end(), mt19937(time(NULL)));

Why editorial soln of E shuffles cert array ?

Proof?

agree.also I don't understand why do we divide by 2 here : cnt=max(1,⌊a−max(b,x)2b⌋) I solved it using this : y=max((a-x),b)/b;