Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
a = sorted(list(map(int, input().split())))
print('Yes' if a[2] <= a[0] + a[1] + 1 else 'No')
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
n, t = map(int, input().split())
a = list(map(int, input().split()))
id = 0
for i in range(n):
if a[i] > a[id]:
id = i
t -= a[i]
if t < 0:
break
if t >= 0:
id = -1
print(id + 1)
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for t in range(int(input())):
n, m = map(int, input().split())
a = [x - 1 for x in list(map(int, input().split()))]
b = [x - 1 for x in list(map(int, input().split()))]
pos = a[:]
for i in range(n):
pos[a[i]] = i
lst = -1
res = m
for i in range(m):
if pos[b[i]] > lst:
res += 2 * (pos[b[i]] - i)
lst = pos[b[i]]
print(res)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
const int MOD = 998244353;
const int N = 1e6 + 7;
int n;
vector<int> a[N];
int cnt[N];
int inv[N];
int add(int a, int b) {
a += b;
if (a >= MOD) a -= MOD;
return a;
}
int mul(int a, int b) {
return a * 1ll * b % MOD;
}
int binpow(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = mul(res, a);
a = mul(a, a);
b >>= 1;
}
return res;
}
int main() {
scanf("%d", &n);
forn(i, n) {
int k;
scanf("%d", &k);
a[i].resize(k);
forn(j, k) scanf("%d", &a[i][j]);
forn(j, k) cnt[a[i][j]]++;
}
forn(i, N) inv[i] = binpow(i, MOD - 2);
int ans = 0;
forn(i, n) for (auto x : a[i])
ans = add(ans, mul(mul(inv[n], inv[sz(a[i])]), mul(cnt[x], inv[n])));
printf("%d\n", ans);
}
```

Idea: Ne0n25

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define pb push_back
#define mp make_pair
#define sqr(a) ((a) * (a))
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define forn(i, n) for (int i = 0; i < int(n); ++i)
#define fore(i, l, r) for (int i = int(l); i < int(r); ++i)
typedef long long li;
typedef long double ld;
const int N = 55;
const li INF = 2e18;
int n;
li k;
li cycl[N], cnt[N];
bool used[N];
int ans[N];
li add(li x, li y) {
return min(INF, x + y);
}
li mul(li x, li y) {
ld t = ld(x) + y;
if (t > INF) return INF;
return x * y;
}
void solve() {
cin >> n >> k;
--k;
cycl[0] = cycl[1] = 1;
fore(i, 2, n + 1)
cycl[i] = mul(cycl[i - 1], i - 1);
cnt[n] = 1;
for (int i = n - 1; i >= 0; i--) {
cnt[i] = 0;
fore(val, i, n) {
int len = (val - i) + 1;
cnt[i] = add(cnt[i], mul(cnt[i + len], cycl[len - 1]));
}
}
if (cnt[0] <= k) {
cout << -1 << endl;
return;
}
memset(used, 0, sizeof(used));
memset(ans, -1, sizeof(ans));
forn(i, n) {
fore(val, i, n) {
int len = (val - i) + 1;
li cur = mul(cnt[i + len], cycl[len - 1]);
if (cur <= k) {
k -= cur;
continue;
}
ans[i] = val;
used[val] = true;
for (int j = i + 1; j < i + len; j++) {
int lft = len - (j - i) - 1;
fore(nval, i, val) if (!used[nval] && j != nval) {
if (j != i + len - 1) {
int tmp = ans[nval];
while (tmp != -1 && tmp != j)
tmp = ans[tmp];
if (tmp == j) continue;
}
li cur = mul(cnt[i + len], cycl[lft]);
if (cur <= k) {
k -= cur;
continue;
}
ans[j] = nval;
used[nval] = true;
break;
}
}
i += len - 1;
break;
}
}
forn(i, n) cout << ans[i] + 1 << ' ';
cout << endl;
}
int main() {
int tc;
cin >> tc;
forn(i, tc) solve();
}
```

1279F - New Year and Handle Change

Idea: vovuh

**Tutorial**

Tutorial is loading...

