Sofa~ Enjoy the round.(By the way, kitty lemon is so cuuute>w<).

sjfyyds!

sjfnb！！！

sjfnb!

Chinese statement！Wow

So is this the first CF round contains Chinese statement? TBH in these recent days I'm also thinking about if it will be allowed to offer Chinese statement in my next round (if I will finish my problemset lol), and now surprisingly find your new round does it earlier.

SJF YYDS！！！

I want to click on “Vote：I like it”，but I click on “Vote：I do not like it” by mistak。How can I change it？ qvq

Can't wait any more, let's enjoy sjf's round.

So, what's the interesting chinese statements? Something like "Super Idol的笑容 都没你的甜 八月正午的阳光 都没你耀眼 热爱 105 °C的你 滴滴清纯的蒸馏水"?

A cat round. Excited to read the problem statements of the round.

〜(￣▽￣〜)

I see meow, I upvote.

I hope this round came easier than the last one

≧ω≦ it is a nice cat .. I wish the round be good like the latest one ..

I'll have a cat sooner or later! QAQ

sjfnb！！！！ I hope everyone can have fun solving our interesting problems ~ o(*￣︶￣*)o

sjf nb

meow!

to tell the truth the problems we discarded can make up another contest

Hope you can solve our interesting problems and gain high rating!

sjfnb!!!

FreshP_0325 orz

As the fourth naughty cat no one talks about I am absolutely hurt. iN oRdEr To compensate for tHiS mIsTaKe I mUsT bE gIvEn +200

When I first registered for this round, my rating was below 1900. Now, I've registered again for the same round but in Div. 1 category. Which category am I supposed to participate in now?

Can I make submissions in both categories during the contest ( ಠ◡ಠ )?

sjfnb!

I hope that i will be a pupil

Я надеюсь что я стану учеником

Good luck for everyone!!!

Всем удачи!!!

I am curious about your favorite problem. As your favorite problem has got rejected, you can share it in chat

Well, Chinese round, help me to be blue lol...

So when are you eating your cats?

my first div1 contest :D

any one pls tell that what does it mean (750+1000) in scoring distribution Div.2: 500 — (750 + 1000) — 1250 — 2000 — 2000 — 2750 does it mean that 2nd question will be off 1750 orr it will of 750 or 1000 i'm bit confussed

sjf nb!!!

The cats look really tired after a long day of preparing the round.

what actually that 750+1000 mean (in div 2 scoring distribution)

Permutationforces again

Problem C(div1) was really funny pretending to be a non-permutation problem.

server is tooo much fast guys :D

The memory in problem C is very annoying

Dang, that problem B though :P

I think it should be swapped with C (looking at point distribtuion)?

Ugh! Headache from that B2 I'm done

Solved 4 again including E . I wonder what would they say now . All they wanted was to bully me and downplay me

Context

solved Problem C but didn't solve Problem B2 :(

Finally solved a FFT problem during contest. POG

Edit: I just overcomplicated Div 1D like a bot. Ignore this comment

Rubbish round

C was easier than B2 :/

Hints for Div2E/Div1C

Solve a simpler problem first. You are given $$$k$$$ boxes numbered from 1 to $$$k$$$. Assign unique values to them from the set $$$1, 2, 3, \dots n$$$ such that $$$\Sigma_{i = 1}^{k} |val[i] - val[i + 1]|$$$ is maximized.

