Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if a[0] + a[1] > a[-1]:
print(-1)
else:
print(1, 2, n)
```

1398B - Substring Removal Game

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (Ne0n25)**

```
#include <bits/stdc++.h>
using namespace std;
#define sz(a) int((a).size())
#define forn(i, n) for (int i = 0; i < int(n); ++i)
void solve() {
string s;
cin >> s;
vector<int> a;
forn(i, sz(s)) if (s[i] == '1') {
int j = i;
while (j + 1 < sz(s) && s[j + 1] == '1')
++j;
a.push_back(j - i + 1);
i = j;
}
sort(a.rbegin(), a.rend());
int ans = 0;
for (int i = 0; i < sz(a); i += 2)
ans += a[i];
cout << ans << endl;
}
int main() {
int T;
cin >> T;
while (T--) solve();
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
for _ in range(int(input())):
n = int(input())
a = input()
d = {0 : 1}
res, s = 0, 0
for i in range(n):
s += int(a[i])
x = s - i - 1
if x not in d:
d[x] = 0
d[x] += 1
res += d[x] - 1
print(res)
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (pikmike)**

```
n = [int(x) for x in input().split()]
a = []
for i in range(3):
a.append([int(x) for x in input().split()])
a[i].sort(reverse=True)
dp = [[[0 for i in range(n[2] + 1)] for j in range(n[1] + 1)] for k in range(n[0] + 1)]
ans = 0
for i in range(n[0] + 1):
for j in range(n[1] + 1):
for k in range(n[2] + 1):
if i < n[0] and j < n[1]:
dp[i + 1][j + 1][k] = max(dp[i + 1][j + 1][k], dp[i][j][k] + a[0][i] * a[1][j])
if i < n[0] and k < n[2]:
dp[i + 1][j][k + 1] = max(dp[i + 1][j][k + 1], dp[i][j][k] + a[0][i] * a[2][k])
if j < n[1] and k < n[2]:
dp[i][j + 1][k + 1] = max(dp[i][j + 1][k + 1], dp[i][j][k] + a[1][j] * a[2][k])
ans = max(ans, dp[i][j][k])
print(ans)
```

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e5) + 9;
int n;
set <int> sDouble;
long long sum[2];
set <int> s[2];
int cntDouble[2];
// 0: 0 -> 1
// 1: 1 -> 0
void upd(int id) {
assert(s[id].size() > 0);
int x = *s[id].rbegin();
if (id == 1) x = *s[id].begin();
bool d = sDouble.count(x);
sum[id] -= x, sum[!id] += x;
s[id].erase(x), s[!id].insert(x);
cntDouble[id] -= d, cntDouble[!id] += d;
}
int main(){
cin >> n;
for (int i = 0; i < n; ++i) {
int tp, x;
cin >> tp >> x;// tp = 1 if double
if (x > 0) {
sum[0] += x;
s[0].insert(x);
cntDouble[0] += tp;
if (tp) sDouble.insert(x);
} else {
x = -x;
int id = 0;
if (s[1].count(x)) id = 1;
else assert(s[0].count(x));
sum[id] -= x;
s[id].erase(x);
cntDouble[id] -= tp;
if (tp) {
assert(sDouble.count(x));
sDouble.erase(x);
}
}
int sumDouble = cntDouble[0] + cntDouble[1];
while (s[1].size() < sumDouble) upd(0);
while (s[1].size() > sumDouble) upd(1);
while (s[1].size() > 0 && s[0].size() > 0 && *s[0].rbegin() > *s[1].begin()) {
upd(0);
upd(1);
}
assert(s[1].size() == sumDouble);
long long res = sum[0] + sum[1] * 2;
if (cntDouble[1] == sumDouble && sumDouble > 0) {
res -= *s[1].begin();
if (s[0].size() > 0) res += *s[0].rbegin();
}
cout << res << endl;
}
return 0;
}
```

Idea: Roms

**Tutorial**

Tutorial is loading...

**Solution (Roms)**

```
#include <bits/stdc++.h>
using namespace std;
const int N = int(1e6) + 99;
const int INF = int(1e9) + 99;
int n;
string s;
vector <int> p[2][N];
int nxt[2][N];
int ptr[2];
char buf[N];
int main(){
cin >> n >> s;
for (int i = n - 1; i >= 0; --i) {
if (s[i] != '0') nxt[0][i] = 1 + nxt[0][i + 1];
if (s[i] != '1') nxt[1][i] = 1 + nxt[1][i + 1];
}
for (int b = 0; b <= 1; ++b) {
int l = 0;
while (l < n) {
if (s[l] == char('0' + b)) {
++l;
continue;
}
int r = l + 1;
while (r < n && s[r] != char('0' + b)) ++r;
for (int len = 1; len <= r - l; ++len)
p[b][len].push_back(l);
l = r;
}
}
for (int len = 1; len <= n; ++len) {
int pos = 0, res = 0;
ptr[0] = ptr[1] = 0;
while (pos < n) {
int npos = INF;
for (int b = 0; b <= 1; ++b) {
if (nxt[b][pos] >= len)
npos = min(npos, pos + len);
while (ptr[b] < p[b][len].size() && pos > p[b][len][ ptr[b] ])
++ptr[b];
if (ptr[b] < p[b][len].size())
npos = min(npos, p[b][len][ ptr[b] ] + len);
}
if (npos != INF)
++res;
pos = npos;
}
cout << res << ' ';
}
cout << endl;
return 0;
}
```

Idea: BledDest

**Tutorial**

Tutorial is loading...

**Solution (BledDest)**

```
#include<bits/stdc++.h>
using namespace std;
#define forn(i, n) for(int i = 0; i < n; i++)
#define sz(a) ((int)(a).size())
const int LOGN = 20;
const int N = (1 << LOGN);
const int K = 200043;
const int M = 1000043;
typedef double ld;
typedef long long li;
const ld PI = acos(-1.0);
struct comp
{
ld x, y;
comp(ld x = .0, ld y = .0) : x(x), y(y) {}
inline comp conj() { return comp(x, -y); }
};
inline comp operator +(const comp &a, const comp &b)
{
return comp(a.x + b.x, a.y + b.y);
}
inline comp operator -(const comp &a, const comp &b)
{
return comp(a.x - b.x, a.y - b.y);
}
inline comp operator *(const comp &a, const comp &b)
{
return comp(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
}
inline comp operator /(const comp &a, const ld &b)
{
return comp(a.x / b, a.y / b);
}
vector<comp> w[LOGN];
vector<int> rv[LOGN];
void precalc()
{
for(int st = 0; st < LOGN; st++)
{
w[st].assign(1 << st, comp());
for(int k = 0; k < (1 << st); k++)
{
double ang = PI / (1 << st) * k;
w[st][k] = comp(cos(ang), sin(ang));
}
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(comp a[N], int n, int ln, bool inv)
{
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++)
{
comp l = a[pos];
comp r = a[pos + len] * (inv ? w[st][pos - k].conj() : w[st][pos - k]);
a[pos] = l + r;
a[pos + len] = l - r;
}
}
}
if(inv) for(int i = 0; i < n; i++)
a[i] = a[i] / n;
}
comp aa[N];
comp bb[N];
comp cc[N];
inline void multiply(comp a[N], int sza, comp b[N], int szb, comp 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] : comp());
for(int i = 0; i < n; i++)
bb[i] = (i < szb ? b[i] : comp());
fft(aa, n, ln, false);
fft(bb, n, ln, false);
for(int i = 0; i < n; i++)
cc[i] = aa[i] * bb[i];
fft(cc, n, ln, true);
szc = n;
for(int i = 0; i < n; i++)
c[i] = cc[i];
}
comp a[N];
comp b[N];
comp c[N];
int used[M];
int dp[M];
int main()
{
precalc();
int n, x, y;
for(int i = 0; i < M; i++)
dp[i] = -1;
scanf("%d %d %d", &n, &x, &y);
vector<int> A(n + 1);
for(int i = 0; i <= n; i++)
scanf("%d", &A[i]);
for(int i = 0; i <= n; i++)
{
a[A[i]] = comp(1.0, 0.0);
b[K - A[i]] = comp(1.0, 0.0);
}
int s = 0;
multiply(a, K + 1, b, K + 1, c, s);
for(int i = K + 1; i < s; i++)
if(c[i].x > 0.5)
used[(i - K + y) * 2] = 1;
for(int i = 1; i < M; i++)
{
if(!used[i]) continue;
for(int j = i; j < M; j += i)
dp[j] = max(dp[j], i);
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
int l;
scanf("%d", &l);
printf("%d ", dp[l]);
}
}
```

How to solve e

Can someone give an example of why greedy solution for D is incorrect?

2 3 1

2 5

3 4 4

6

Greedy will give : (6,5)+(4,2) = 38 But we can take (5,4)+(4,6)+(2,3) = 50

in problem D , .. i assigned color 0, 1, 2 and stored all in a single vector pair(as constraints were low) . sorted in reverse . then used two loops to have pairs whose color is different and not visited earlier ... where i did wrong ???

cin >> r >> g >> b; vector<pair<ll, ll>> f; for(ll i = 0; i < r; ++i) { ll x; cin >> x; f.push_back({x, 0ll}); } for(ll i = 0; i < g; ++i) { ll x; cin >> x; f.push_back({x, 1ll}); } for(ll i = 0; i < b; ++i) { ll x; cin >> x; f.push_back({x, 2ll}); } sort(f.begin(), f.end(), greater<pair<ll, ll>>()); map<pair<ll, ll>, bool> lit; ll fs = f.size(); ll ans = 0; for(ll i = 0; i < fs; ++i) { for(ll j = 0; j < fs; ++j) { if(f[i].se != f[j].se and !lit[f[i]] and !lit[f[j]]) { ans += f[i].fi * f[j].fi; lit[f[i]] = lit[f[j]] = 1; break; } } } cout << ans << endl;

Consider the case

As you can see the optimum answer is 760, but greedy would give 400, issue being greedy only cares about maximum values, and not take into account the number of pairs available of each color.

Take Case

Greedy will give 15*12=180

while maximum will be 15*10+12*10=270

plz can any one help me..

I recently got this question in coding contest i was not able to solve can you please help me out.

ques:-in a TV show game of thrones there are n houses on a battle field and n-1 bidirectional roads connecting houses it is known that you can reach any house from anywhere each house has its own army. A battle is fought between two army(houses) who have a path between their houses one army can take part in one episode of the show the winning and loosing teams can still fight but on the next day. you are the friend of the directors help him to find the minimum episodes he need to air this season and also the number of battles fought on the kth episode . in case of multiple outcomes return output which the maximum number of fights take place after.

input1 = n input2 = k input3 = 2d a[0][i] path to a[1][i]

Sample Tc: n = 4 arr = [[1,1,1],[2,3,4]] k = 2

output=(3,1){3-episodes,1-battle on 2 nd day} in each episode 1 battle {1,2} {1,3} and {1,4} on second day 1 battle.

Sample Tc: n = 4 arr = [[1,1,4],[4,2,3]] k = 2

output=(2,2)

on first day {1,4} on second day {4,3}and{1,2} hence minimum episodes is 3 and on second day 2 battles.

Simplest counterexample:

Greedy will give 3*3=9 but we can do better with 3*2+3*2=12.

Greedy = 16 + 16 = 32

dp = 4*3 + 4*3 + 4*3 + 4*3 = 48

Please tell me in C why are we initializing the mapped value of 0 as 1

Because there is an empty prefix of length 0. So if any other prefix itself will be a good prefix then it should also be counted in answer, so it is paired with an empty prefix of length 0.

Because consider you don't initialise m[0] with 1, then if you come across a subarray of sum = 0 for the first time then you won't consider it as your answer, but indeed it should have been counted in your answer. Hope it helps :)

Can someone please tell me what am I doing wrong in C? Please help!

Here is my code

Your code doesn't take into consideration the subarrays that begin at the index 0. You need to initialize the answer with

`mp[0]`

, not`0`

.Can you please explain a little bit more? I still didn't understand.

Yo have to take a zero value initially ,for the empty string part. for index 0 take value as zero and build a prefix array with 1 indexing on top of that.Otherwise you woould leave that edge case from consideration for example if string starts from the index zero itself.

Finally understood. Thanks a lot for your help.

And consider the case where "...20..."

The prefix sum contains after first step the same value at both positions, after decresing by i two different values. But you would like to match those two positions, because it is a good subarray of size 2.

You need to initialise

`mp[0]`

as 1 , not 0. This is because if the sum of a prefix of the array is 0, you need to consider this prefix. If mp[0] is initialised as 0 you will not add such prefixes to the answer. Also you need to change`++mp[pref[i]-i]`

to`++mp[pref[i]-(i+1)]`

as the array indexing is 0 based.How this code concept of ++mp[pref[i]-(i+1)] is working. What's the intution behind this logic. why we are adding (x)(x-1)/2 to the ans;

actually you are missing the case of one length subarray. Basically you are taking all possible pairs(nc2) when pref[j] -pref[i] = j-i. But this doesn't count the single length case. So just add this, pref[i] = i+1 (0<=i<n), ans++;

If you prefer a video format for solutions, I explain A-E here (timestamps are in the description).

Your video was awesome!!

Awesome Work,galen_colin It's always nice to see better Coders help others who are at earlier stages

Good work.Thanks!

Here is a solution for Problem C using naive O(n2) solution and pragmas. https://codeforces.com/contest/1398/submission/90028294

I used same approach still getting TLE on test case 3, link to my code is given below. Can you please tell me why it's giving TLE for the same logic: https://codeforces.com/contest/1398/submission/90044479

Add the three first lines i've written in my code. It makes the O(n2) solution faster

It worked like a charm. But, how does this make it fast? I don't know about pragmas, can you please tell me how it works?

Pragmas are like compilation flags but per file (kinda), so #pragma("OFast") is like compiling with -O2 / -O3 which optimizes the machine code produced by the compiler. You can read more about pragmas here

Thanks, that really helped...

Hello, tangra can u explain what are you doing, and what are pragmas. I'm a newbie

You can learn more about pragmas here https://codeforces.com/blog/entry/66279

I used the same approach and added pragmas also, but still getting TLE on test 3. Please tell me where i am doing wrong. https://codeforces.com/contest/1398/submission/90298210

how People did 1398E - Two Types of Spells with segment tree?

I think seg tree + binary search in this case could be used to get the answer to: What is the sum of the K greater spell powers? (but I think using two sets is way easier)

I had a solution for F that also uses the harmonic numbers for $$$O(n \log n)$$$, but is otherwise very different.

First, let's get rid of $$$?$$$'s that aren't unclear at all. If a block of $$$?$$$'s is bordered by the same number on both sides, or an end of the string on one side, we will only ever assign either $$$0$$$ or $$$1$$$ to these $$$?$$$. So just do that now.

Now $$$s$$$ consists of alternating blocks of $$$0$$$'s and $$$1$$$'s with some $$$?$$$'s in between. Lets find all these blocks, and for each of them save

Going through these blocks left-to-right, we can greedily create $$$\lfloor\frac{l+m+r}{x}\rfloor$$$ blocks of size $$$x$$$ from a block. If we use some of the $$$r$$$ $$$?$$$'s to the right, we save that and adjust the next blocks $$$l$$$ value accordingly.

To get to $$$O(n \log n)$$$, we consider that only blocks with $$$l + m + r \geq x$$$ are interesting to us. By increasing $$$x$$$ from $$$1$$$ to $$$n$$$, we can discard blocks whenever $$$l + m + r < x$$$. Since every character is counted for at most two blocks ($$$1$$$ block for $$$0$$$ and $$$1$$$, $$$2$$$ for $$$?$$$), there is at most $$$\frac{2n}{x}$$$ blocks for every value of $$$x$$$. Thus, the overall runtime is $$$O(n \log n)$$$.

The tutorial of D saids that we should choose larger sticks, and the code also sorts length in decreasing order. However, sorting length in increasing order also gets AC though I cannot clearly explain it. Does anyone have explanation or proof for this?

You initialized all the values of dp with $$$0$$$. Thus, you allowed it to skip any number of sticks from the prefix of any color. So as long as the suffix of each set is taken and the values are matched in the same sorted order, it gives the same answer.

Thank you for your explanation and now I understand that the matched values are the same in either order.

For people who haven't already seen it in the contest announcement blog and are interested, here's a 3b1b-styled visual editorial for problem C using tmwilliamlin168's code. Link to comment in announcement with details.

In D, since the dp will iterate over all the possible combinations, why does sorting the array matter?

It matters because if for the current dp state we're using some previous dp states, then we have to have already computed those previous dp states

Try this test case:

If you don't sort the arrays, your solution gives 142 and the optimal is 147, this is because it's optimal to take (10,8) and (7,5) and is impossible with the arrays unsorted (those pairs cross each other)

I got it. Since we may be skipping some of the pairs, its better to sort them first so we only pick a pair of larger length. thanks.

I like problem E very much. The same method as solving Dynamic median number problem by two Binary Beap(s) , but not easy to discover for me. Thanks a lot.

.

Problem G — I managed to get by using bitset to get all available sizes of horizontal segments. Run time is 1900ms ... I guess I'm lucky. (Submission 89952340)

FFT is the way to go!

Actually, you can get even faster bitsets which fit comfortably in the time limit. Example: 90376940.

I think this is because the pragmas (in particular -Ofast and -unroll-loops) improve performance significantly on bitsets.

Dammmnnn, the answer of letter C is magnific!

i am not getting problem E :(

can someone tell me the error in my submission 90040255. I used dp , but for test case 7 the function goes into infinite recursion , but I really cannot figure out how. Thank YOu in advanced

plz someone help me with C problem,i couldn't understand it.

I read this solution in the Announcement. But for problem C, You can subtract 1 from every term and the problem reduces to finding subarrays with sum 0 which is pretty standard.

damn!

Hello all,

These are the links of my two submissions for problem D : 1. Accepted Solution 2. Getting runtime error on test case 14

The only difference between the two submissions is in the size of vectors which I am using for storing the lengths of red, green, and blue sticks. In the second submission, the size of vectors exactly matches the number of sticks while in the accepted submission the size of vectors is 1 more than the number of sticks.

In the whole code, I have made sure that I am never referencing any index which is out of bounds for the vectors. But still, I am getting runtime error on test 14 when I am using vectors of the exact size.

It would be really helpful if someone can let me know the reason for this.

Test case : 1 10 100 1000 1001 1002 Question A As per the accepted solution this testcase should fail? I mean it's obvious we've to printf 4,5,6 here but as per the accepted solution 1,2,n is wrong. Idk where i'm going wrong with this idea. Help!

Why does priority queue is not working in 1398D - Colored Rectangles? we need to select two largest values each time and if all have equal then we will select two values from that queue which has larger size. Getting wrong answer on test case 7 My code submission[submission:89996393] Please help .

https://codeforces.com/contest/1398/submission/89996393 link to code

Taking the largest wont work everytime beacause you could take two smaller values which add up greater than the larger one. Try this:

You could take 10 and 11 to get 110. But the optimal solution: 9*11 + 3*10 = 123

I read this solution in the Announcement. But for problem C, You can subtract 1 from every term and the problem reduces to finding subarrays with sum 0 which is pretty standard.

yeah, I also did it that way.

@epsilon_573, I didn't understand. You said, we need to substract 1 from every term, 6 0 0 0 5 => 5 -1 -1 -1 -1 4 now, what?

in problem D , .. i assigned color 0, 1, 2 and stored all in a single vector pair(as constraints were low) . sorted in reverse . then used two loops to have pairs whose color is different and not visited earlier ... where i did wrong ???

cin >> r >> g >> b; vector<pair<ll, ll>> f; for(ll i = 0; i < r; ++i) { ll x; cin >> x; f.push_back({x, 0ll}); } for(ll i = 0; i < g; ++i) { ll x; cin >> x; f.push_back({x, 1ll}); } for(ll i = 0; i < b; ++i) { ll x; cin >> x; f.push_back({x, 2ll}); } sort(f.begin(), f.end(), greater<pair<ll, ll>>()); map<pair<ll, ll>, bool> lit; ll fs = f.size(); ll ans = 0; for(ll i = 0; i < fs; ++i) { for(ll j = 0; j < fs; ++j) { if(f[i].se != f[j].se and !lit[f[i]] and !lit[f[j]]) { ans += f[i].fi * f[j].fi; lit[f[i]] = lit[f[j]] = 1; break; } } } cout << ans << endl;- ~~~~~ Your code here... ~~~~~

am I the only one! who is still suffering for problem E?

Just copied and pasted editorial solution for problem D and got TLE on 8 test case. Is it normal or I am doing smth wrong?

I'm still not able to get C, someone please explain it ( why do we have to intialise like m[0]=1) with an example of why it is needed It would be a great help thanks!

You must have done problem of finding subarray having zero sum. It is same

I am not able to get the solution of 1398C, can anyone please help with C++ program?

Can someone please explain me the last line in the Tutorial of C. I have tried DP and Greedy but both have failed.

$$$pre[j]-pre[i-1]=j-i+1$$$ is the requirement. This can be reduced to $$$pre[j]-pre[i-1]=j-(i-1)$$$ So,simply find all such (prefix sum-index) which have same value(suppose x such $$$pre[i]-i$$$ have a value r) and choose two at a time as $$${C_2}^x$$$ So, it is simply sum of all such value as $$$\sum(x*(x-1))/2$$$.

I tried doing that but that logic fails at certain times. This is the code I made.

c+=((x.second)*(x.second-1))/2; Put the brackets wisely!!

Also mp[0]=1;initially.

For problem D, I have submitted the following code. It gives correct answer on my local machine however it gives WA for second test case. Can someone help me with this!! Submission: https://codeforces.com/contest/1398/submission/90305945

Why there is a greedy tag on the problem D?

Picking numbers from largest to smallest is itself greedy I guess

Can someone explain me how to solve c? Thank you.

Do a search on youtube they have some sood interactive explanations

Is there any implementation of E using segment trees for finding k maximums combining the two different set of elements.

please can someone provide more in detailed description of problem F. i saw from others solution that there are many ways to deals with it. can any one provide the intuition behind their solutions ?

Please can anyone tell why we need to sort the arrays before applying dynamic programming in problem D. Since we are calculating all the states of the DP isn't it unnecessary to sort them? However I get WA on test case 5 without sorting. Thanks in advance.

It's necessary to sort as we need to proceed greedily. product of two numbers a*b is maximum when a is closer b. So, thereby sorting we are ensuring that we proceed on path of maximum value.

What means ld x = .0?

The code of problem E is so short that it really does shock me.

Div. 2 Educational round with FFT task? Are you kidding?

Cause of we don't have Div 1 ER)

My recursive solution for problem D : https://codeforces.com/contest/1398/submission/90893065

A simple solution to c

https://codeforces.com/contest/1398/submission/91039888

just keep track of the states you have seen upto now and if the same state has been seen we add all the subarrays that can be formed with that index as the ending point

Didn't get problem G at all :( It makes me afraid!

problem E:Can anyone tell me what's wrong with this code as this is giving TLE ontest 47. TIA.