Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
vector<int> l(3);
for (int i = 0; i < 3; ++i)
cin >> l[i];
bool ok = false;
for (int i = 0; i < 3; ++i)
ok |= l[i] == l[(i + 1) % 3] + l[(i + 2) % 3];
for (int i = 0; i < 3; ++i) if (l[i] % 2 == 0)
ok |= l[(i + 1) % 3] == l[(i + 2) % 3];
cout << (ok ? "YES\n" : "NO\n");
}
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (awoo)**

```
for _ in range(int(input())):
n = int(input())
p = [int(x) for x in input().split()]
s = input()
l = sorted([[s[i], p[i], i] for i in range(n)])
q = [-1 for i in range(n)]
for i in range(n):
q[l[i][2]] = i + 1
print(*q)
```

Idea: 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())
typedef long long li;
const int INF = int(1e9);
const li INF64 = li(1e18);
int n;
li k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.resize(n);
fore (i, 0, n)
cin >> a[i];
return true;
}
li accurateFloor(li a, li b) {
li val = a / b;
while (val * b > a)
val--;
return val;
}
inline void solve() {
sort(a.begin(), a.end());
vector<li> pSum(n + 1, 0);
fore (i, 0, n)
pSum[i + 1] = pSum[i] + a[i];
li ans = 1e18;
fore (y, 0, n) {
//(a[0] - x)(y + 1) + (pSum[n - y] - a[0]) <= k
//a[0] - x <= (k - pSum[n - y] + a[0]) / (y + 1)
//x == a[0] - (k - pSum[n - y] + a[0]) / (y + 1)
li x = a[0] - accurateFloor(k - pSum[n - y] + a[0], y + 1);
ans = min(ans, y + max(0LL, x));
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--) {
read();
solve();
}
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include <bits/stdc++.h>
using namespace std;
const int MOD = 998244353;
int add(int x, int y)
{
x += y;
while(x >= MOD) x -= MOD;
while(x < 0) x += MOD;
return x;
}
int main()
{
int n;
cin >> n;
int k;
cin >> k;
string s;
cin >> s;
vector<int> p(n + 1);
for(int i = 0; i < n; i++) p[i + 1] = p[i] + (s[i] - '0');
vector<vector<int>> C(n + 1);
for(int i = 0; i <= n; i++)
{
C[i].resize(i + 1);
C[i][0] = C[i][i] = 1;
for(int j = 1; j < i; j++)
C[i][j] = add(C[i - 1][j], C[i - 1][j - 1]);
}
int ans = 1;
for(int i = 0; i < n; i++)
for(int j = i + 1; j < n; j++)
{
int cnt = j + 1 - i;
int cnt1 = p[j + 1] - p[i];
if(cnt1 > k || p[n] < k) continue;
cnt -= 2;
if(s[i] == '0') cnt1--;
if(s[j] == '0') cnt1--;
if(cnt1 <= cnt && cnt1 >= 0 && cnt >= 0)
ans = add(ans, C[cnt][cnt1]);
}
cout << ans << endl;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); ++i)
int main() {
int t;
scanf("%d", &t);
while (t--) {
int n, m;
scanf("%d%d", &n, &m);
vector<int> x(n);
forn(i, n) scanf("%d", &x[i]);
vector<vector<int>> a(n, vector<int>(m));
forn(i, n) forn(j, m) scanf("%1d", &a[i][j]);
int ans = -1;
vector<int> best;
forn(mask, 1 << n) {
vector<int> val(m);
forn(i, n) forn(j, m) if (a[i][j]) val[j] += ((mask >> i) & 1) ? +1 : -1;
int res = 0;
forn(i, n) res += ((mask >> i) & 1) ? -x[i] : x[i];
vector<int> p(m);
iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int x, int y) { return val[x] < val[y]; });
forn(i, m) res += val[p[i]] * (i + 1);
if (res > ans) ans = res, best = p;
}
vector<int> ansPerm(m);
forn(i, m) ansPerm[best[i]] = i;
forn(i, m) printf("%d ", ansPerm[i] + 1);
puts("");
}
}
```

Idea: Neon

**Tutorial**

Tutorial is loading...

**Solution (Neon)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 13;
using li = unsigned long long;
int pr[N];
li hs[N], f[N];
unordered_map<li, int> rf;
int main() {
int n;
scanf("%d", &n);
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
iota(pr, pr + N, 0);
for (int i = 2; i <= n; ++i) if (pr[i] == i) {
for (int j = i; j <= n; j += i) pr[j] = min(pr[j], i);
hs[i] = rnd();
}
for (int i = 2; i <= n; ++i) {
f[i] = f[i - 1];
int x = i;
while (x != 1) {
f[i] ^= hs[pr[x]];
x /= pr[x];
}
rf[f[i]] = i;
}
auto solve = [&] (int n) -> vector<int> {
li fp = 0;
for (int i = 2; i <= n; ++i) fp ^= f[i];
if (fp == 0) return {};
if (rf.count(fp)) return {rf[fp]};
for (int i = 2; i <= n; ++i) {
li x = f[i] ^ fp;
if (rf.count(x) && rf[x] != i) return {rf[x], i};
}
return {2, n / 2, n};
};
auto ans = solve(n);
printf("%d\n", n - (int)ans.size());
for (int i = 1; i <= n; ++i)
if (find(ans.begin(), ans.end(), i) == ans.end()) printf("%d ", i);
puts("");
}
```