**Solution (vovuh)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = 1000 * 1000 + 11;
const int INF = 1e9;
int n, k, l;
string s;
int a[N];
pair<int, int> dp[N];
int calc(int mid) {
for (int i = 0; i <= n; ++i) {
dp[i] = make_pair(INF, INF);
}
dp[0] = make_pair(0, 0);
for (int i = 0; i < n; ++i) {
if (dp[i + 1] > make_pair(dp[i].first + a[i], dp[i].second)) {
dp[i + 1] = make_pair(dp[i].first + a[i], dp[i].second);
}
if (dp[min(n, i + l)] > make_pair(dp[i].first + mid, dp[i].second + 1)) {
dp[min(n, i + l)] = make_pair(dp[i].first + mid, dp[i].second + 1);
}
}
return dp[n].second;
}
int solve() {
int l = 0, r = n;
int res = 0;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(mid) > k) {
l = mid + 1;
res = mid;
} else {
r = mid - 1;
}
}
if (calc(res) <= k) return 0;
calc(res + 1);
return dp[n].first - (res + 1) * 1ll * k;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
// freopen("output.txt", "w", stdout);
#endif
cin >> n >> k >> l >> s;
for (int i = 0; i < n; ++i) {
a[i] = islower(s[i]) > 0;
}
int ans = INF;
ans = min(ans, solve());
for (int i = 0; i < n; ++i) {
a[i] = isupper(s[i]) > 0;
}
ans = min(ans, solve());
cout << ans << endl;
return 0;
}
```

Can someone guide me through PROBLEM D.Im not getting the same result as the test case.Can someone simplify the tutorial.

Probability of choosing 1 kid in among n is

`1/n`

. Let that kid is "x".Probability of choosing 1 item from the list of the chosen kid(x) is

`1/k`

. Let that item is "y".So probability of choosing a pair (x, y) is

`1/n AND 1/k`

.Now lets choose 1 kid from n kids again. And probability of choosing this kid is

`1/n`

(it is not 1/(n-1) because it is independent form the previous choice. Let this kid is "z".As there are n kids and all the items of a kids list are different so we can say the probability of choosing a kid who want y item is

`frequency(y)/n`

.So probability of choosing a z kid who want y item is

`1/n AND frequency(y)/n`

.Probability of finding a valid triple (x, y, z) is

`(1/n AND 1/k) AND (1/n AND frequency(y)/n)`

.then what...?? do we have to sum all the probabilities of different students..?? sorry but i didn't get that. pls explain by the first test case. and i don't know why i am getting wrong answer for test case 1 but for case 2 answer is perfect.

Query Contest

In the solution to F, why is it necessary to include the $$$res$$$ variable in the binary search? It seems odd since the last value of $$$res$$$ would always be a $$$mid$$$ where $$$check(mid)$$$ returned more than the permitted operations. In which case the later $$$check(res)<=k$$$ would not trigger. However, replacing it with $$$hi + 1$$$ gives WA on 78.

Otherwise, thanks for a thorough explanation!

Can someone explain the "standard method of lexicographic recovery" of problem E more in detail? I never heard of a standard method for that before.

Similar to the method to solve "restore the k-th permutation". I think you can google the solution to that. Just instead of choosing the next number to put we choose the entire block of numbers.

Try values in the prefix and have a count function to calculate the number of different suffixed having some property. Something like:

codeThanks. Now I think I have a better idea of the algorithm. It would be something like this:

First we need to figure out the size of the first block. We try sizes 1, 2, 3, ..., N in that order (because of lexicographic order). We keep a running count of how many permutations we have skipped (initially 0). The number of permutations where the first block has size x is $$$(x-2)! \times DP(x+1)$$$. So we keep skipping block sizes until we find the block size x where the k-th permutation lives. So let's call $$$k' = k - skipped$$$. This means we want the k'-th permutation among all permutations where the first block has size x.

So now we know the first block has size x, but we still don't know the exact permutation of numbers from 1 to x of the first block. To find it, we need to remember that there are (x-2)! good permutations for the first block, and that for each one we can fill the remaining numbers to the right in DP(x+1) ways. This means we need to find the r-th permutation of the first block, where r = k'/DP(x+1). So how do we find the r-th good permutation of a block of size x? Here the idea would be doing something like lexicographic recovery: first in a block of size x, we know the first number is x. So we need to fill the second, third, ..., and x-th numbers of the block. For the second number we can try 1, 3, 4, ..., x-1 (x is already used and 2 would create a self-loop). So this is the part I haven't figured out yet (and I would appreciate some help):

1) How do we check that the prefix of numbers we have placed so far in the block is valid? I guess the naive way of following pointers and making sure there are no closed cycles should be enough (if we close a cycle prematurely then it's wrong).

2) This part I don't have any clue yet: How do we count the number of ways we can fill the remaining numbers to the right (the suffix of the block we haven't filled yet) such that the full permutation is good? We have to count making sure we don't accidentally count permutations that would create invalid cycles in combination with the prefix we have placed so far. No clue how to do that.

if you have prefix of length $$$X$$$ and set first $$$Y$$$ numbers correctly(no cycle there), the rest can be set in $$$(X - Y - 1)!$$$ ways. You can see it in code as well, where $$$cycl[lft]$$$ is used. You can think about it like this, you have to put $$$X-Y$$$ numbers in rest of the places. It's obvious that no number can go to it's place like $$$p[a] = a$$$ as it will create a cycle of length one. Now putting some number in some place, let's say $$$p[2]=6$$$ creates a constraint $$$p[6]\neq2$$$, but there already was a constraint $$$p[6]\neq6$$$ so for one place there is still one constraint about numbers that are left. So if you know that block has size $$$6$$$ it should start with $$$6$$$ and number of ways is $$$4!$$$. When you move to next position, you basically have same problem, you "know" (by iterating) the first number and size is one less.

After discussing the problem with my brother we have come up with a proof of ans(c) being convex. The way I think of the problem is that you are given a list of numbers containing $$$0$$$s and $$$1$$$s, and then let $$$g(k)$$$ be the maximum number of $$$1$$$s you can cover with $$$k$$$ intervals of length $$$L$$$. In this formulation the goal will be to prove that $$$g(k)$$$ is concave.

Take an optimal $$$k$$$ interval solution and an optimal $$$k + 2$$$ interval solution. Then make a bipartite graph out of the intervals, where edges are drawn between intervals that intersect. Here is an example for $$$k=7$$$ (the black bars symbolizes the intervals of the two solutions)

The bipartite graph then becomes

The reason for picking $$$k$$$ and $$$k + 2$$$ is because I want to create a $$$k + 1$$$ configuration from this that is at least as good as the mean of $$$g(k)$$$ and $$$g(k + 2)$$$. The method I apply is based on analysis of alternating paths in the bipartite graph, in particular what happens if you "flip" a path (meaning you exchange intervals between the two solutions). For example flipping the 3rd path from the left will result in

The following is a proof of the existence of a $$$k + 1$$$ interval solution that contains at least as many $$$1$$$s as the mean of the optimal $$$k$$$ solution and the optimal $$$k + 2$$$ solution.

Formal proofWe know that there must exist at least $$$2$$$ odd length paths that start and end in $$$k + 2$$$ since the solution for $$$k + 2$$$ contains two more intervals than $$$k$$$. Flipping any one of them will cause the optimal $$$k$$$ solution to be increased by some $$$c \ge 0$$$, from $$$g(k)$$$ to $$$g(k) + c$$$, and the optimal $$$k + 2$$$ solution to be decreased by $$$c$$$, from $$$g(k + 2)$$$ to $$$g(k + 2) - c$$$. So after the flip we have two $$$k + 1$$$ solutions, and by the pigeon hole principle one solution covers $$$\ge \frac{g(k) + g(k + 2)}{2}$$$ ones and the other covers $$$\le \frac{g(k) + g(k + 2)}{2}$$$ ones.

So conclusion from this is that $$$g(k + 1) \ge \frac{g(k) + g(k + 2)}{2}$$$, i.e. $$$g$$$ is concave.

Awesome! This kind of proof resembles the proof of convexity for Monge dynamic programming. This also has an additional nice property of being constructive.

For the proofs using less brain, it seems the problem can be reduced into negative cycle canceling. Construct an edge $$$i \rightarrow i + 1$$$ with cost 0, and $$$j \le i$$$ with cost $$$-sum[i, j)$$$ for $$$i < j \le i + L$$$. Since negative cycle canceling is dual to the augmenting path, it should have the same convex property.

In the contest, I thought the problem had an MCMF modeling. But after the contest, what I had in mind turned out to be wrong, and this is the best I could get afterwards.

Just curious as to why is it that some problem names in the tutorial appear in Russian (like problem F), while others are in English? I have seen this in many previous editorials as well.

For the solution of Verse for Santa, alot of macros are used. Its not that clear to me as i am not that fluent in c++ and macros are not defined in solution. Can someone please give reference to their full solution link. It will help me thanks. If its java then better.

Its a python solution, not a C++ solution.

Got the solution's idea. Thanks

In the first question "New Year garland" For the second test case where 1 red, 2 green and 10 blue bulbs are given. we can arrange them as GRBGBBBBBBBBB But according to the question it should print NO

No, you can't. It is given that two same lights can't be adjacent.

They can be adjacent if they are in the end of the garland

Note that it's ok to have lamps of the same color on the ends of the garland.

It's written in one of the paragraph

u have understood it wrong, lamps of same colour can be adjacent mean, at end means , a point where the garland makes the full loop.

Thanks for this

In problem C its not clear to me for case.

7 2

2 1 7 3 4 5 6

3 1

how is output 8. I am having doubts can someone please clarify. Thanks

First in array A {2 1 7 3 4 5 6},we need to remove first 4 element to grab 3 and putting back the removed elements in order of ({1,2,7} or {1,7,2}) and your array A become {1,2,7,4,5,6}; the total opearations you did before was 7{removing 4 elements + putting back 3 elements} and now you just need 1 more operation to remove 1 from A; so total no of operations = 7+1 = 8;

Thanks

Can someone please explain what is the use of the pos array in 1279C?

In 1279D, problem D, there is error in formulas. It should be $$$1 / (n k_{x})$$$ and $$$cnt_{y} / n$$$.

thanks, now i can understand that.

why my approach is wrong? https://codeforces.com/contest/1279/submission/68775026

in c why we initialise res=m? why can't we add res+=1 in the else statement when pos[b[i]] < last ??

I can't understand what

(this choice is independent of choosing x and y)means in D problem, my solution works as follow:But that don't give me the correct answer. Can anyone help me?

have the same problem :(

try to search about dependent events in probability on Google, i found any help in that.

that is a really good book about probability.

after that, see that comment, he/her shows two errors at editorial.

sorry for my bad english.

can someone point out what is the error in this code for problem c https://codeforces.com/contest/1279/submission/69722050

In problem C, shouldn't we have

`res = 2 * (pos[b[i]] - i)`

than`res += 2 * (pos[b[i]] - i)`

because we only need to calculate 2*K+1 seconds for last found present, than other could be simple taken in (no. of presents-1) seconds. Here's my code :and it's giving wrong answer also here's my submission I don't understand why?

I was trying to figure out all possible triplets in Problem D . But I couldn't figure out all 8 possibilities .

Here is what I got ..

for the first case which is ---

2

2 2 1

1 1

(1 , 2 , 1) , (1 , 2 , 2)

(1 , 1 , 1) , (1 , 1 , 2)

(2 , 1 , 1) , (2 , 1 , 2)

Where (x , y , z) is ...

x = kid number .

y = one of the gifts kid x wants

z = the chosen gift y is given to kid z .

Now I am wondering what are 2 other possibilities ?

Can anybody help me ??

You are right, there are 6 possibilities. But they do not have the same probability.

After first selection, both x = 1 and x = 2 have probability of 1/2. If he selected x = 2, then we have only 1 selection for y, so selection (x = 2, y = 1) also has probability of 1/2. Finally, each of (2, 1, 1) and (2, 1, 2) would be 1/4.

In case of x = 1, both y and z have two options, so probability for each of (1, 2, 1), (1, 2, 2), (1, 1, 1), (1, 1, 2) is 1/8.

Then, since the only incorrect choice is (1, 2, 2), whose probability is 1/8, the answer will be 7/8.

Ouch !

I feel so dumb now . How can I miss that for each kid the sum of probability distribution will be $$$1/n$$$ .

In problem F, the claim is $$$ dp[n][k] = res(\lambda_{opt},c_{\lambda_{opt}}) - \lambda_{opt}k $$$.

Why is the last value $$$k$$$ instead of $$$ c_{\lambda_{opt}} $$$?

You missed the previous paragraph where we claim that $$$res(\lambda_{opt},k)=res(\lambda_{opt},c_{\lambda_{opt}})$$$.