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?

Build a flow network as follows: let's create a source $$$s$$$, a sink $$$t$$$, and a vertex for each element. We will try to model the problem as the minimum cut in this network.

For every element $$$i$$$, there are several elements $$$j$$$ to the left of it that should be taken if we take it. Let's add a directed edge with infinite capacity from $$$i$$$ to all such elements. For elements will positive $$$b_i$$$, add a directed edge from $$$s$$$ to them with capacity equal to $$$b_i$$$. For elements will negative $$$b_i$$$, add a directed edge from $$$i$$$ to $$$t$$$ with capacity $$$|b_i|$$$.

What does an $$$s$$$-$$$t$$$ cut in this network represent? Let's say that all elements in the same part with $$$s$$$ are taken into the answer, and all other elements are ignored. Let's say that we have some $$$i$$$ that is taken into answer and depends on some element $$$j$$$ that is not taken. Then there is an infinite-capacity edge from $$$j$$$ to $$$i$$$, and it goes through the cut, so the value of the cut is infinite (and we are searching for a minimum cut, so this cannot happen). For each positive $$$b_i$$$, if $$$i$$$ is not taken, the value of the cut increases by $$$b_i$$$ (since the edge from $$$s$$$ belongs to the cut), and for each negative $$$b_i$$$, if $$$i$$$ is taken, the edge from $$$i$$$ to $$$t$$$ belongs to the cut, so $$$|b_i|$$$ is added to the value of the cut. So, the minimum cut actually minimizes the sum of positive $$$b_i$$$ that are not taken, minus the sum of negative $$$b_i$$$ that are taken, so it gives us the optimal answer.

There's one issue though. This network can easily reach $$$O(n^2)$$$ edges, and that's too much. To reduce the number of edges to something like $$$9n$$$, for each $$$i$$$, consider all divisors of $$$a_i$$$ (including $$$a_i$$$ itself) to the left of it. If there are several equal divisors, then taking the closest of them ensures that we take all other divisors into the answer, so actually, for each divisor of $$$a_i$$$, we need to consider only the closest occurrence of this divisor to the left of $$$i$$$, and add an infinite edge from it to $$$i$$$.

Why would anyone do this? Afaik you get nothing for hacking in this contest.

Getting downvotes due to CAPS :v

It's never said that $$$b$$$ has to be the sequence with the least number of inversions

True, but it is said that

[...] and $$$b$$$ is lexicographically maximum.

Also note that

It can be proven that $$$p$$$ exists and is unique.

I think you missed the requirement where B must be lexicographically maximum.

roz adhoc problems karke man nahi bharta kya patang udao gilli danda khelo! come out of this artificial life.

I did same mistake with you during contest.

Try to solve this testcase by your hand

1 7 4

Go to secondthrad's youtube channel , he has explained that problem quiet nicely.

Yes, 4 in both cases.

Yes. It's 4 in both.

No.1 2 3 2 1 have 3 inversions and 3 2 1 2 3 have 4 inversions

Your bfs solution is incorrect because edges in this task are weighted and that's why bfs won't work in this case. Try to use Dijkstra algorithm.

I think this violates Rule #6 by destabilizing the checking system (trying to increase the queue size by increasing the running time)

I got it no problem anymore:/

Nah, seg tree is really close to the linear solution anyway.

if(no.a>dist[no.b.a][no.b.b])continue;

it the pair in the priority_queue has more distance than the shortest
path found till now then don't iterate further.Codes which didn't
add this condition got hacked(TLE).weak pretests

create the following arrays :

MaxTillHere[] -> stores the max value upto a particular index MinTillHere[] -> stores the min value upto a particular index

then, using backward traversal create the following array :

MaxFromHere[] -> stores the max increase we'll get after a particular index MinFromHere[] -> stores the max decrease we'll get after a particular index

now the answer is simple, for each query (l, r) : int max = MaxTillHere[l — 1] + val[i] + MaxFromHere[r] int min = MinTillHere[l — 1] + val[i] + MinFromHere[r]

ans = max — min + 1

I hope my answer was clear. Some index value might be wrong here, but i hope you've got the gyst of the solution!

Educational contest take too much time for ratings updation and editorial normally

Что такое дп?

GREAT EXPLANATION BROTHER !!!