How can we solve Problem D in O(n)?

Compute the location of each “1” in the string and for each of them, count the number of strings where it is the first “1” that is moved. This is just the difference of two binomial coefficients.

EDIT: here is a relatively clean example solution

I had same solution, but I precompute all binomials in O(n^2). Thanks for your code! I think I learned something!

not just in o(n) but you can solve this in o(1) also

## include <bits/stdc++.h>

using namespace std;

int main() { int t; cin>>t;

}

Is someone solved C using the ternary search on final value of minimum element and cost of comparison equals no of moves required for that final value?

I had, but unfortunately it failed on system tests. I got accepted after system tests ( https://codeforces.com/contest/1622/submission/140871019 ). However, my solution is very strange.....

Why do we need

randomnumbers for primes in problem F?For hashing. Xor have this property that if you xor same value even number of times, then you get 0. We want to check if in 1! 2! ... n! all primes exists even number of times.

I know this trick from Zobrist hashing. Not sure how it is call in CP.

Here I've got a solution to problem F without hashing or any other randomicity. Though I don't know how to prove it, it seems to be correct. Due to the limitation of the space, I'll only put the conclusions here.

First if $$$ n = 1 $$$, the answer subset include only $$$ 1 $$$. Now we assume $$$ n \not = 1 $$$.

If $$$ n \equiv 1 \pmod 2 $$$, we check if $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is a square number. If so, the answer subset is all numbers from $$$ 1 $$$ to $$$ n $$$ except $$$ \frac{n - 1}{2} - 2 $$$ and $$$ n - 2 $$$.

If $$$ n \cdot (\frac{n - 1}{2} - 1) $$$ is not a square number, $$$ n $$$ will not be in the answer subset, and we let $$$ n \leftarrow n - 1 $$$ and continue our discussion.

So we now have $$$ n \equiv 0 \pmod 2 $$$. Let $$$ m = \frac{n}{2} $$$.

If $$$ m \equiv 0 \pmod 2 $$$, the answer is $$$ 1, \cdots, n $$$ except $$$ m $$$.

Else we have $$$ m \equiv 1 \pmod 2 $$$. Check if $$$ \frac{m + 1}{2} $$$ is a square number. If so, answer is $$$ 1, \cdots, n $$$ except $$$ m + 1 $$$.

We also check if $$$ m = 9 $$$. If $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 7 $$$.

In the case that neither $$$ \frac{m + 1}{2} $$$ is a square number nor $$$ m = 9 $$$, answer is $$$ 1, \cdots, n $$$ except $$$ 2 $$$ and $$$ m $$$.

Obviously there must be $$$ \text{answer's size} \geqslant n - 3 $$$, for there will be at most $$$ 2 $$$ absent number for even $$$ n $$$ and one more for odd $$$ n $$$.

Check 140891764 for code. I use this OEIS sequence to reach some of the same conclusion as in the official solution.

As you see, this solution is partly based on the official solution, but to construct the subset by just discussing about $$$ n $$$, instead of using hashing.

How to proof this constructed method?

In the editorial of D do you mean (excluding them) instead of (including them) or I misunderstood something

Yeah , why are i and j made as ‘1’ . Can this be explained please..

I don't know why I printed max(result, 1) and ruined my submission in problem D :'(

Same mistake :)

+1;

can anyone give me O(n) solution

140865670 here you go

Thanks!!

In problem C i'm facing overflow issue. Can someone please help to find out where is my code overflowing i have verified the calculations and data type multiple times. 140977108

Use "ll reduce_operations" in place of "int reduce_operations" code

Thanks

Problem B: "The general way to prove it is to show that if the order has any inversions, we can always fix the leftmost of them (swap two adjacent values), and the cost doesn't increase." Can anyone give a proof on that?

I referred to this solution and understood the logic easily — https://www.youtube.com/watch?v=Gd9O95Ciooo&t=1s

You can get better intuition here -> Link

Can someone please explain D, tutorial explanation is somewhat tough to understand.

Why my solution is getting TLE for problem B, can anybody help me. My sol.140979076

You can check out this solution, easily understandable — https://www.youtube.com/watch?v=Gd9O95Ciooo&t=1s

For problem D test case 23 has answer 0.How is 0 answer possible given we always have the string s?

The answer is not 0, but 0 mod P, which means that the actual integer answer is a multiple of P = 998244353.

I see.Thank you!

For problem F, solution part: Why do we have to include

`rf[x]!=x`

in`if (rf.count(x) && rf[x] != x) return {rf[x], i};`

?Is there any efficient ternary search algorithm???? I have used ternary search on 1622C - Присвоить или уменьшить. It passed the pretest but give a wrong verdict on system test case. Though, I have also checked +-2 range from the expected range manually. Here is my solution 140786085

Please help me.

Solution of Problem B is possible in O(N) time for each test case. This can be achieved by using Hash maps for creating inverse function from rating p to song number. If the lowest rated song is liked it is given rating #disliked songs + 1, else rating 1. And so on can be done just by iterating over the Hash map. (Hash map can be implemented using array which will guarantee the songs are visited in ascending order of priority.

I tried using binary search for C. But the solution gets TLE. I can't find the reason for my mistake. Can somebody help?

Here's the link to my submission 141226085

at some point lo and hi becomes equal and ur loop becomes infinite loop. try lo<hi in the loop condition. Also don't use i<=mid for inner loop condition, rather use i<=mid && i<n for better performance.

Here's the link 141232531

How sometimes answer for D can be 0. Could you please explain?

The answer is 0 modulo 998244353, not 0 new orderings

Can someone explain the accurateFloor function in problem C? why can't we simply write c/d — 1 when c<0?

for exmple ： -3 / 1 ， you can't c/d — 1

For problem D, can't we use the inclusion/exclusion principle to count duplicate occurrences?

Here is my solution, but it's giving WA in test 10.

These are the steps of my solution:

1. Compute all the intervals [i,j] such that the number of 1 in the interval is k. Let s1, s2, s3,...sk be the intervals.

2. Number of common combinations between s1, s2, s3,...si is the arrangement of one and zero that are present in the intersection of these. Then use inclusion and exclusion principle to get union of these.

Consider this testcase

We need to permute substrings containing exactly three $$$1s$$$. Since the entire string contains a single $$$0$$$, the uniqueness can be identified by the position of $$$0$$$. Since $$$[1110]$$$ contains exactly three $$$1s$$$, we can place a $$$0$$$ at any of the first four spots. Since $$$[1011]$$$ also contains exactly three $$$1s$$$, we can place a $$$0$$$ at the last two spots too. Hence, there are 6 possible configurations.

However, your code outputs 7.

Thanks for providing a test case. Can you explain to me why my logic is wrong?

The problem involves substrings instead of subsequences. You can prove by drawing or otherwise, that only adding contributions from

`k-one`

substrings and removing those of`(k-1)-one`

substrings is optimal, rather than`c(k) - c(k-1) + c(k-2) - c(k-3)...`

.You would also have to make sure that all the intervals must follow

`(l == 0 || v[l - 1] == 1) && (r == n - 1 || v[r + 1] == 1)`

, as its only feasible to stop moving left or right when we come across a`1`

or else we will be recounting things.code for above approach

Understood it. Thanks for providing the explanation.

I tried using binary search, but my code is getting tle on test case 39 and idk why. Its also weird how Java is only allowed 2 seconds. Is this possible to solve with a binary search using Java? https://paste-bin.xyz/30397.

EDIT : Nvm, the tle is because Javas Arrays.sort is n^2. Shuffling the array, then sorting passes

In Problem F, is there any chance I random some bad number and get a wrong answer?

Could I use n bool arrays to record the amount of every possible prime factor of each number? The space complexity would be O(n^2) then.

For Problem D, I think there's a pretty manageable way of iterating over the substrings of interest and keeping track of how shuffling different substrings may result in the same string.

Iterating from left to right, say we have processed the substring $$$[l_1, r_1]$$$ and we're now processing $$$[l_2, r_2]$$$. $$$[l_2, r_2]$$$ has a part that overlaps with $$$[l_1, r_1]$$$ and a part that doesn't. Shuffling $$$[l_2, r_2]$$$ will result in a duplicate string if the part that doesn't overlap remains the same as the original.

If there are $$$c$$$ ones in the overlapping interval, then there are $$${{r_1 - l_2 + 1} \choose c}$$$ duplicate strings that result from shuffling $$$[l_2, r_2]$$$.

This approach can reach $$$O(n)$$$.