Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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;
}
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
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")
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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 - Максимальное произведение наносит ответный удар
Идея: Aris
Разбор
Tutorial is loading...
Решение
#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();
}
}
Идея: myav, MikeMirzayanov
Разбор
Tutorial is loading...
Решение
#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 - Перспективные подстроки (простая версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
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 - Перспективные подстроки (сложная версия)
Идея: MikeMirzayanov
Разбор
Tutorial is loading...
Решение
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/RE verdict on problems from this contest, you can get the smallest possible 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_index and submission_id.
my divide and conquer solution for f
https://codeforces.me/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
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!
Does the solution of F1 take into account the adjacent situation?
How can I solve C. Get an Even String with dp ?
I think there is a mistake in tutorial for problem C. Instead of
used
it should beprev
.Can someone give me the DP solution of number C? I think it will help me get intuition faster to this types of problems.
Can anyone give counter test case for my solution for D here it is:257423322 getting wrong ans on test 2