RIP SupaHotFire meme skils

Congrats dude you managed to survive the downvote apocalypse going on in here :P

good luck, bro! This is my first experience too :)

Educational rounds have never failed to be educational bro, you don't need to worry about that :)

No,you will not get any points but the hacked solution will count as wrong solution.

How's life?

6.9/10 recommend.

How the problems were educational ?

can you please provide the solution to it..i am getting WA. THANKS.

Yes just keep track of the minimum and maximum prefix sum

I solved it using prefix and suffix arrays.

might be, but will be an overkill.

yes but my code is very large and weird. Waiting for another solution (if there exist one)

No segment tree, required, for both prefix and suffix store the maximum and minimum sums.

I didnt manage to finsih the code but it is :

//Think simple yet elegant.
#include <bits/stdc++.h>
using namespace std;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll  long long
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define pi pair<int,int>
#define REP(i,n) for(int i=0;i<n;i++)
const ll mod=1e9+7;


int main(){
	fast;
	int t,n,m,l,r,i,j;
	cin >> t;
	while(t--){
		cin >> n >> m;
		string s;
		cin >> s;
		set<int> hsh;
		vector<int> p(n),s(n);
		hsh.insert(0);
		int val=0;
		for(i=0;i<n;i++){
			if(s[i]=='-')
				--val;
			else
				++val;
			hsh.insert(val);
			p[i]=hsh.size();
		}
		hsh.clear()
		while(m--){
			cin >> l >> r;
			--l,--r;
			cout<<p[l-1]+s[r+1]<<"\n";
		}
	}	
	
}

I used a sparse table, though it could have been done by maintaining a minimum of prefix/suffix and a maximum of those two.

The trick is to avoid all possible off-by-one errors. I did by try'n'error for about an hour.

We can convert edge {u, v, w} to three edges {u, v, w, 0}, {u, v, 0, 1}, {u, v, 2 * w, 1}. The fourth element in the edge is use as minimal or as maximal edge. Introduce Dynamic Programming d[v][flag1][flag2] — minimal answer in vertex v, where flag1 = 1, when we used maximal edge, and where flag2 = 1, when we used minimal edge. Calcing the Dijkstra. Answer for vertex v is d[v][1][1]

It was too complicated for me to find and proof the solution and thus i brute forced and observed the pattern .

from i=1 to 2*k-n-1 you need to print i itself . After that you need to start from k . For example for n=5,k=5 : 1 2 3 4 5. for n=6 , k=5 : 1 2 3 5 4 . n=7,k=5 : 1 2 5 4 3 . n=8,k=5 : 1 5 4 3 2 . n=9,k=5 : 5 4 3 2 1.

It can be proved that the number of inverse of array B must be more than or equal to A regardless of any permutation. I separated array into two parts p[1],p[2],...p[k-(n-k)-1] and p[k-(n-k)],p[k-(n-k)+1],...,p[k],p[k-1],p[k-2],...,p[k-(n-k)]. If you take a look at the latter part, you can see that, for any pairs of i<j between k-(n-k) and k, there is always one p[i] appeared before p[j] and another p[i] appeared after p[j]. So the number of inverse in the latter part is always constant because any pairs of i and j have exactly 1 inverse. In the first part, the number of inverse in array A is 0 because it is arranged in ascending order and every elements of first part in array A in less than second part. So basically, we have to create any array that the first part is the same as A(or else inverse will be more than A) which is 1,2,3,...,k-(n-k)-1 and second part can be any permutation of k-(n-k),k-(n-k)+1,...,k. and lexicographically largest permutation is k,k-1,k-2,...,k-(n-k).

I'll try to explain with examples

Let's use $$$k = 5, n = 9$$$
Initially
$$$P$$$ = $$$1, 2, 3, 4, 5$$$
And $$$B$$$ = $$$1, 2, 3, 4, 5, 4, 3, 2, 1$$$
Notice when you swap $$$5$$$ with $$$4$$$ in $$$P$$$ It doesn't change the number of inversions (because of the mapping b[i] = p[a[i]])
$$$P$$$ becomes $$$1, 2, 3, 5, 4$$$
And $$$B$$$ becomes $$$1, 2, 3, 5, 4, 5, 3, 2, 1$$$
So you can continue swapping the largest number to the left as far as the number you want to swap with has a duplicate value on the right-hand side of $$$B$$$

Let me use a smaller example
You have $$$k = 3, n = 4$$$
$$$P$$$ = $$$1, 2, 3$$$
$$$B$$$ = $$$1, 2, 3, 2$$$
You can swap $$$3$$$ to the left once in $$$P$$$
$$$P$$$ becomes $$$1, 3, 2$$$
$$$B$$$ becomes $$$1, 3, 2, 3$$$
And you can't swap $$$3$$$ again
Because if you swap it left you will increase the number of inversions

In general
If you have a sequence $$$P$$$ = $$$1, 2, 3, 4, 6 ... k$$$ and $$$n$$$
Reversing the last $$$n - k + 1$$$ in values in $$$P$$$ is your solution and the number of inversions remains the same.

Lol! reverse the original array.

if you found the solution for prefix ,why you didnt reverse the array and did the same thing?

You don't need to find maximum/minimum prefix of suffix. Instead, you can calculate sum in two segments and substract minimum/maximum suffix, which can be calculated similar to minimum/maximum prefix.

first traverse from front then from back, keeping track of current position and max. and min. it has reached.

You can use an edge more than once

I tried square root decomposition and was expecting it to work But got TLE because I use Python RIP. Maybe it should work in CPP O(M root(N))

so true :))

D can be solved by range minimum & maximum queries in Segment tree.

I did D by maintaining prefix and suffix minimums/maximums without segment trees. Just eliminate the effect of l to r by adding the cumulative sum to the min and max of the remaining suffix array. The answer is total_max — total_min + 1 Total_min and total_max are overall min and max(from prefix array and suffix array before l and after r respectively) after eliminating the effect of the segment l to r

traverse the input array, if there is no number greater than d, print yes. Now sort the array. If the sum of first two numbers is less than or equal to d, then it means that any number which is bigger than d can be replaced by the sum of these two numbers. But if their sum is not less than or equal to d, then we can be sure that no other sum in this array will be smaller than this. therefore, after sorting

if(a[0]+a[1]<=d) print yes else print no

Same for me, I find it hard to beleave that so much people solved C. It looks kind of unsolvable to me, I still did not read any near-to-understandable explanation.

Can you explain how did you do D?