Codeforces Round #780 (Div. 3) Editorial

#	User	Rating
1	ecnerwala	3648
2	Benq	3580
3	orzdevinwang	3570
4	cnnfls_csy	3569
5	Geothermal	3568
6	tourist	3565
7	maroonrk	3530
8	Radewoosh	3520
9	Um_nik	3481
10	jiangly	3467

#	User	Contrib.
1	maomao90	174
2	awoo	164
2	adamant	164
4	TheScrasse	159
4	nor	159
6	maroonrk	156
7	-is-this-fft-	150
8	SecondThread	147
9	orz	146
10	pajenegod	145

Tutorial

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;
}

1660B - Vlad and Candies

Idea: Vladosiya

Tutorial

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")

1660C - Get an Even String

Idea: MikeMirzayanov

Tutorial

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

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();
    }
}

1660E - Matrix and Shifts

Idea: myav, MikeMirzayanov

Tutorial

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

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

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)

import java.util.*; public class A_Vasya_and_Coins { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); while(t-->0) { int a = sc.nextInt(); int b = sc.nextInt(); int a1 = a*1; int a2 = b*2; if(a==0) System.out.println(1); else { int ans = (a1+a2) + 1; System.out.println(ans); } } } }

Comments (15)

Show archived | Write comment?

variety-jones

2 years ago, # |

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.

→ Reply

__LOOSER__

my divide and conquer solution for f

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

_no_mercy

2 years ago, # ^ |

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

Murot_06

← Rev. 2 →

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

Shermes

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!!!

haochenkang

Most likely this is due to integer overflow with arrays.

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

alsoba

← Rev. 3 →

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:

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.