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>=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 < 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 < 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.com/contest/1461/submission/100945988

Try using long double

Edit: nvm, see comment below

Actually, you are not reading all the input for a test case and returning early.

Inclusion-Exclusion is O(2^n). For example,

| A U B U C| = |A| + |B| + |C| — |A ∩ B| — |B ∩ C| — |C ∩ A| + |A ∩ B ∩ C|

Inclusion exclusion wasn't needed. 1-p would be the product of individual (1-pi's) provided the part after position ri is sorted From that p can be computed

I have used inclusion-exclusion as well. But I have used dp for calculating it.

with same approach, why my code fails

https://codeforces.com/contest/1461/submission/100926909

please help to find error.

what is it, I wrote a strange recursion which might fail if someone hacks

Can you please provide a reference? Thanks.

is it, can you please share the link if possible?

Just implementation (you can use prefix sums as well).

Let's define dp[i][j] as a number of spruces where (i, j) is the top. Now you can calculate dp table iterating from bottom to the top in the following way:

if s[i][j] == '*':
    dp[i][j] = min(dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]) + 1
else:
    dp[i][j] = 0 

The answer to the problem will be the sum of all values in the dp table.

You are not getting whole input correctly

Did the exact same mistake -_-

that costed me 2 penalties

Use prefix sums.

Just a small hint: to prevent bugs in binary search you can try to use lower_bound() and upper_bound()

My code was failing too in pretest 7. For me, it was an integer overflow problem and changing int to long long int fixed the code.

B is not dp

i know a way using manacher algorithm and two pointer in $$$O(n*m)$$$ worst case

I used a simple algorithm for B

Basically, build it from the bottom (after checking for valid indices, etc.) :

tree[i][j] = min({tree[i + 1][j - 1], tree[i + 1][j], tree[i + 1][j + 1]});

Reference

Edit: Perhaps that qualifies as DP (not sure)

Nah that problem D was 50x more cancer than this problem B :P. On this problem B they were generous enough to let you bash.

I believe segment tree should do it, just sort the array beforehand. For some reason I could not get the second test in the given pretest right, so I didn't submit. But still it seems relatively simple. Correct me if I'm wrong.

The method I thought of is instead of getting the traditional tm = (tl + tr) / 2, we use binary search to find the first index greater than our mid element.

And finally, you insert the sum from tree[v] into some set. In the end for each query if you can find it in the set it's possible, otherwise not.

Just a simple "merge sort"-like recursion will do it all.