Answer: 2*(Suffix sum of k//2 elements - prefix sum of k//2 elements).

Now, get rid of the 2 arrays to construct an array c where c[i] = index of b[i] in a[i].

Array $$$C$$$ is a permutation, and will have several disjoint cycles. The answer for each cycle can be computed from the formula above. In the end, we need to assign a sign, $$$+, -, 0$$$ to the array $$$[1, 2, \dots n]$$$. Each disjoint cycle would contribute cc_size/2 to the answer, for both the suffix and prefix.

What was B2? Can someone provide me some testcases?

Bruh, solution to E is somewhat tedious and straightforward, but requires you to solve "sum up the total area of rectangles in a rectangle" queries. I spent the whole contest implementing it. Seems to pass pretests, but since it is the only problem I submitted, maybe I shouldn't have submit it at all when I was done...

What's the solution for B2, is it something to do with dp?

.

I want to know what's the intended solution for Div2C, cuz I just wasted 30 mins optimizing my original solution.

anyone pls tell me what was the intuition and how you've solved div2 2 (b harder version )

Permutation Forces

Div 2 is too unbalanced

Wow, I made the last "pretests passed" submission in the whole Div.1 round, at 01:59:46.

My heart was beating soooo fast!

For me Div2 B2 >>> Div2 E

F = this + this + this.

C was easier than B2 :/

Would love to know the solution of B2.

Solved B1 literally by "guessing" with no complete proof, feeling uncomfortable. Feel B2 could be solved by guessing also, but have no time to write it down. This is a bad experience. Really want to see clean solutions for B1 and B2 with PROOFs in the editorial.

Ordered set giving TLE in div2 C sed life :-(

desperately waiting for the solution to B2

My submission to pC

The time complexity should be O(n^2),but I got TLE. Can somebody help me?

The funniest thing is how div1D was named "and permutations". Because the rest isn't :^)

1D is ezer than 1B and 1C !!!

Had to rewrite my solution to D2C from python to c++ because O(n*n*logn) with Fenwick wouldn't pass otherwise /:

Failed to solve B

I think div2 C is easier than div2 B2. div2 B2 caused me to have no time to solve div2 D......

I should have expected that it will be a trash contest from the blog vibes.

I think A is the hardest among first 5 problems in div 1.

A is similar to 1400D - Zigzags

How to write Tokitsukaze and Meeting without much pain? I had seen there several complex loops, and every time I tried to write them, I had gotten confusion.

My solution for C with ordered set in C++ with O(n^2*logn) complexity was failing. Then i tried solution using 2 arrays in which space complexity was o(n^2) as well as the time complexity. It was giving MLE on test case 5. After optimizing the space for one of the arrays to O(N) the solution passed. I noticed someone else solution after the contest who had also used 2 arrays with o(n^2) complexity but used int than long long as I had done. Do data types affect space so much that a whole test case failed because of it?

I have a fun solution for DIV2 B1, pretty much different from other people's solutions :

Is B2 DP?

B1 and B2 can be solved with DP

states => i, parity of 0, parity of 1, last character parity

transitions try to make previous consecutive frequency even for any of the two elements at every recursion or just pass it with default values als note that at every point in recursion maintain either p1 == 1 or p0 == 1.

Solution

#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
#define pob pop_back
#define b back
#define cout(x) cout << x << endl
#define lb long double
#define soa(arr, n) sort(arr,arr+n)
#define inputVector(v, n) for(ll i = 0; i < n; i++) cin >> v[i]
#define sov(v) sort(v.begin(), v.end())
#define rev(v) reverse(v.begin(), v.end())
#define pl pair<ll, ll>
#define all(a)    a.begin(), a.end()
#define vpp vector<pair<ll, ll>>
#define fastIo ios_base::sync_with_stdio(false), cin.tie(0)
#define endl '\n'
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<pair<ll,ll>, null_type,less<pair<ll,ll>>, rb_tree_tag,tree_order_statistics_node_update>
#define No cout << "NO\n"; return;
#define Yes cout << "Yes\n"; return;
typedef long long int  ll;
ll P = 1e9 + 7;
pair<ll,ll> dp[200001][2][2][2];

pair<ll,ll> findOps(ll i, string &s, ll p0, ll p1, ll last) {
    
    if(i == s.length()) {
        if(p0 &1 || p1 & 1) return {1e8, 1e8};
        else return {0, 1};
    }
    if(dp[i][p0][p1][last].first!= -1) return dp[i][p0][p1][last];
    pair<ll,ll> ans = {1e8, 1e8};
    if(p0) {
        if(s[i] == '0') {
            ans = min(ans, findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0'));
        } else {
            s[i] = '0';
            pair<ll,ll> minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0');
            minis.first += 1;
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis); 
            s[i] = '1';
        }
        
    } else if(p1){
        if(s[i] == '1') {
            ans = min(ans, findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0'));
        } else {
            s[i] = '1';
            pair<ll,ll> minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0');
            minis.first += 1;
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis); 
            s[i] = '0';
        }
        
    } else {
        // chance of toggling.
        if(s[i] == '0') {
            pair<ll,ll> minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0');
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis);
            s[i] = '1';
            minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0');
            minis.first += 1;
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis);
            s[i] = '0';
        } else {
            pair<ll,ll> minis = findOps(i + 1, s, p0, p1 ^ 1, s[i] - '0');
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis);
            s[i] = '0';
            minis = findOps(i + 1, s, p0 ^ 1, p1, s[i] - '0');
            minis.first += 1;
            minis.second += i > 0 && s[i] != s[i - 1];
            ans = min(ans, minis);
            s[i] = '1';
        }
    }
    return dp[i][p0][p1][last] = ans;
}
void solve() {
    ll n;
    cin >> n;
    string s;
    cin >> s;
    
    for(ll i = 0; i < n; i ++) {
        for(ll j = 0; j < 2; j ++) {
            for(ll k = 0; k < 2; k ++) {
                for(int l = 0; l < 2; l ++)
                    dp[i][j][k][l] = {-1, -1};
            }   
        }
    }
    pair<ll, ll> minis = findOps(0, s, 0, 0, 0);
    cout <<  minis.first << " " << minis.second <<  endl;
}

 
 int main() {
    ll t=1,i=1, n;
    fastIo;
    cin >> t;
    while(t--) {
       // cout << "Case #"<<i<<": ";
       solve();
       i ++;
    }
    return 0;
}

