Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
int main() {
int t;
cin >> t;
for (int it = 0; it < t; ++it) {
int a, b;
cin >> a >> b;
cout << (a == 0 ? 1 : a + 2 * b + 1) << '\n';
}
return 0;
}
```

Idea: Vladosiya

**Tutorial**

Tutorial is loading...

**Solution**

```
t = int(input())
for _ in range(t):
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
if n == 1:
if a[0] > 1:
print("NO")
else:
print("YES")
continue
if a[-2] + 1 < a[-1]:
print("NO")
else:
print("YES")
```

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include<bits/stdc++.h>
using namespace std;
int sz = 26;
void solve(){
string s;
cin >> s;
int m = 0, n = (int)s.size();
vector<bool>prev(sz, false);
for(auto &i : s){
if(prev[i - 'a']){
m += 2;
for(int j = 0; j < sz; j++) prev[j] = false;
}
else prev[i - 'a'] = true;
}
cout << n - m << endl;
}
int main(){
int t;
cin >> t;
while (t--){
solve();
}
}
```

1660D - Maximum Product Strikes Back

Idea: Aris

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
void solve() {
int n; cin >> n;
vector<int> a(n);
forn(i, n)
cin >> a[i];
int ans = 0;
int ap = n, as = 0;
for(int i = 0, l = -1; i <= n; i++) {
if (i == n || a[i] == 0) {
int cnt = 0;
bool neg = false;
int left = -1, right = -1;
int cl = 0, cr = 0;
for (int j = l+1; j < i; j++) {
neg ^= a[j] < 0;
if (a[j] < 0) {
right = j;
cr = 0;
}
if (abs(a[j]) == 2) {
cnt++, cr++;
if (left == -1) cl++;
}
if (a[j] < 0 && left == -1) {
left = j;
}
}
if (neg) {
if (cnt - cl > cnt - cr) {
right = i;
cnt -= cl;
} else {
left = l;
cnt -= cr;
}
} else {
left = l, right = i;
}
if (ans < cnt) {
ans = cnt;
ap = left + 1, as = n - right;
}
l = i;
}
}
cout << ap << ' ' << as << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
```

Idea: myav, MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
#include <bits/stdc++.h>
using namespace std;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) (int)v.size()
#define all(v) v.begin(),v.end()
#define eb emplace_back
const int INF = INT_MAX >> 1;
void solve() {
int n; cin >> n;
int cnt1 = 0;
vector<int> cnt (n, 0);
for (int i = 0; i < n; i++) {
string s; cin >> s;
for (int j = 0, k = (n - i) % n; j < n; j++, k = (k + 1 == n ? 0 : k + 1)) if (s[j] == '1') {
cnt1++;
cnt[k]++;
}
}
int ans = INF;
for (int i = 0; i < sz(cnt); i++) {
ans = min(ans, cnt1 - cnt[i] + (n - cnt[i]));
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
forn(tt, t) {
solve();
}
}
```

1660F1 - Promising String (easy version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
tst = int(input())
for _ in range(tst):
n = int(input())
s = input()
b = [0 for i in range(n+1)]
bal = n
b[0] = bal
ans = 0
for i in range(1,n+1):
if s[i-1] == '+':
bal += 1
else:
bal -= 1
b[i] = bal
for j in range(i):
if b[j] >= b[i] and (b[j] - b[i]) % 3 == 0:
ans += 1
print(ans)
```

1660F2 - Promising String (hard version)

Idea: MikeMirzayanov

**Tutorial**

Tutorial is loading...

**Solution**

```
tst = int(input())
for _ in range(tst):
n = int(input())
s = input()
f = [0 for i in range(3)]
cur_bal = n
cnt_bal = [0 for i in range(2 * n + 1)]
cnt_bal[cur_bal] += 1
f[cur_bal % 3] += 1
ans = 0
for i in range(n):
#print(f)
#print(cur_bal, ans)
new_bal = cur_bal
if s[i] == '-':
new_bal -= 1
f[new_bal % 3] += cnt_bal[new_bal]
ans += f[new_bal % 3]
cnt_bal[new_bal] += 1
f[new_bal % 3] += 1
else:
f[new_bal % 3] -= cnt_bal[new_bal]
new_bal += 1
ans += f[new_bal % 3]
cnt_bal[new_bal] += 1
f[new_bal % 3] += 1
cur_bal = new_bal
print(ans)
```

If you are/were getting a

WA/REverdict on problems from this contest, you can get thesmallestpossible counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints.I've also added a new feature to view progress of your judgement in

near real-time. (For example, the current state of your ticket, how many inputs were evaluated, etc).If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the

contest_id,problem_indexandsubmission_id.my divide and conquer solution for f

https://codeforces.com/contest/1660/submission/152497191

Can you explain ur solution

in problem I made simple observation that whenever number of negative is greater

let say r = number of negative in subarray — number of pos in subarray

if r >0 and r%3 == 0 then subarray will be promissing

I used divide and conquer to calculate those subarray

There is a solution in the f2 order_set or fenw_tree.This is awesome

thanks for explanations

In B Can someone please explain why 6 1 1 1 1 1 5 will give no in this case we eat candies like index 6, index 5 , index 6, index 4, index 6, index 3 , index 6 , index 2 , index 6 ,index 1.

Give attention to this line, "Vlad decided to eat exactly one candy every time, choosing any of the candies of a type that is currently the most frequent (if there are several such types, he can choose any of them)." In your case, the most frequent one is 5 and when he eats one candy, the most frequent type is again the last one because its count is 4 and is highest. And Vlad also don't want to eat same candies in a row. That is why this case will give a NO.

Can anyone please point out for me the difference between these two submissions:

152864441(I used vector and got WA)

152864364 (I used array and got AC)

Thanks in advance!!!

Most likely this is due to integer overflow with arrays.

Can you elaborate more for me ? I'm still confused. Thank you very much!

Look at expression in line 21:

if((n == 1 && vec[0] > 1) || (vec[n — 1] — vec[n — 2] > 1))

The condition behind the OR doesn't check for vector size, so for n == 1, then you are evaluating this: (vec[0] — vec[-1] > 1)

Imagine this input:

1

1

1

Then:

(n == 1 && vec[0] > 1) || (vec[0] — vec[-1] > 1)

(1 == 1 && 1 > 1) || (1 — vec[-1] > 1)

(true && false) || (1 — vec[-1] > 1)

false || (1 — ?? > 1)

So basically you are accessing vec[-1]. Depending on the value in that "illegal" memory position, it may be true or false. Same happens for arr[-1], but you just go lucky there with the memory value there at the time of the submit.

Wow, now I get that! Thanks very much!

Can someone check my I get a memory limit to exceed the error in the c problem https://codeforces.com/contest/1660/submission/153739220

Does the solution of F1 take into account the adjacent situation?

How can I solve C. Get an Even String with dp ?

To solve 1660C with DP we should start by finding the recursive solution: for each i in the strings there are 2 options: I either remove the current element, or I remove elements until I reach the next occurrence of this character in the string (if there is any). We recur on both options and take the minimum result.

The naive approach to finding out how many elements are until current element and next occurrence of character is a simple linear scan. We can speed it up by a LOT by first scanning the string and then storing the positions of the characters in the string in a

`vector<set<int>> pos(26)`

, where index stores the character type, and the elements in the set store the indexes where this element occurs.After that simple (but most likely necessary) optimization, we can notice one thing: if I happen to be in the same index again, the best solution is going to be the same! So I simply store it in a memo vector.

This is my submission for additional clarity: 163585297

It's gonna be pretty simple translating it to a simple iterative bottom-up approach! This exercise is left for you.

I think there is a mistake in tutorial for problem C. Instead of

`used`

it should be`prev`

.187127635 Problem D: Can someone explains me, Why i am getting WA with this??

Take a look at Ticket 16616 from

CF Stressfor a counter example.