Shhh, I’m desperate for a rated contest

testers are so cool!

if FynjyBath = tester, round = bad

Nice avatar

What will be the distribution of points?

i can say problems are very hard LOL :)

It can't be delayed since it has to be held during Moscow Olympiad for Young Students.

Don't cross your fingers, it will be difficult for you to type during contest. (◠‿◠)

And Chinese like me

I'm also Vietnamese!!!

same. cant wait to demote to newbie bro

I don't understand why you upvote this. Firstly,if you notice that a problem is similar with another one in the past,keep it for yourself and don't spoil the contest. Second of all,saying that you copied your code from a solution source is against the values imposed by codeforces(ig).

I used binary search for A and it worked. Have no idea how to solve it normally though...

I didn't prove it, but I solved it in a few minutes by greedily going max_sum, max_sum-1, max_sum-2... min_sum, min_sum+1, min_sum+2.. max_sum-1. I was surprised it worked.

Note the length of the array is always (x-y)*2 .

if x>y ->

x, x-1, x-2, ... , y+1, y, y+1, ... , x-1

there is only one higher and lower point and always difference 1

Just start from max sum, go down to min sum and then go up to max sum -1. The reason it works is that, only the max/min sum will be local maxima/minima so, all others are unimportant.

n = (x — y) * 2. That's because local minimum and local maximum are alternating(x1, y1, x2, y2, x3, y3, ...(that's quite easy to prove)) which means that the quantities of minimums and maximums are equal(that's unimportant to the solution, it's just an interesting fact). So with this information we can easily count n. Lets look at slice [x1...y1..x2). We can easily count the quantity of all elements in the slice [x1...y1...x2): n = x1 — y1 + x2 — y1. Then add n to answer and do such thing till you return to your first slice. We can see that the final result will be ans = 2 * x1 + 2 * x2 + ... + 2 * xm — 2 * y1 — 2 * y2 — ... — 2 * ym = 2 * (x1 + .. xm — y1 — ... — ym) = 2 * (x — y). Finally, we can easily create an appropriate array with only 1 maximum and minimum which are equal x and y.

Idk if it will pass or not but anyways you should try this optimization: Optimization with Hilbert curve

• I've tried F with Mo's algo + multisets, TLE4
• My multiset solution had high constant factor(10 operations per index) so I decided to come up with a segtree solution(2 calls to update per index) but it still TLEs.
• I tried with some different block sizes too like N/logN, N/sqrt(q) etc.
• Also added that zig zag sort. They all TLE lol.
• Hilbert curve optimization works better with small q, so it's not going to change anything

last problem is a copy of 765F - Souvenirs