Fixed my bug on E 10 minutes after the contest, by just changing two chars. TaT

Seriously, I've never seen a problem more stupid than Div.1 E.

Man E is super easy. I think B1/B2 is harder than E. Why do we need to bring a super easy question like this to E?

My solution for $$$Div2$$$ $$$B$$$:

Easy part:

First observe that any valid solution consists of even ones, even zeros, even ones, ... So, any $$$prefix_i$$$ of odd length with $$$a[i]\neq a[i+1]$$$ will require at least one operation, the lower bound on number of operations is the count of such prefixes.

The mentioned lower bound is achievable, as such odd prefixes appear in the form of, e.g., even prefix followed by odd ones (odd prefix), even zeros (odd prefix), even ones(odd prefix), odd zeros (even prefix). So just changing the last value in each odd prefix will make all the prefixes where the values change to be even.

Hard part:

The objective here is to choose the values to change in a way to increase the connectivity of segments with the same value. From the previous proof, observe that any even $$$prefix_i$$$ ending with $$$2$$$ zeros or $$$2$$$ ones implies that in the final solution $$$prefix_i$$$ should end with the same value, otherwise more operations will be done.

So, we can greedily search for the next even prefix ending with $$$2$$$ zeros or $$$2$$$ ones and make the whole segment have the same value (starting from after the previous even prefix). When we cannot find any more such prefixes (reached the end of array), if the current segment we are working on starts from $$$i\neq 0$$$, we can choose $$$a[i-1]$$$ and use it in the whole segment, otherwise we can just choose any value.

Submission

That balance is 10 out of 10 basically, but you've tried)

Why C does not pass with Ordered_Set but applying Fenwick Tree it does?

I think such things should not happen in future either both should or both should not.

This round let me feel that I sould give up

Thanks to the round authors for problem E, I liked it very very much. Unfortunately didn't have to implement it during the contest due to sucking too much at combinatorics >_>

for B1 just look at s[i] and s[i+1] if they are different then we have no choice other than to change any one of them.

for B2 just work in two length contiguious substrings if s[i] and s[i+1] are different then simply look at s[i-1] and make these equal. if s[0] and s[1] are different then once choose both of them 0,0 and find the values using above procedure, similarly for 1,1 and take the minimum of these two.

https://codeforces.com/contest/1678/standings/friends/true#

Waiting for usual YT editorials for last div2 problems :)

WTF!!

link this problem is the same as problem C I replaced every < by == and got accepted

The pretests are so powerful that the issue occurred Runtime error on test 4 LOL

Problem C O(N*N*log) AC : 156339292

how is can fit when N up to 5000?

Guys who created this round, what do you think about Winnie the Pooh?

As a Chinese,exicted for Chinese statement!

It seems that I am the only person who FST on Div.1 B. :<

Здравсвтуйте, вы мне задачу C из Codeforces Round #789(Div. 2) засчитали как списанное, хотя если посмотреть в группе в которую вы меня занесли, мой код не имеет схожести с другими.

Мое решение : https://codeforces.com/contest/1678/submission/156348355

И несколько решений от пользователей из моей группы: https://codeforces.com/contest/1678/submission/156340778 https://codeforces.com/contest/1678/submission/156342693 https://codeforces.com/contest/1678/submission/156343315 https://codeforces.com/contest/1678/submission/156343329 https://codeforces.com/contest/1678/submission/156348676 https://codeforces.com/contest/1678/submission/156348782 https://codeforces.com/contest/1678/submission/156348723

Achievement unlocked: "Perfectly Balanced": obtain 0 delta

A good contest!

tourist научи прогать пж. Как выиграть IOI? Плиз туториал, заплачу 1р.

Thank you for the Chinese tutorial.