What is the purpose behind setting limits such that (na + nb + ab) logn solutions fail E?

I have tried to optimize it, i got it down to 2.5s in a mashup with adjusted limits, couldnt get it to pass.

The problem was already quite hard enough without the limits, imo n<=1e3 wud be much better.

Good contest otherwise though, i liked both C and D

I tried every combination for problem C after setting the number 2 and it got accepted. Here is the CODE : 198939113

another solution for task B

https://mirror.codeforces.com/contest/1809/submission/198975521

Can someone help me prove my solution for C? I thought my solution was an elegant linear time solution but it did rely on one claim I was only probably sure was true. My claim was that: for any number 0 <= k <= n*(n+1)/2, and with access to the numbers 1...n, we can always greedily choose the largest n that fits and add it to the sum until we reach k. If this claim is true, then we can solve C using the following strategy:

Initialize an array of length n, all 0s

If we "set" index i of the array, then it will create n-i positive subarrays. We set the largest indices that fit into the sum of k.

Now we iterate through the array backwards and set the values such that the set indices make every subarray ahead of them positive and the unset indices make every subarray ahead of them negative.

Solution: 198783142

I didn't prove that we can always make k greedily using the numbers 1...n, but I thought it might be true because it felt similar to the Div 4 G problem.

Problem E becomes more interesting if instead of requesting all (c,d) pairs we only request q pairs. Limits like n<10^4, a+b<10^18, q<10^6

1809F - Traveling in Berland could be solved in $$$O(n)$$$ by using 2 pointers

We can duplicate $$$a, b$$$, st $$$a[i + n] = a[i]$$$ and $$$b[i + n] = b[i]$$$

Suppose we are solving for $$$k$$$ so our path starts at $$$k$$$ and ends in $$$k + n$$$

For example we have $$$x, y, z, \dots, last$$$ st $$$k \le x \le y \le z \le \dots \le last \le k + n$$$ and $$$b[x] = b[y] = b[z] = \dots = b[last] = 1$$$

We can split path into $$$k \rightarrow x \rightarrow y \rightarrow z \rightarrow \dots \rightarrow last \rightarrow k + n$$$

For points $$$x, y, z, \dots$$$ we can use 2 pointers. For example in point $$$x$$$ we will buy $$$\min(len[x \rightarrow y], limit)$$$ if $$$limit < len[x \rightarrow y]$$$ we will buy more in other points with cost 2

For $$$k \rightarrow x$$$ and $$$last \rightarrow k + n$$$ we can compute naively. Total complxity $$$O(n)$$$ 198830497

Graph explanation of E: (consider for all cases of (c, d) with same value of c+d)

if anyone solved D using dp, can you pls tell me the approach?

I actually didn't like the tutorial for task B

It's way too complicated for beginners

O(1) Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int32_t main() {
	int T;
	cin >> T;
	while(T--) {
	    int N;
	    cin >> N;
	    int r = ceil(sqrt((double)N)/2);
	    while(4*r*r < N) r++;
	    int mx = 2*r - 1;

	    r = ceil((sqrt((double)N)-1)/2);
	    while(4*r*(r+1)+1 < N) r++;
	    int mxx = 2*r;

	    if(N == 1) cout << "0\n";
	    else cout << min(mx, mxx) << "\n";
	}
	return 0;
}

O(logN) Solution

#include <bits/stdc++.h>
using namespace std;
#define int long long
 
int binarySearchEven(int N) {
	int start = 1, end = 1e9, r;
	while(start <= end) {
		r = start + (end - start)/2;
		if(N > 4*r*(r+1)+1) start = r+1;
		else end = r-1;
	}
	return start;
}
 
int binarySearchOdd(int N) {
	int start = 1, end = 1e9, r;
	while(start <= end) {
		r = start + (end - start)/2;
		if(N > 4*r*r) start = r+1;
		else end = r-1;
	}
	return start;
}
 
int32_t main() {
	int T;
	cin >> T;
 
	while(T--) {
	    int N;
	    cin >> N;
	    
	    int s = 2*binarySearchOdd(N) - 1;
	    s = min(s, 2*binarySearchEven(N));
 
	    if(N == 1) cout << "0\n";
	    else cout << s << "\n";
	}
	return 0;
}

I solved F after the contest with a solution that is O(n) 198883707, then noticed that each b_i is limited to either 1 or 2. The 1 or 2 constraint is essentially not required and would only slightly simplify the code.

Can anyone explain B's given test case? Why is answer for 975461057789971042 987654321? I am sure it should be 987654320.

A simple solution for task B is just print " (int) sqrt(n-1)" ;)

your have to define int to long long int.

I have two almost similar logic solution for problem B, one is failing while the other one is working.

Failing one- https://mirror.codeforces.com/contest/1809/submission/199048077,

Working one- https://mirror.codeforces.com/contest/1809/submission/199048367

Could someone help understand what's going wrong here? Also I see that for c++ sqrt(n-1) works while not for JAVA, why is that so?

Another possible solution for D:

