Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
bool ans[26];
void solve() {
string s;
cin >> s;
memset(ans, 0, sizeof(ans));
for (int i = 0; i < s.size(); i++) {
int j = i;
while (j + 1 < s.size() && s[j + 1] == s[i])
j++;
if ((j - i) % 2 == 0)
ans[s[i] - 'a'] = true;
i = j;
}
for (int i = 0; i < 26; i++) if (ans[i])
cout << char('a' + i);
cout << endl;
}
int main() {
int q;
cin >> q;
while (q--) solve();
}
```

Idea: adedalic

**Tutorial**

Tutorial is loading...

**Solution (adedalic)**

```
fun main() {
val q = readLine()!!.toInt()
for (ct in 1..q) {
val n = readLine()!!.toInt()
var (odd, evenGood, evenBad) = listOf(0, 0, 0)
for (i in 1..n) {
val s = readLine()!!
when {
s.length % 2 == 1 -> odd++
s.count { it == '0' } % 2 == 0 -> evenGood++
else -> evenBad++
}
}
println(n - if (odd == 0 && evenBad % 2 == 1) 1 else 0)
}
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
int t;
string a;
int main() {
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> a;
string s[2];
for(auto x : a)
s[int(x - '0') & 1] += x;
reverse(s[0].begin(), s[0].end());
reverse(s[1].begin(), s[1].end());
string res = "";
while(!(s[0].empty() && s[1].empty())){
if(s[0].empty()){
res += s[1].back();
s[1].pop_back();
continue;
}
if(s[1].empty()){
res += s[0].back();
s[0].pop_back();
continue;
}
if(s[0].back() < s[1].back()){
res += s[0].back();
s[0].pop_back();
}
else{
res += s[1].back();
s[1].pop_back();
}
}
cout << res << endl;
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(2e5) + 99;
const int INF = int(1e9) + 100;
int t;
int n;
long long s;
pair<int, int> p[N];
bool ok(int mid){
long long sum = 0;
int cnt = 0;
vector <int> v;
for(int i = 0; i < n; ++i){
if(p[i].second < mid)
sum += p[i].first;
else if(p[i].first >= mid){
sum += p[i].first;
++cnt;
}
else
v.push_back(p[i].first);
}
assert(is_sorted(v.begin(), v.end()));
int need = max(0, (n + 1) / 2 - cnt);
if(need > v.size()) return false;
for(int i = 0; i < v.size(); ++i){
if(i < v.size() - need)
sum += v[i];
else
sum += mid;
}
return sum <= s;
}
int main() {
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d %lld", &n, &s);
for(int i = 0; i < n; ++i)
scanf("%d %d", &p[i].first, &p[i].second);
sort(p, p + n);
int lf = 1, rg = INF; ///WA -> 10^9
while(rg - lf > 1){
int mid = (lf + rg) / 2;
if(ok(mid)) lf = mid;
else rg = mid;
}
printf("%d\n", lf);
}
return 0;
}
```

1251E1 - Voting (Easy Version)

1251E2 - Voting (Hard Version)

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(3e5) + 99;
int t, n;
vector <int> v[N];
int main() {
int t;
scanf("%d", &t);
for(int tc = 0; tc < t; ++tc){
scanf("%d", &n);
for(int i = 0; i < n; ++i)
v[i].clear();
for(int i = 0; i < n; ++i){
int x, s;
scanf("%d %d", &x, &s);
v[x].push_back(s);
}
multiset <int > q;
long long res = 0;
int pref = n;
int cnt = 0;
for(int i = n - 1; i >= 0; --i){
pref -= v[i].size();
int need = i - pref;
for(auto x : v[i]) q.insert(x);
while(cnt < need){
++cnt;
res += *q.begin();
q.erase(q.begin());
}
}
printf("%lld\n", res);
}
return 0;
}
```

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
const int LOGN = 20;
const int N = (1 << LOGN);
const int MOD = 998244353;
const int g = 3;
#define forn(i, n) for(int i = 0; i < int(n); i++)
inline int mul(int a, int b)
{
return (a * 1ll * b) % MOD;
}
inline int norm(int a)
{
while(a >= MOD)
a -= MOD;
while(a < 0)
a += MOD;
return a;
}
inline int binPow(int a, int k)
{
int ans = 1;
while(k > 0)
{
if(k & 1)
ans = mul(ans, a);
a = mul(a, a);
k >>= 1;
}
return ans;
}
inline int inv(int a)
{
return binPow(a, MOD - 2);
}
vector<int> w[LOGN];
vector<int> iw[LOGN];
vector<int> rv[LOGN];
void precalc()
{
int wb = binPow(g, (MOD - 1) / (1 << LOGN));
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, 1);
iw[st].assign(1 << st, 1);
int bw = binPow(wb, 1 << (LOGN - st - 1));
int ibw = inv(bw);
int cw = 1;
int icw = 1;
for(int k = 0; k < (1 << st); k++)
{
w[st][k] = cw;
iw[st][k] = icw;
cw = mul(cw, bw);
icw = mul(icw, ibw);
}
rv[st].assign(1 << st, 0);
if(st == 0)
{
rv[st][0] = 0;
continue;
}
int h = (1 << (st - 1));
for(int k = 0; k < (1 << st); k++)
rv[st][k] = (rv[st - 1][k & (h - 1)] << 1) | (k >= h);
}
}
inline void fft(int a[N], int n, int ln, bool inverse)
{
for(int i = 0; i < n; i++)
{
int ni = rv[ln][i];
if(i < ni)
swap(a[i], a[ni]);
}
for(int st = 0; (1 << st) < n; st++)
{
int len = (1 << st);
for(int k = 0; k < n; k += (len << 1))
{
for(int pos = k; pos < k + len; pos++)
{
int l = a[pos];
int r = mul(a[pos + len], (inverse ? iw[st][pos - k] : w[st][pos - k]));
a[pos] = norm(l + r);
a[pos + len] = norm(l - r);
}
}
}
if(inverse)
{
int in = inv(n);
for(int i = 0; i < n; i++)
a[i] = mul(a[i], in);
}
}
int aa[N], bb[N], cc[N];
inline void multiply(int a[N], int sza, int b[N], int szb, int c[N], int &szc)
{
int n = 1, ln = 0;
while(n < (sza + szb))
n <<= 1, ln++;
for(int i = 0; i < n; i++)
aa[i] = (i < sza ? a[i] : 0);
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : 0);
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = mul(aa[i], bb[i]);
fft(cc, n, ln, true);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
}
vector<int> T[N];
int a[N];
int b[N];
int n, k;
int ans[N];
int Q[N];
int fact[N];
int rfact[N];
int auxa[N];
int auxb[N];
int auxc[N];
int C(int n, int k)
{
if(n < 0 || k < 0 || k > n) return 0;
return mul(fact[n], mul(rfact[k], rfact[n - k]));
}
vector<int> newtonExp(int a, int b, int p)
{
vector<int> res(p + 1);
for(int i = 0; i <= p; i++)
res[i] = mul(C(p, i), mul(binPow(a, i), binPow(b, p - i)));
return res;
}
int main()
{
precalc();
fact[0] = 1;
for(int i = 1; i < N; i++) fact[i] = mul(fact[i - 1], i);
for(int i = 0; i < N; i++) rfact[i] = inv(fact[i]);
scanf("%d %d", &n, &k);
for(int i = 0; i < n; i++) scanf("%d", &a[i]);
for(int i = 0; i < k; i++) scanf("%d", &b[i]);
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++) scanf("%d", &Q[i]);
map<int, int> cnt;
for(int i = 0; i < n; i++)
cnt[a[i]]++;
for(int i = 0; i < k; i++)
{
int redL = b[i];
int cnt1 = 0;
int cnt2 = 0;
for(auto x : cnt)
{
if(x.first >= redL)
break;
if(x.second == 1)
cnt1++;
else
cnt2++;
}
memset(auxa, 0, sizeof auxa);
memset(auxb, 0, sizeof auxb);
memset(auxc, 0, sizeof auxc);
vector<int> p1 = newtonExp(2, 1, cnt1);
vector<int> p2 = newtonExp(1, 1, cnt2 * 2);
int sa = p1.size();
int sb = p2.size();
int sc;
for(int j = 0; j < sa; j++)
auxa[j] = p1[j];
for(int j = 0; j < sb; j++)
auxb[j] = p2[j];
multiply(auxa, sa, auxb, sb, auxc, sc);
for(int j = 0; j < q; j++)
{
int cntW = Q[j] / 2 - redL - 1;
if(cntW >= 0 && cntW < sc)
ans[j] = norm(ans[j] + auxc[cntW]);
}
}
for(int i = 0; i < q; i++)
printf("%d\n", ans[i]);
}
```

in c tutorial what does

`thirst`

means ?I think it's

`first`

rather than`thirst`

.Maybe just another typo...

Can someone please explain the DP solution of E1?

Sort all the voters in the order of non-decreasing values of $$$m$$$

Let $$$dp[ind][team]$$$ store the minimum amount of money you need to spend to make first $$$ind+1$$$ voters vote for you, when already $$$team$$$ number of voters are voting for you. So our final answer will be stored in $$$dp[n-1][0]$$$.

Now let's see the transitions from $$$dp[ind][team]$$$

value of $$$dp[ind][team]$$$ will be the minimum of all these three. For our base condition, when we have only one voter to consider $$$(ind=0)$$$, then we'll have to either pay him or not, depending on the number of voters we currently have with us.

The 1st transition works because, that state will be filled only when all of first $$$ind$$$ voters have agreed to vote us.

Implementation: 63362330

Actually, you don't need the first transition at all. Taking a voter for free is covered by the second transition, and cases when

teamvalue for some states is larger than needed are handled by the nature of DP automatically. You only decrease the number of extra votes by paying the voters (as in the third transition).The successful submission of your code without the first transition http://mirror.codeforces.com/contest/1251/submission/63500118

Thanks! edited.

Can someone please help me finding bug in my solution for the problem

E2. It's givingWAontest case 3, the test case is really large so I'm not able to find out which input is giving WA.Link to my code

may be you need

`lower_bound`

instead of`find`

, and`totalcost+=cheapest.f`

for adding the costMy approach for F is very dirty. (I gave up to code this)

Let's make some definitions:

`unique whiteboard`

which whiteboard has unique height.`non-unique whiteboard`

which is whiteboard but not unique whiteboard.Suppose there are $$$x$$$ unique whiteboards and $$$y$$$ non-unique whiteboards, and you picked $$$x_{1}$$$ unique whiteboards, $$$y_{1}$$$ non-unique whiteboards once and $$$y_{2}$$$ non-unique whiteboards twice. ($$$0 \le x_{1} \le x$$$, $$$0 \le y_{1} + 2 y_{2} \le y$$$)

Then you have to satisfy this formula: $$$target = \frac{Q}{2} - R - 1 = x_{1} + y_{1} + 2 y_{2}$$$

Since $$$y_{2}$$$ non-unique whiteboards should be at both side, the side of $$$x1$$$ and $$$y1$$$ boards only matters. So there are $$$2^{x_{1} + y_{1}}$$$ cases in state $$$(x_{1}, y_{1}, y_{2})$$$.

Now for $$$y_{2} = [1, 2, 3, \ldots, \frac{target}{2}]$$$, calculate number of possible $$$(x_{1}, y_{1})$$$ pairs, and add it. And you have to apply dirty casework to calculate this fast.

How to prove Monotonicity in D?

here

what if we get a mid such that only mid < l is there for all salary ranges, since that will be an invalid median how do we check that we should go higher or lower?

the ans must large or equal than the median of all salary's li

so you could calculate the value of median of all salary's li ，then start binary search

What's the dp sol of E1?

here

Thank you.

I cannot find a way to prove the correctness of gready algorithm in E2. If we are considering voters with m = i, and we need more voters with m >= i. Suppose that we pick a voters with m = x, so the need of additional picking of this voter before may be not neccessary. I don't know how it can effect to the process of greedy?

let's notice to the inverse iteration of i. If we are considering voters with m=i, we can still use voters with m=x>i because those voters (with m=x>i) were inserted into the multiset before (in the order of iteration) and notice that if they are not chosen to pay money, they will be still in the multiset. HUST student!

In E2, when

`pref[x] + cnt < x`

we can buy additional`x−pref[x]−cnt`

votes or buy all the members of the group`x`

. But in the solution buying all the members of group`x`

is not considered. I don't understand why. Can someone explain please?because the limit mi is 0<=mi<n

so we could leave a person for every mi ，and the person would vote since the vote number of other person is great or equal than mi

If we are considering $$$m_i=x$$$, the number of $$$m_i=x$$$ is $$$s$$$, the number of $$$m_i<x$$$ is $$$p$$$.

First people whose $$$m>x$$$, we have already considered it, denote $$$y=m$$$, obviously $$$y>x$$$ and $$$p+s+cnt\ge y$$$

Consider $$$x$$$, $$$need=x-p-cnt$$$

$$$s-need=s-x+p+cnt=y-x>0$$$ so $$$s>need$$$

Proved.

Problem D has a greedy tag on it. Can anyone please provide a greedy solution?

The greedy are Embedded in binary search https://mirror.codeforces.com/contest/1251/submission/63414228 The function named 'ok' is greedy solution

in problem D, could someone help me find out what will happen if $$$mid$$$ is not in any salarie $$$[l_i, r_i]$$$? Thanks! :)

mid > ri ---> The salary of people must less than median

mid < li ---> The salary of people must large than median

Could someone please explain problem D solution? I am having a hard time getting the editorial.

I can explain my solution which is similar. I'm assuming you know about binary search and sorting.

Let $$$ok(mid)$$$ be a function that returns:

-1 if $$$mid$$$ is impossible to make as a median because it is too low.

0 if $$$mid$$$ is possible to make as a median in some way.

1 if $$$mid$$$ is too big to make as a median (there isn't enough money).

Then we can binary search $$$mid$$$ to find the maximum such that $$$ok(mid)$$$ returns $$$0$$$.

How will the function $$$ok$$$ work? Assume that we will assign the number $$$mid$$$ to some interval. Also, let initially $$$k = s$$$ from the statement (the total money). Subtract $$$mid$$$ from $$$k$$$, since that's the cost to assign the number $$$mid$$$ to the interval that will be the median. We can put the $$$i$$$-th interval $$$[l_i, r_i]$$$ into 1 of 3 groups:

$$$r \lt mid$$$: the number we assign

mustbe smaller than $$$mid$$$ (no other choice). Let the count of these numbers be $$$cntsmall$$$. Also, since we want to use as little money as possible (greedy), might as well assign $$$l_i$$$ to this number. Don't forget to subtract that from $$$k$$$.Those with $$$l \gt mid$$$: the number we assign

mustbe bigger than $$$mid$$$ (no other choice). Let the count of these numbers be $$$cntbig$$$. Do the same stuff as with the previous group.Those with $$$l \le mid \le r$$$: for these numbers, we will choose whether we assign a number less than, equal to, or more than than $$$mid$$$ (whether they will be "before" or "after" $$$mid$$$ in the sorted list of numbers).

Now, if $$$cntsmall \gt \lfloor n/2 \rfloor$$$ or $$$cntbig \gt \lfloor n/2 \rfloor$$$ we can't use $$$mid$$$ as a median because we must always have exactly $$$\lfloor n/2 \rfloor$$$ numbers left and right of the middle element (the median). So return $$$-1$$$ if there are too many bigger numbers ($$$mid$$$ is too small), or $$$1$$$ is there are too many smaller numbers ($$$mid$$$ is too big).

If everything is alright, then we need to assign numbers to the intervals from the 3rd group.

From the first group (smaller numbers), we need to assign $$$\lfloor n/2 \rfloor - cntsmall$$$ numbers (The first $$$cntsmall$$$ numbers were forcefully assigned, now we care about the remaining numbers). Since we want to minimize the cost, we should sort all intervals so that their $$$l$$$ is increasing, then assign $$$l_i$$$ for the first $$$\lfloor n/2 \rfloor - cntsmall$$$ of these numbers (again, by assigning we mean subtracting that number from $$$k$$$, the total money remaining).

From the second group (bigger numbers), we need to assign $$$\lfloor n/2 \rfloor - cntbig$$$ numbers. Since they will come after $$$mid$$$, they need to be bigger or equal to $$$mid$$$. Obviously, it's best to use as little money as possible, so we assign $$$mid$$$ to all of them, so the total cost for this part is just $$$mid * (\lfloor n/2 \rfloor - cntbig)$$$.

Now, all intervals have been assigned a number. If $$$k \geq 0$$$, then we had enough money to do it, so return $$$0$$$. If $$$k \leq 0$$$, then we didn't have enough money, or in other words $$$mid$$$ was too big, so return $$$1$$$.

Too good. Thank you so much for a nice explanation!

Can someone explain E2 solution better? I don't understand the two cases, and also why we iterate from x=n-1 to x=0.

Excuse me for interrupting you.

I think the Tutorial of Problem D may have something wrong.

The ok function has two return values.

`if(need > v.size()) return false;`

It is because var

`mid`

too small.`return sum <= s;`

It is because var

`mid`

too large.So how to keep monotonicity?

May someone help me? Thanks for your kindness.

My thought to problem F:

`unique whiteboard`

means whiteboard has unique height.`non-unique whiteboard`

means whiteboard has non-unique height.Let's use the "generating function".

For each unqiue whiteboard, its generating function is $$$(1+2x)$$$

For each non-unique whiteboard, its generating function is $$$(1+2x+x^2)=(1+x)^2$$$

So, the generating function of the answer is $$$(1+2x)^\text{how many unique whiteboards} \cdot (1+x)^{2\times \text{how many non-unique whiteboards}}$$$

We will get a $$$O(n \log^2 n)$$$ solution if we use FFT/NTT to calculate it directly.

To optimize it, we can pre-calc the coefficients of $$$(1+2x)^\text{how many unique whiteboards}$$$ and $$$(1+x)^{2\times \text{how many non-unique whiteboards}}$$$, by binomial theorem, then use FFT/NTT to merge them. The complexity is $$$O(n \log n)$$$.

Sorry for my poor English...

Could you elaborate more about why the generating function for each unique whiteboard and non unique whiteboard are (1 + 2*x) and (1 + x)^2 respectively? I would really appreciate that.

Is it just me or are the sidebar links to the announcement of tutorial to this round e.g on the page https://mirror.codeforces.com/contest/1251/problem/E1 not appearing?

EDIt: yeah seems to work now

Seem to work for me

In problem F how do we get $$$\binom{2m}{k}$$$ when no white board has unique length? We can chose say x

_{1}boards once and x_{2}boards twice(such that x_{1}+ 2*x_{2}= k) and for each of x_{1}boards we can place it either to the left or right of red board, right?Yes. We are counting the ways to put k non unique whiteboards using 2*m in total. One way to prove this is thinking that you're using x non unique whiteboards on the left side of the red board and k — x of the others on the right side. As you can see the answer is $$$\sum\limits_{i = 0}^{i = k}{{m} \choose {i}} * { {m} \choose {k - i}} = {{2*m} \choose k}$$$. There is an obvious bijective proof of this. However you can proof it by using the Snake Oil method too!.

Super simple idea for E2:

Suppose we choose exactly $$$k$$$ voters to pay. Then the sequence of sorted $$$m$$$ values of the remaining voters must be non-strictly bounded from above by the sequence $$$k,k+1,...,n-1$$$. We can also think of this as being bounded from above by the sequence $$$0,1,...,n-1$$$, with allowed "empty slots" in the sequence.

So, the solution is simply to choose a subset of voters satisfying the bounded property, such that the sum of their $$$p$$$ values is maximum. We can do this by greedily filling slot $$$0$$$ (which only accepts voters with $$$m\leq 0$$$), then filling slot $$$1$$$ (which only accepts voters with $$$m\leq 1$$$), and so on, always choosing the voter with maximum $$$p$$$ value if it exists, or just leaving an empty slot if no voters satisfy the requirement for that slot.

This can be done easily with a priority queue in $$$O(n\log n)$$$.

This leads to the same algorithm as the editorial by the way, just a little clearer to think about in my opinion.

Why in Problem F it is better to use NTT than to use FFT?

I really liked E! Thank you.

E2:

Let's assume that all $$$m_i$$$ are pairwise different.

Once falling into the situation $$$pref_x + cnt < x$$$, we have exactly $$$pref_x + cnt + 1 = x$$$.

That's why we "don't need to" consider about "pay for $$$i$$$ instead of meeting the inequality", because these two choices are the same when dealing with.

The case when some $$$m_i$$$ are equal is a little complicated, but it's not hard to verify that the above assertion is still true.

The solution for C can be extremely simple. It is simply the merged array of the subsequence of evens and the subsequence of odds.

I dont know why this fails, please debug for me!

https://mirror.codeforces.com/contest/1251/submission/189034494

F problem

NTT is not working for large modulos , how to resolve this issue ?