I hope I can reach 800 in this contest.

let's gooo

rp++

Noticed that Problem C & D's scores are abnormal, also noticed that Problem E's score is just 50 points higher than D, so I think the contest will be a harder's one than before, and if I'm poor at D, I'll give it up and go to solve the E quickly.

rp+=inf

Please let me solve 3 problems,I am just a pupil;

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.

where Will I get the 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"

Here is my solution for C

I solved like this I can choose any x between b to sigma Ai

Now if b > max_element(A) then I cannot have b object of same flavor so cout<<-1<<'\n'; now case 2 If b<max_element(A) then I have to select at least n bags then as the opponent can choose all the different bags to give you to choose.

Now even if I select n bags I have now n different flavours so I need b-1 flavour of the same type from any of the choosen n flavours . How can I gurantee that I will end having atleast b-1 flavours of same type from rest ??

now each value of array has been decreased by 1

5 1 4 1 8 4 9 5 sort() --? 1 4 4 8 9 look for this test case after first operation my array looks something like this 0 3 3 7 9

now I have to make b-1 that is 4 so I have to take all the values before which is less than 4 in the new array .

So I have to take 0 +3 + 3 = 6

and also I have to take all the elements b-2 times which is at a index after the index of element >=b-1 and also I have to take b-1 time the same element to make it b why so because the opponent can take up to b-2 times any object as we have already used 1 of each in 1st operation so he cannot use b-1 times so he has to use b-2 times in order to maximize the x

.

Let the index of our use be i (the first number which is greater than equal to b-1)

then I need in short extra of

pref_sum[i-1]+(b-2)*(n-1-i)+(b-1) .

so In short I need

n+pref_sum[i-1]+(b-2)*(n-1-i)+(b-1) .where i>0 else i-1<0 so remove this

but If I dont want to change my array I can simply do

n+pref_sum[i-1]-i+(b-2)*(n-1-i)+(b-1).

why so ??

Figure it out youll understand better.

#include <bits/stdc++.h>
using namespace std;
#define int long long 
void solve() {
   int n; cin>>n; 
   int q; cin>>q; 
	vector<int> v(n,0); 
	for(auto &i:v) cin>>i;
	sort(v.begin(),v.end()); 
	vector<int> pref_sum(n,0); 
	pref_sum[0]=v[0]; 
	for(int i=1; i<n; i++){
		pref_sum[i]=pref_sum[i-1]+v[i]; 
	} 
	while(q--){
	int sum=0;
	int b; cin>>b; 
	if(b>v.back()) cout<<-1<<'\n'; 
	else{ 
	auto it=lower_bound(v.begin(),v.end(),b-1)-v.begin(); 
		sum+=(n+(n-1-it)*(b-2)+(b-1)+(it>0? pref_sum[it-1]-it:0)); 
		cout<<sum<<'\n'; 
	}
	}
}
signed  main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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?

800+. Alhamdulliah

How do ya'll deal with debugging when you can't see test cases? Even after the contest I couldn't figure out how (if possible at all) to view them. I'm fairly new to AtCoder so I could be missing something.

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.

why this approach for D not works? first count all contiguous ones as they always lead to 1 so add all substring of that n*(n+1)/2 second count all contiguous zero which are even , they always lead to so add for 6 even zeros we have to add (6-1)+(6-3)+(6-5) we can make this AP series at last we have to add those transitions where one also present and then next we have even zeroes like 111000011 so this whole also results to 1 , calculation of all substring may be complex for this case ,

any other appraoch

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.

thanks!

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.

When is the editorial getting published.

Hope it will be published before next contest.

Bad time limit for E