I hope I can reach 800 in this contest.

let's gooo

Fun fact: 418 is a joke http status code, which indicates that this server is a teapot and cannot provide coffee.

Does anyone has any idea on how to solve C?Mine's Binary Search only got 5 out of 11.Waiting for solutions.

E is a weaker version of LeetCode 3625 as the latter doesn't ensure every three points are not colinear.

Problem E is similar to LeetCode 3625. Count Number of Trapezoids II, which appeared in the weekly contest three weeks ago.

The time limit is very bad in E.

How to solve F?

So close yet so far on $$$E$$$ :(

Challenging. :)

How F and G?

Problem G is very similar to https://qoj.ac/problem/12010. It does a great job of popularizing the Myhill–Nerode theorem. However, its downside is that it’s a bit too “brainless,” as contestants can simply copy a template they’ve written before to pass. I only spent ten minutes on it.

edit: Here is another blog about Myhill–Nerode theorem(in Chinese): https://oi-wiki.org/misc/fsm/#myhillnerode-%E5%AE%9A%E7%90%86

E is just Count Number of Trapezoids II, but with the tough edge cases omitted due to the easier constraints.

when will the final ratings update

ahhhhhh only 1 min to submit my AC code of E!!!! my solution

ABC are harder than CF div2 these days...

Screencast with commentary

lol :) lots of white iranian cheater guys ending in some suspicious numbers...

Is there an original question for this competition?（这场比赛有原题吗）

G trash casework solution: (Good means a string which can be reduced to "1")

0000: Only good is "1"

0001: Only good is all '1's

0010: Good if "1" or starts with 10 or (starts with "11" and has at least 3 1s)

0011: Good if starts with '1'

0100: Good if "1" or ends in "01" or (ends in "11" and has at least 3 1s)

0101: Good if ends in '1'

0110: Good if odd number of '1's

0111: Good if at least one '1'

1000: Bad if "0" or "01" or "10" or "11" or "000" or "101" or "111"

1001: Good if even number of '0's

1010: Bad if "0" or "01" or "11"

1011: Bad if "0" or "01111..."

1100: Bad if "0" or "10" or "11"

1101: Bad if "0" or "...111110"

1110: Bad if "0" or "11" or "101"

1111: Only bad is "0"

Did anyone faced similar situations in E?

I searched "trapezoid" in baidu, a Chinese search engine, and the first result was called "不规则四边形", which means "a flat shape with four straight sides, none of which are parallel", and I couldn't understand the example or its explanation, which also didn't explain what a trapezoid was...

I only understood it after seeing its further results called "a flat shape with four straight sides, one pair of opposite sides being parallel and the other pair not parallel". What's more, the online translation websites in China also gave me the first result I mentioned, so many other participants might be puzzled.

I think the E is easier than D.

In problem E I wanted to group edges by their slopes but I did not know how since slope take the form of x / y is there a trick for this ?

Any clue why as to this submission to E gives TLE?

submission

Who can help me solve Problem C?I got 6 WA.I think my logic is correct. First Try Second

How long before the English Editorial?

For question 2 considering the third given test case how can someone think they are only asking for character 't' and not for any other character?

How to solve problem F — We're teapots ?

What i understood till now :

• number of ways to fill coffee and tea in n length array without constraints is

    ways[0] = 1;
    ways[1] = 2; 
    for(int i = 2; i <= n; i++){
        ways[i] = (ways[i-1] + ways[i-2]) % mod2;
    }

• number of ways to fill exactly r coffee in n length such that any two cups has atleast one tea is (n-r+1) C r

can anyone share the soln for E, like how to make sure that u dont take the same of set of 4 pts for a trapezium again, in case of a ||gm.

This is a good solution to problem D by hitoare, can anyone explain it please :

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double

int main() {
    int N;
    string T;
    cin >> N >> T;
    ll odd = 0, even = 1;
    int cnt = 0;
    for (char c : T) {
        if (c == '0') cnt++;
        if (cnt%2 == 0) even++;
        else odd++;
    }

    ll ans = odd*(odd-1)/2+even*(even-1)/2;
    cout << ans << endl;
    return 0;
}

How to do D?

For the people asking for the solution of D:

The XNOR operation is associative, meaning the order of operations doesn't matter. For a string the final character is simply the XNOR sum of all its characters. If you notice carefully, the final sum for a string is '1' if the number of '0's is even, and '0' if the number of '0's is odd. The number of '1's doesn't affect the result.

Now, our task is to calculate the number of indexes $$$[l,r]$$$ such that count of '0's in substring $$$S_l$$$...$$$S_r$$$ is even. A substring from index $$$l$$$ to $$$r$$$ has an even number of '0's if the number of '0's in the prefix up to $$$r$$$ and the number of '0's in the prefix up to $$$l−1$$$ have the same parity.

For for each index $$$i$$$ we will check the parity of the count of '0's till now, and store that value. In the final answer we will choose how many ways we can pick $$$[l,r]$$$ from the odd and even parity respectively which is just $$$C(parityCount,2)$$$ and add them together.

Was anyone able to solve F without BST?

I can see the Japanese Tutorial mentions set or segment tree. But I don't think I completely understand the implementation given there.

Unfortunately, I spent too much time on problem E, since at first sight, I didn't pay too much attention to the condition that [No three points are co-linear].

However, fortunately, for problem F, I have met a similar idea (almost the same) just one week ago, which is Codeforces Round 612 (Div. 2) problem F. LCC.

The idea is that, we transform the dp equation into matrix-multiplication form, and for every query, we use segment tree to handle point-updating, so that the total complexity is O(2^3 n logn).

So, you could search how to solve Codeforces Round 612 (Div. 2) problem F, and after that, I think you can surely solve today's F as well.

Bad time limit for E