• Start by skipping all leading 0's and trailing 1's, because these 2 parts are already sorted and we don't have to worry about them, let left be the index of the 1st '1' that we encounter from the left and right — the index of the first '0' that we encounter from the right. It is easy to see that if right < left then the string is already sorted.
• Count the total amount of 0's and 1's in substring s between left and right.
• We are going to iterate over s from right to left and each time we are going to count the consecutive number of 0's and 1's, meanwhile decreasing the total amount of 0's and 1's. Each time after we have iterated over 2 segments of consecutive 1's and 0's we have several options:

1. Let's consider keeping current amount of 0's and deleting current 1's, then this would mean that we also have to get rid of all 1's left up to left, so the string would become sorted, this way we can estimate the answer immediately.
2. If we delete the current amount of 0's then we have two more options: we would have to delete all 0's left in s up to left or we can keep the 0's and get rid of the 1's instead. This way we get 2 more estimates of our answer, also we are going to keep track of all possibly deleted 0's for future estimations.
3. Extra case: if current amounts of 1's and 0's are both equal to 1 and the total left amount of 0's is not less than amount of 1's then we get another estimate for our answer: deleting all left '1' with previously deleted 0's and adding a cost for one swap.

Iterating over s from right to left each time we assign our answer the minimum value of 3 + 1 possible estimates and our current answer.

Submission: 199079054

O(1) solution for B:

Solution: If N is a perfect square then the answer is √N — 1 and otherwise it's just √N

198856454

1809G is similar to 1437F, although the constraint of 1809G is tighter.

In problem D, how do they determine that it is optimal to have at most one delete operation.

Perhaps few person remember that EDU rounds may reuse old problems.

Actually 1809E - Two Tanks is a resemble of an old task OneDimensionalRobot from SRM 608 authored by rng_58.

https://youtu.be/xvyXv1IO7yg

Video sols for A,B,C

F can be solve in O(n) instead of O(nlogn). You can preprocess (not sure how to say it, you get the idea) the prefix and suffix of every position with gas price 2, then calculate the answer of any city with gas price 1.
The difference between different starting points will be: the concecutive price 2 cities that got seperated by the starting position. Just calculate the offset with prefix and suffix then you get the correct answer.
199636012

Is D solvable if it was given a permutation instead of a binary string?

I get Wa5 because of I mul 1e12 and I dont realize it, terribly

can anyone recommend problems similar to E

Alternate solution for C in O(n): https://mirror.codeforces.com/contest/1809/submission/209213026

We realise we can form an array [2, 2, 2, 2, -x, -1000, -1000 ...], -x will depend on the number of good subarrays you have yet to form from [2,2,2,2].

We try our best to form the most good subarrays at the left side, then once we could not do it anymore, we still have some leftover good subarrays to form. We can then set the value of -x to be such that we will form +leftover more good subarrays.

Problem G is totally the same as 1437F - Emotional Fishermen.

Alternate $$$O(n)$$$ solution for problem F:

Firstly, let us divide the city into maximal continuous segments of type-$$$1$$$ and type-$$$2$$$ cities (cities having fuel cost 1 and 2 respectively) by considering the starting city to be $$$1$$$.

Observations:

1. For any type-$$$1$$$ city $$$x$$$, it is never suboptimal to buy all the fuel we use for crossing it, in that city itself.
2. From observation $$$(1)$$$, its easy to prove that it is never suboptimal to arrive in a type-$$$1$$$ city with $$$0$$$ fuel left.
3. But however, sometimes we need to buy fuel in type-$$$1$$$ cities and use that fuel to cross type-$$$2$$$ cities. From observations $$$(1)$$$ and $$$(2)$$$, it's trivial to show that it's never suboptimal to buy extra fuel in a type-$$$1$$$ city, only when there is a type-$$$2$$$ city next to the type-$$$1$$$. (ie, the type $$$1$$$ city lies at the end of its segment)
4. When at a type-$$$1$$$ city $$$x$$$ which lies at the end of its segment, it's optimal to buy $$$min(k - a_x, \sum{a_i} (\text{over next type-2 segment}))$$$ extra litres of fuel to use in the next type-$$$2$$$ segment.

So for a fixed starting point $$$s$$$, the maximal segments are defined and constant.
For a type-$$$2$$$ segment $$$S$$$, define :

• $$$sub_S$$$ = extra type-$$$1$$$ fuel we buy from the city just to the left of current segment.
• $$$sum_S$$$ = $$$\sum{a_i}$$$ over all $$$i$$$ which lie in $$$S$$$.

The answer for a set of maximal segments is $$$\sum{a_i}(\text{over all type-1 segments}) + \sum{sub_s + 2(sum_s - sub_s)} (\text{over all type-2 segments})$$$.

Now when we iterate over the starting city $$$s$$$, at most two terms in this summation change on each iteration (corresponding to the type-$$$2$$$ segment we are "splitting" by $$$s$$$), these can easily by fixed in $$$O(1)$$$.

Implementation: link

Simple O(N) solution to problem C: 262967868