Feel Good to you and your friend as a first time tester Sir !!

As a tester, my name is not mentioned in the tester's list. ⊙︿⊙

Edit — Now I'm on it.

Where is score distribution??

Same here!! And I can say after the contest everyone will love zebra.

As a contestant, me too :D

Who's idea? btw I'm neutral towards zebra but the photos were good and calming to look at. Thanks

Isn't rating a zero sum game? Although, I'm not entirely sure what the method to compute rating delta is...

Hi, sorry I was just testing this round — there won't be any video editorials for it.

However I am making video editorials for a contest later this month, so look out for that :p

As a plagiarism hater, stop copying my son's comments every now and then

no meme for this announcement?

10x deadlier when combined with weak pretests.

Unfortunately, I don't see your name in the testers list

If there is I am going to troll them by solving it with KMP.

Now even if they planned to have such problem, they will replace it with another problem because of this comment!!!

What is Z-algorithm?

Were the problem statements short, sir?

I am sure, he will.

Did you try not trying?

Taking breaks actually help.

*Problems

The scoring distribution is 500 — 1000 — 1250 — 1500 — 2250 — 2750.

no you

yes, found them easy enough to interpret

Find such maximal position X that for all i > X it is true that a[i] = i.

Then just calculate the answer with a well-known formula:

ans = 1

if (r[i] >= X) ans = ans * (1 — p[i])

Answer is 1 — ans.

Here is how I thought about it : First we find the first index such that the suffix of the array is sorted. Now inorder to make the array not sorted after m operations, the elements at index = (first_index-1 to n) should not be sorted. Then just do 1-x as we have to find winning probability. Idk why it fails on pretest 2.

//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 maxn=100005;
const ll mod=1e9+7;


int main(){
	fast;
	int t,n,i,j,k,m;
	cin >> t;
	while(t--){
		cin >> n >> m;
		double y=1.0;
		vector<int> a(n+1);
		for(i=1;i<=n;++i){
			cin >> a[i];
		}
		if(is_sorted(all(a))){cout<<fixed<<setprecision(10)<<y<<"\n";continue;}
		vector<pair<int,double>> v(m+1);
		for(i=1;i<=m;++i){
			cin >> v[i].ff >> v[i].ss;
		}
		sort(all(v));
		vector<bool> suff_sorted(n+1,false);
		if(a[n]==n)
			suff_sorted[n]=true;
		int first_ind=n;
		for(i=n-1;i>=1;--i){
			if(a[i]==i && suff_sorted[i+1]){
				suff_sorted[i]=true;
				first_ind=i;
			}
		}
		double x = 1,init=0;
		int ind=m+1;
		if(a[n]!=n)
			first_ind=n+1;

		for(i=1;i<=m;i++){
			if(v[i].ff>=(first_ind-1)){
				ind=i;
				break;
			}
		}
		//cout<<ind<<endl;
		for(i=ind;i<=m;++i){
				x*=(1.0-v[i].ss);
			
		}
		cout<<fixed<<setprecision(10)<<(1.0-x)<<"\n";

	}
}

Well first find the length of the largest suffix of a that is sorted in ascending. Say it has length len. Then let x = n-len. Clearly, if any operation (r, p) has r >= x, the whole array is sorted. Lets say we have opi1, opi2, ... opik where 1 <= i1 < i2 < ... < ik <= m, such that the previous condition is satisfied. picking any combination of these operations to go through to sort the corresponding prefix of array a will suffice to sort the whole of array a. Also an interesting thing is the probability of this occuring is exactly 1 minus the probability of the complement, that is, none of these operations going through. None of the other operations opi matter if it doesn't belong to the previously said list. Now the probability of this compliment, is just the product of (1-pi1)(1-pi2)...(1-pik). As I already said, ans is 1 minust that. One corner case is if array is sorted to begin with, in which case the answer is just 1.0. (As ops don't affect array)

Note that once the array is sorted it never gets unsorted, by definition of the problem.

Then, if a postfix of len x is sorted, the array can get sorted in each experiment if $$$r[i]+x \gt =n$$$

In this case it stays unsorted with prob $$$1-p[i]$$$

So we need to multiply all these numbers to get the probabilty that the array is still unsorted after last experiment. Then ans equals 1-prop.

Give you a permutation.

Then give you $$$m$$$ operations like $$$(r_{i},p_{i})$$$. It means in this operation, It has $$$p_{i}$$$ probability to let the first $$$r_{i}$$$ numbers in the permutaion be sorted.

You task is to find the possibility of permutations to be sorted.

test 13 of E is probably some overflows on long long

Since you can easily get the solution later. Here's a hint, try searching for problem "Maximal square in a rectangular matrix having 1" and try to use the same approach. I used same.

My solution breaks it into two cases, although maybe someone else can provide a more concise solution.

I won't detail the exact formulas, but you can see them in my submission.

Case 1: $$$x \geq y$$$

The overall value of $$$k$$$ diminishes over time, so we should greedily add $$$y$$$ whenever possible to prolong the time the cooler amount stays above $$$l$$$. Initially, for some number of days, we won't be able to add $$$y$$$ without overflowing past $$$r$$$, so our cooler amount decreases by $$$x$$$ for each of those days. After a certain point, we will always be able to add $$$y$$$ without overflowing, so our cooler amount decreases by $$$x - y$$$ for the remaining days. We can calculate all this information in $$$\mathcal O(1)$$$ with some math.

Case 2: $$$x \lt y$$$

Because $$$y$$$ is greater, we can always first let the cooler drain at a rate of $$$x$$$ for as many days as possible, before adding $$$y$$$, then repeating. This is optimal since we're only refilling when absolutely necessary, so we don't risk overflowing $$$r$$$. There might be an $$$\mathcal O(1)$$$ math formula for this, but I'm not sure. I did $$$\mathcal O(x)$$$: whenever we add $$$y$$$, it's because we can no longer drain any more $$$x$$$, so $$$0 \leq k - l \lt x$$$. We can thus treat this as a graph that cycles through nodes $$$0 \dots x - 1$$$, and if we ever encounter a cycle, we know that going through this cycle will sustain the cooler capacity for the entire $$$t$$$ days.

I know that wasn't the clearest explanation (I found it a bit difficult to put into words), but hopefully the code can clear up any doubts. https://codeforces.me/contest/1461/submission/100945988