agreed i am surprised that the answer for the case when x — y = 1 is just an array of {x , y} :((

statement so unclear and stupid

Why Genshin out of nowhere...

I mistyped min to max when initializing prefix min of positions. However it also squeezed into the first 5 pretests:(

Segment Tree seems pretty overkill for D. My strategy was to count the #of subsegments such that they share a common MEX by iterating over the MEX value and using 2 pointers to handle everything. I got it to pass the example cases too. Wish I could have submitted it :(

Edit: It got accepted. Here's the code if anyone's curious: 193333734

One tip is to write a brute force solution for D and compare your submission with the brute force solution.

// time-limit: 2000
// problem-url: https://codeforces.com/contest/1793/problem/D
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
#define int int64_t
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define txtio(s) freopen((string(s)+string(".in")).c_str(),"r",stdin);freopen((string(s)+string(".out")).c_str(),"w",stdout);
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define sqr(a) (a)*(a)
#define endl '\n'
#define I insert
const int mod=1000000007;
int binpow(int a, int b) {
	int res=1;
	while (b>0) {
		if (b&1)
			res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
void solve(int wasd){
	//cout<<"Case "<<wasd<<" :";
	int n;
	cin>>n;
	vector<int> p(n,0),q(n,0);
	for(int i=0; i<n; i++){
		int tmp;
		cin>>tmp;
		p[tmp-1]=i;
	}
	for(int i=0; i<n; i++){
		int tmp;
		cin>>tmp;
		q[tmp-1]=i;
	}
	int ans=(abs(p[0]-q[0])-1)*(abs(p[0]-q[0])-2)/2+min(p[0],q[0])*(min(p[0],q[0])-1)/2+(n-max(p[0],q[0])-1)*(n-2-max(p[0],q[0]))/2+n-max(p[0],q[0])-1+min(p[0],q[0])+abs(p[0]-q[0])-1;
	int curl=min(p[0],q[0]),curr=max(p[0],q[0]);
	for(int i=1; i<n; i++){
		if(curl==0&&curr==n-1){
			break;
		}
		if((p[i]>=curl&&p[i]<=curr)||(q[i]>=curl&&q[i]<=curr)){
			curl=min(curl,min(p[i],q[i]));curr=max(curr,max(p[i],q[i]));
			continue;
		}
		if(min(p[i],q[i])>curr){
			ans+=(curl+1)*(min(p[i],q[i])-curr);
		}
		else if(max(p[i],q[i])<curl){
			ans+=(curl-max(p[i],q[i]))*(n-curr);
		}
		else ans+=(max(p[i],q[i])-curr)*(curl-min(p[i],q[i]));
		curl=min(curl,min(p[i],q[i]));curr=max(curr,max(p[i],q[i]));
	}
	ans++;//solution where all of the array is included
	cout<<ans<<endl;
}
int32_t main(){
	fastio;
	int t=1;
	//cin>>t;
	for(int i=0; i<t; i++) solve(i);
}

note that i used my template here and used cpbooster to parse and submit the code so there are a lot of unnecessary lines. you can assume that solution starts from void solve()

did u find what is pretest 6? mine is also failing

just go to https://codeforces.com/problemset/problem/765/F and read editorial

accepted :)

I used two pointers -- while(l < r && flag), flag = false, if a[l] or a[r] = min or max, increment l or decrement r, increment min or decrement max, and set flag to true. Then output l and r as the answer,

I did the exact same thing, even the same variable names.

But it feels like there is a better sol

As i understand you try to find l and r for every element in array, so it is O(n^2). There is no requirement that length of subsequence should be minimal, so we could just check that left and right elements aren't current minimal or maximum

I loved problem C! My solution is even simpler. I solved with also two pointers, but instead of the segment tree, I used 2 RMQs. Starting from the first and last element, check whether the range is good or not with RMQ; if it is good, print and stop. Else, update left and right by equality conditions, respectively. The segment tree method is another solution, but I think RMQ is even shorter and simpler. Btw used the sparse table method, so it gives min and max in O(1).

I have also overkilled! same idea and used 3 sparse table :)

no it isn't

solution exist only for n<1e5 (given) so above case will not have any solution

First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circle

Last line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5

I would swap A and D around, but I agree with this lol. Wasted a ridiculous amount of time on B

what was your idea for D that you put is so low on difficulty?

my submission

basic idea is with 3 conditions

price on first day is a and price on second day is b

then

if (a < b) ... you should alway buy on first day

if (a > b BUT you can save with a discount ) then you should get discounted items on first day and remaining on second day

else buy everything on second day

First line of the question For his birthday recently Fedya was given an array a of n integers arranged in a circle

Last line of the question It is guaranteed that the sum of n over all test cases does not exceed 2⋅10^5

Exactly , I was wondering how would i even print such a huge sequence even if i get one :/

Exactly, It had took my lot of time for optimizing number of operations, and I checked constraints on x and y more than 5 times, Also problem statement of A is not well written, it could be written in 2-3 lines. Even F is taken according to me.

Agreed, perhaps the worst Div. 2 B of all time, or at least in recent memory.

I totally agree with this, just this line alone $$$-10^{9} \le y < x \le 10^{9}$$$ can mislead people to think that $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ is a valid input, even though the next line says that the sum of $$$n \le 2 * 10^{-5}$$$

And as such leaving their head scratching that there is a better answer than $$$2*(x-y)$$$ for $$$x = 10^{9}$$$ and $$$y = 10^{-9}$$$ that can fit into the given constraint on $$$n$$$, which can possibly cause them to get stuck forever

yaa !did u solved it ? i thought it's easy but took lot of efforts but still didn't got accepeted '~'

can you explain why my code is wrong?

void solve(){
    ll a,b;
    cin>>a>>b;
    ll n,m;
    cin>>n>>m;
    
    if(n <= m){
        cout<<min(a,b)*n<<endl;
        return;
    }
    ll ans;
    ans = min(n*a,n*b);
    
    ll maxiBeta = n / (m + 1);
    ans = m*maxiBeta*a + (n-(m+1)*maxiBeta)*min(a,b);
    cout<<ans<<endl;
}

Can you prove B?

yaa in first attempt in A i did exactly what u r saying but didn't get accepted so started thinking something else

Great Explanations !! I managed to solve C using 2-Pointers as following: " Don't forget to move the pointer, and if we got "l==r" then -1 "

• if "l" or "r" is pointing at min then "new_min = min+1"

• if "l" or "r" is pointing at max then "new_max = max-1"

• if none of above then print (l, r)

found = False
    l, r = 0, N — 1
    MN, MX = 1, N
    while l < r:
        if A[l] == MN:
            MN += 1
            l += 1
        elif A[l] == MX:
            MX -= 1
            l += 1
        elif A[r] == MN:
            MN += 1
            r -= 1
        elif A[r] == MX:
            MX -= 1
            r -= 1
        else:
            found = True
            break
    if found:
        print(l + 1, r + 1)
    else:
        print(-1)

In A isn't it possible that if we buy x number of the potatoes out of n from a and remaining from b so now we vary this x How can we claim that it is best to divide all n in m+1 groups for a and remaining for b Can't there be any intermediate x out n for which we find the best possible minimum I tried this using binary search but W/A

Am i missing something? : Yes

consecutive numbers should have a difference of 1 :)

Check this case:

4
2 3 1 4
2 3 1 4

answer = 10

Check this case:

6

4 1 2 3 5 6

5 6 4 1 2 3

answer = 6

FOR（MEX，1，n+1） { Find Range of L in this MEX Find Range of R in this MEX answer += len of Range_L * len of Range_R } you can solve MEX=i by MEX=i-1

Cause F problem was present in previous contests. Most probably round gonna get unrated