The problems were named after songs of my favorite musical group, Hippie Sabotage. Give them a try!
Hint1
Hint2
Solution
С++ Implementation: 204718333
Hint1
Hint2
Solution
С++ Implementation: 204718497
Hint1
Hint2
Hint3
Solution
С++ Implementation: 204718535
Hint1
Hint2
Solution
С++ Implementation: 204718553
Hint1
Hint2
Hint3
Solution
С++ Implementation: 204718603
Hint1
Hint2
Hint3
Solution
С++ Implementation: 204718641
instant editorial
What? Hints are in Russian and solutions are in English.
Sorry, fixed!
In your solution for Lunatic Never content you used n-i+1 when it should be n-i-1.
This is not a mistake
The difference comes from 1-enumeration against 0-enumeration
I'll add implementations as soon as system testing finishes.
Thanks for participation, I hope you liked the contest even though problem A was kinda hard.
It was very hard that first time users of codeforces can't sleep tonight
LMAO
almost 19 months, even not solving problem A in this contest. how can i sleep though?
you kidding right
Hahahaha
Hey! Can you please add implementation for Problem E?
A little late, but I added all of them:)
Thanks a lot man!
I am unable to open the solution links it seems
Yeah me neither. It says I don't have access to view the page. Take your time tho. Thanks for the hard work.
Damn access rights, will ask my coordinator for help here
if you are the manager of the contest while submitting, your submissions wont be visible.
In normal gym, there is the option to disable manager mode and then submit, im not sure if theres a similiar one here. Alternatively, you can ask somebody else to submit your codes for you, or use a third party website like pastebin.
Excuse me. Could Problem E get "Accepted" by Python or Pypy? I tried for a few times, but I failed.
Probably not, since problem E is tight on time limit.
Gotcha. Thanks. Poor Python :(
In Problem F, was the inaccuracy 1e-4 in projection set deliberately? Maybe the projection point is fairly accurate, but the judge adds a random number smaller than 1e-4. Otherwise It's simple to find all points by y=0, y=-0.001x (2 queries).
Yes, it was set deliberately The interactor simply adds noise to the answer
By the way, can we add line $$$x=0$$$ here and be alright? This way, we will have precise enough values of candidate ys (which are well spread apart), and then we can just match.
Right. That's one of the solutions.
Does a 2 query solution pass? I am not sure why you needed to add weird constraints and inaccuracy
+) I think the editorial for 'getting rid of noise' part is needed
May be because getting rid of noise is a part of the problem difficulty, otherwise, the problem is too easy to be placed in F.
I wrote a strange solutino for E and not sure if it will FST.
I notice that the bottleneck is calculating the relationship of (i, j), it's O(m) originally. The whole algorithm is O(n^2m). So I add two optimization strategies：
1 2 3 4 5
1 2 3 4 5
...
1 2 3 4 5
1 1 1 1 1
https://mirror.codeforces.com/contest/1826/submission/204635663
The method got accepted.
And all these above is unnecessary. O(n^2*m) implementation with a check: skip previous j if f[j]+a[i]<=f[i] is three times faster. Only 452 ms.
https://mirror.codeforces.com/contest/1826/submission/204631083
Both are hacked
Congrats with heuristics cheesing though :D
https://mirror.codeforces.com/contest/1826/submission/204725421
I improve this trick for E. Welcome to hack！
shit as predickted
Worst div.2 that I've ever participated in.
nice, you cant solve proplems and and you say its the authors fault
I have given quite a few contests(60+) which is more than twice of what you have given and yet it's my first time commenting something like this. There has to be a reason for this no?
I did not say it because of my bad performance, I said it because of the imbalance in the problems.You can see that B has more accepted solutions than A and the number of accepted solutions of A and C are comparable. This is not the usual case.
I have given more contests than you and I say it was a good contest and a nice problem set. Thank you authors for the nice problems.
I don't trust your nickname
Haha. It's just personal preference. Though I suck a lot at math I still love it.
It's not about giving more contests , I said it to show that I don't do comments like these after every contest. And I have given quite a few.
There are about 7000 solutions on a and about 6000 on c, maybe its really hard for a div2, but everybody can solve it, maybe not for 5 minutes as usual. As for c it is easier than usual, and you also could solve it, but you didnt and now you tell me that there is something wrong with the contest.bruh
Is D can be solved using ternary search ?
Isnt it f(len) = max1+max2+max3+len for all length a convex function
I tried during contest but couldnt do. Can somebody let me know whether i am correct or not
Why would it be convex?
Sorry my bad, intially i got intuition that it should be convex. But now i realized it is not necessary.
100 1 1 100 1 1 100 1
Function has local maximum at length = 4 and length = 7 so it is not convex
Problem B is from past contests.
Problem Link: https://mirror.codeforces.com/gym/102035/problem/I
In $$$B$$$, it should be "which basically says $$$x$$$ divides $$$a_i−a_{n−i+1}$$$"
You can solve problem 1826E - Walk the Runway in $$$O\left(n^2 \times m\right)$$$ in C++ without bitsets. Based on naive $$$O\left(n^2 \times m\right)$$$ approach, you need to apply next optimizations one-by-one for getting
1872 ms.$$$2.500.000$$$ numbers in input is a lot. Use fast input of chars with symbolic reading (google C++ getchar unlocked).
Reduce size of 2D array
rin $$$2$$$ times. Since $$$r_{ij} \le 500$$$, you can useuint16_t. It will allow you to hit L1, L2 and L3 cache better.Use cache-friendly order of data access. In original naive approach you need to compare $$$r_{1i} \lt r_{1j}, r_{2i} \lt r_{2j}, ..., r_{ni} \lt r_{nj}$$$, if you will decide to pick two persons $$$ij\text{ }\left(i < j\right)$$$ and placed them nearly. Instead of it, you can transpose array
rand compare $$$r_{i1} \lt r_{j1}, r_{i2} \lt r_{j2}, ..., r_{in} \lt r_{jn}$$$. Now, all of the elements will be placed in memory one-by-one and memory access will be cache-friendly.Allow GCC to use SIMD instructions. Enable
Ofast,unroll-loops,avx,avx2andfmaand use keyword__restrictfor pointing that memory for arrays are not overlapped.Accepted 1872 ms submission
Optimization 1 is redundant, this part of solution takes less then 100 ms.
__restrict keyword is also unnecessary, your code doesn't change arrays.
I tried to use similar approach but didn't came up with genius optimization 2.
I changed your check function a little bit, now solution is 1263 ms :)
204651252
Thank you, idea with unsigned difference instead of comparison is very cool too.
I think 1263 ms is not so fair, because during system testing a lot of solutions are running simultaneously on same cpu with common L3 cache (L2 and L1 are isolated and are private for each core) and more likely that someone will push out your data from L3 cache, then it will be pushed out of L2, then will be pushed out of L1, because it is required for data to be in cache of higher level. But I can be wrong.
I remember that runtime of my original solution was 1200 ms in the custom invocation during a contest with m = 5000, n = 500 and each row is sorted permutation, but it became 1700 ms after submit (pretests) and 1872 ms during system testing.
I tried to submit both versions within a second (obviously not during contest). I even tried to return back "restrict" keyword in my version. I repeated it 3 times. Here are results. Rather unstable but highest bit trick tends to be faster.
Screenshot
I think cache is not a bottleneck here. The main optimization is SIMD usage. uint16_t helps to do more operations per vector instruction.
Why highest bit trick is faster? Well, I guess sometimes bool type behaves in other manner. Like a widely known fact that construction "if (a && b)" for many compilers is actually "if (a) if (b)". I remember in some video a guy explained if you want your SIMD to work properly use bool very carefully :)
About 1200 ms on sorted max test — maybe branch predictor memorized this simple pattern and helped to reduce time in some way (I'm not sure, just an assumption).
I think my solution for D is different, and slightly over-complicated comparing the editorial.
I thought of the array being empty first and then I put the elements from higher to lower beauty in their position, at each iteration, the answer is to choose the best three consecutive sights, they are consecutive because the answer has the three most beautiful sights in some [l, r], when the minimum of them is put in the array, they are consecutive because there is nothing between them. Finally adding one sight to the array creates only three new trios of new possible consecutive sights, (e. g. m is the index of the new sight
[a, b, m, c, d], the new three consecutive trios are[a, b, m],[b, m, c]and[m, c, d]), so I represented the dynamic array with sets, and check the three new possible trios after I put an element in the array.So why my solution of E 204620376 got TLE?
Update: Now I optimized it in 204648297
To my mind, if there was problem E instead of problem D (but with smaller constants,like m<=100, n<=1000), this contest would be much better. Cause D is too easy for this position, and E is quite easy too (comparing to other "E" problems)
Why is this submission getting Idleness Limit Exceeded on Test 120?
EDIT: replacing 0.0002 with 0.0002004 gives AC :(
You can solve problem D even if instead of finding 3 best elements we had to
find k best elementsin time complexity ofO(k*nlogn). For finding best two, you can do the following : For all i, first insert a[i]-i in the set. Now iterate on i from left to right, erasea[i]-ifrom set and find maximum value in set(mx) and setb[i] = a[i]+mx+i. b[i] now contains the answer for maximum 2 values. Now you repeat this by insertingb[i]-iand setting asc[i] = a[i]+mx+iagain. Repeating this allows to pick k best elements inO(k*nlogn)Nice variant!
I think this can be optimized into O(NK) time: define $$$s(j, l) = max (A[i_1] - i_1 + A[i_2] + A[i_3] + ... + A[i_l])$$$ for any $$$i_1 < i_2 < ... < i_l < j$$$ (that is: the maximum value of a subsequence of length $$$l$$$ using elements before $$$j$$$ and baking in the $$$+ l$$$ term). Then the answer is $$$max(s(j, K-1) + A_j - j)$$$ over all possible values of $$$j$$$ ($$$1 < j < N$$$).
We can go through the array from left to right and calculate $$$s(j, l) = max(s(j - 1, l), s(j - 1, l - 1) + A_j$$$ in O(K-1) time, for an $$$O(NK)$$$ time and $$$O(K)$$$ space solution.
i did it in linear time by computing prefix and suffix maximums of of a[i]+i and a[i]-i respectively. and then iterating from 2nd to last second sight 204718856. i wonder how can we solve this using DP, not very good at it ;-;
What is the fairly straightforward solution using DP for D mentioned in the editorial?
DP method uses the same idea: two of the three biggest values are in left and right boundary. Otherwise we will shorten the range and get smaller cost.
f[i][j]is the answer of choosingjnumbers in firstiofnnumbers.0<=j<=3.the cost
-(R-L)=L-Rcan be added into calculation in running process.When the first number is selected, left boundary
Lis fixed to its index. This isf[i][0]->f[i][1], add indexi(=L) to answer additionally.When the third number is selected, right boundary
Ris fixed to its index. This isf[i][2]->f[i][3], subtract indexi(=R) to answer additionally.The method can be expanded to selecting
knumbers rather than3numbers, with timeO(nk).Thanks for this , here is the implementation : 204715362
Thank you for preparing for this round, despite the A problem is hard than B,C hh:)
Problem B was written before:
MikeMirzayanov
It doesn't matter because it's easier to solve than to find the original problem.
Wow, editorials come so fast...
In problem C,
First we need to notice, that in order to keep some amount of options indefinetely, this number has to be at least 2 and divide n.
How to prove that number d divide n ?
Each person casts exactly $$$1$$$ vote. If there are $$$m$$$ options and $$$n$$$ people voting, then for all options to be kept, they must all receive an equal number of votes, $$$k$$$. That means $$$km = n$$$, or equivalently, $$$n$$$ is a multiple of $$$m$$$, or equivalently, $$$m$$$ is a divisor of $$$n$$$.
Thanks! i misread the problem and wasn't considering no matter how people vote, now i got it.
In this i am doing same but then also i got WA why?
I have a different solution for D. I solved it using the divide and conquer method. I must select three elements that maximize the answer from 1 to n. At first, I divided the range into two equal segments 1 to n/2 and n/2+1 to n. Now, there are four cases. 1. All three elements are on the right side. In this case, we have to solve it for the range n/2+1 to n. 2. All three elements are on the left side. In this case, we have to solve it for the range 1 to n/2. 3. Two elements are in the left segment and another one is in the right segment. 4. Two elements are in the right segment and another one is in the left segment. I have to take the maximum of these four results. For case 3 one element is on the right side. I have iterated over the right segment for the element. If I take ith element it will make profit li and to take this element I have to travel i-n/2 miles. So, the ultimate profit is li-(i-n/2). I took the element which makes the maximum profit. For the left segment, there are two elements. I have iterated over the left segment. If the ith element is the first element of the two elements then I have to travel n/2-i miles. I will take the maximum two elements x and y from the i to n/2 range. Then it will make a profit of x+y-(n/2-i). I have chosen that make maximum profit. Case 4 is similar to Case 3. The complexity is O(nlogn). Here is my solution. https://mirror.codeforces.com/contest/1826/submission/204653388
19k registrations and only 5k participants nice A ;)
Problem D can be solved easily without precalculating anything. In fact, it can be solved in O(1) space and O(N) time: https://www.codeforces.com/contest/1826/submission/204656798
The logic is similar to the editorial. We rewrite the problem as: maximize $$$(A_i + i) + A_j + (A_k - k)$$$ subject to $$$i < j < k$$$. Then we can run the values $$$k$$$ from 1 through N, and keep track of the maximum values of $$$A[i] + i$$$ and the maximum value of $$$(A_i + i) + A_j$$$ (see the code for details) at each position.
It's the same DP but you used k-1 = 2 variables to store dp[i][1], dp[i][2] and "answer" to store dp[i][3]
Problem E has weak tests because some AC submissions used random or checked if 50-100 comparisons were ok, while there are 500 needed.
I've added one test to hack these submissions but its still not ok, i guess.
in Ques A why not l(i)>=x as at least x can be no of liers ,, as in editorial its l(i)>x
oooh shit i got it!!
okwedook I still don't understand why 2 queries aren't enough in F. Is it not ok to get the x coordinates through projection on y = 0 and y coordinates through projection on x = 0? It is also written that ans should be correct till 3 decimal places and since the noise is < 10−4 for each point through the query, shouldn't we be good?
From the statement:
In one query, you can ask some line ax+by+c=0 and get the projections of all n points to this line in some order
The points are not nescessarily returned in the same order every time. Thus, the two following cases are indistinguishable from each other with just queries $$$x = 0$$$ and $$$y = 0$$$:
For both of these cases you could recieve the following answers:
$$$x = 0 \ \Rightarrow \ 0\ 1\ 0\ 2$$$
$$$y = 0 \ \Rightarrow \ 1\ 0\ 2\ 0$$$
Thank you so much, I understand it now!
Am I the only one not getting the solution of A? :(
This much is obvious that the number of liars can range anywhere between [0, n] inclusive. Say the no. of liars is L.
From the statement: Some of them might be liars, who always tell lies. The i-th person says "There are at least L liars amongst us".
Since liars always tell lies, they will surely say that the no. of liars are atleast L+1. So these people will always report a value >= L+1
So, if for some value of liars = L, if you are able to find exactly L people who say liars are > L then that means that L is actually the correct no. of liars.
You can iterate over all all possible values of L and check.
AC submission: 204649911
4
2 2 2 2
plz explain this test case nksrivastava18
Let's break it down into 2 subcases.
Claim 1: Let's say the 1st person is not a liar. Therefore his statement is true. So out of the leftover 3 people, the number of liars should be atleast 2. So either 2 of them are liars or all 3 are liars. If only 2 of them are liars, they should lie and report atleast 3 as their answer. Since this is not the case, all 3 of them should be liars. Because all 3 are liars, they should lie and report that there are atleast 4 liars. Since even this is not the case, therefore our claim 1 is false.
Now we are only left with the option that 1st person is a liar. Let this be claim 2. Since he is a liar, his statement is false. Therefore the no. of liars should be strictly less than 2. But since we are still left with 3 people who are saying the no. of liars should be atleast 2, therefore these 3 should also be liars. This is a contradiction and hence claim 2 is also false.
Hence we can conclude that all of them are contradicting each other and return -1 as the answer.
But isn't it always possible that everyone lies? (No. of liars is N)
Which part don't you understand?
Assume the number of liars is $$$x$$$. Then all people who said that the number of liars was greater than $$$x$$$ were lying! So to count how many liars there actually are, you need to count the number of $$$A[i] > x$$$ (note that $$$A[i] = y$$$ means the i-th person claims there are at least $$$y$$$ liars).
It's easy to turn this into an $$$O(N^2)$$$ solution. The challenge is then to optimize this into an $$$O(N log N)$$$ solution.
Still not getting the logic. Why do we need to count A[i] > x?
People can only speak a falsehood by overestimating the number of liars, not by underestimating, since each person only makes a claim about the minimum number of liars there are.
Let's look at a concrete example:
Then there are four possibilities:
Maybe 0 people lied. But that cannot be true, because if 0 people lied, then Charity was speaking the truth, but Anna and Bernd were both lying about the number of liars, so there are 2 liars, not 0.
Maybe 1 person lied. In that case, Anna and Charity are speaking the truth, and Bernd is the sole liar, which is consistent.
Maybe 2 people lied. But that cannot be true, because in that case, Charity and Anna are speaking the truth, and Bernd is lying, so there is only 1 liar, not 2.
Maybe 3 people lied. But that cannot be true, because in that case, all three people are speaking the truth, so there 0 liars, not 3.
So the only valid choice in this case is $$$x=1$$$.
Yes now I understand. Thank you so much for taking the time to explain ^_^
4
2 2 2 2
plz explain this test case
Petition: set at least 2.5-3 seconds time limit when the intended solution requires >1e8 operations. :)))
Which problem are you referring to?
Problem E surely, where the correct solution is $$$O(N^2 M)$$$ with N=5000 and M=500, which makes for $$$125 × 10^8$$$ operations, though processing 64 bits at a time is supposed to bring that down to $$$~1.95 × 10^8$$$.
That's the problem with this type of tasks
You can't cut off all the unintended solutions without cutting off some of the slower intended ones
My fastest solution was faster than 500ms, so a 2s TL is only fair
First of all, thanks for the wonderful round.
I just wanted to say that solving the problem shouldn't be about being "risky" enough ddd.
For A, in the case that everyone says that nobody lied, then everyone may have lied, but that is not an accepted answer.
The people cannot say that nobody lied. They would be saying "at least 0 people lied" which is obivously always true (it's impossible for less than 0 people to lie). Thus if everyone says this, everyone must speak the truth and the number of liars must be 0.
Can anyone give submission link for recursive dp solution of problem D?
If anyone wants to know 204689878
I had a somewhat different solution for Problem B, which I'm not sure whether it was intended to pass or not.
Like the official solution, I consider the pairs of numbers that must be made equal (first and last element of A, second and second-to-last element of A, etc.), ignoring the numbers that are already equal (if all are equal, the answer is 0). For the first pair {a, b}, calculate all possible divisors of $$$a - b$$$. Then for each other pair {c, d}, filter down the possible divisors by checking if each divisor is also a divisor of $$$c - d$$$. (submission source code).
This solution is $$$O(sqrt(10^9) + N×k)$$$ where $$$k$$$ is the maximum number of divisors of a number below 10^9 which is around 1000, for an overall ~100,000,000 iterations.
bad contest
problems were not clear or understandable
Task E is cool, thanks!
May I know if it's possible to do problem A faster than brute force and how to do so?
You can do it in n log(n). The idea is that if someone saying that there are at least 10 liars is saying the truth, then everyone else saying there are 1,2,...,9 liars will also be saying the truth. So you can iteratively check if exactly the first n people are saying the truth or not in O(n) after sorting.
Thanks!
E can be solved in O(nmlogn). we can build a binary index tree for every city.First, we sort all the models by their beauty in every cities(the first city has the largets weight the second has the second largets ...). then, we can do dp with this order( any reverse in this order is invalid!). When dp, for a model i,we can query every binary index tree for every city to get their previous max dp. for those maximum dp values we choose the minimum one for that one is the valid one.(unfortunately I fst cuz I for got that std::sort is weak sortings qwq)my code
What a WAnderful contest, I gained so much~
What is wrong in this this method for C
It is not full. You should add some code. For example, n = 9, m = 4. What is right answer for this test?
yaa i got it , thanks
for problem F, the output format of my code is correct in my computer, but I get a WA because "wrong output format Unexpected end of file — double expected". what's up?
204643420
upd: I adjust my code but also WA for same reason. WHY?
204683775
If I try to see the implementation it says: You are not allowed to view the requested page. What should I do?
Unable to open C++ implementation
"You are not allowed to view the requested page"
I was not able to solve B. Now my rating is a palindrome too xD
Can D be done without dp??
Hey, the C++ Implementation's link in problem A is blocked.
What is the distinction between a lie and a contradiction?
The above test case gives 3 as answer even though what the 4th element is saying is never possible.
In the same sense:
The last 2 says there are atleast 2 liars, and he's right, there are 4 liars, because what the first 4 is saying can never happen. But here the answer is -1. Can somebody explain? TIA
In your second example statements of the first 5 people stay consistent with the previous statements, but the 6th person, who is saying that at least 4 people are lying contradicts himself and the rest of the statements, he can't either be lying or telling the truth.
If the first 5 people are telling the truth then it means that there should be at least 2 and at most 4 liars in the group. Then if the 6th person is telling the truth that actually means that he should be one of the 4 people lying (a contradiction). If he is lying that means that there should be less than 4 total people lying in the group, therefore out of the last 3 people in the group at least 1 should be telling the truth (in turn meaning that there is at least 7 people lying or more, a contradiction).
Hope this helps!
why still I can't see the authors implementation?
Can you see it now?
yes.
My nlogn solution for A with a map: 204718789.
For the life of me couldn't figure out the brute force approach for A (although by looking at constraints it was obvious to me that n^2 should pass).
I wrote also nlogn solution after contest (Virtual Contest) is over Just now after seeing your comment I just checked and saw n is 100 only :p.
Where does the number 64 come from in time complexity of Problem E. O(n^2m/64)
The number of bits used by one number in a computer. In a 64 bit machine this number is 64. This number is often referred to as $$$W$$$, or wordlen.
Thanks a lot!!
The operations on bitset has a complexity of O(N / K) , where N is the length of the bitset and K is the register size of the system (generally 32 or 64). Link
Thanks for the help :)
I am facing a weird behavior in problem F. I will query the 3rd line if the minimum distance between any projection of candidate points is at least
EPS. When I setEPS = 1E-6I getTLE, whileEPS = 5E-4will getACin 200ms. However this is weird since smallerEPSmeans it is more likely to achieve the condition.EPS = 1E-6(TLE): 204744948EPS = 5E-4(AC): 204744799How to solve problem D with the DP method
https://mirror.codeforces.com/contest/1826/submission/204575344
thanks very much
I started solving problem A as soon as the contest started. Gave up after an hour. Had dinner. Started again, thought of a binary search solution; didn't work, then i thought of a linear search solution(the correct one); couldn't implement it, i was just off by one line of code. Gave up. After the contest was over and i looked at the answer it was the hardest facepalm moment of my life.
Coding style is appreciable !!
My thoughts on problem F. Please correct me if you find any issues.
Theoretically, if we choose the degree of slope of our line uniformly in range $$$(0, \pi)$$$, the probability that two points fall on the same line should be 0, and choosing some random fixed slope should also work. However, there are about 200 tests. Consider if each one has $$$t=50$$$ cases, and each case has $$$n=10$$$ points, then the total number of vectors that can be formed is $$$200*50*10^4=10^8$$$. Denote our line as $$$w'x = b$$$, then the maximum of minimum angle between any vector and $$$w$$$ is $$$\frac{1}{2}\frac{ \pi}{10^8}$$$, and the smallest distance between projections of two points is $$$\sqrt{2} sin(0.5\frac{\pi}{10^8}) = 2e-8$$$. Now, this might still be distinguishable by double precision, but the problem can add a $$$1e-4$$$ noise to coordinates. If that noise is added in the direction parallel to our line (that is, orthogonal to $$$w$$$), then it is very easy to swap position of two projected points. Similarly, even if we randomize the slope each time, it is still unlikely to avoid all the vectors (I tried).
However, by the same analysis, if for each test case we choose the maximum possible minimum angle, then the smallest distance becomes $$$\sqrt{2} sin(0.5 \frac{\pi}{25^4 / 2}) = 1e-5$$$. Note that this is still smaller than $$$1e-4$$$. My first guess is that, since the $$$O(n^4)$$$ vectors are formed by choosing pairwise among $$$n^2$$$ points, it actually does not have enough freedom to uniformly spread among $$$(0, 2\pi)$$$, so the true gap is much larger than $$$2e-5$$$. This could be true, but the real reason is that, because all coordinates are in the range $$$(-100, 100)$$$, it is actually impossible for any vector angle to fall in range of, e.g. $$$(0, arctan(\frac{1}{200}))$$$, which is $$$2e-3$$$! This makes the problem completely trivial, as we can actually choose some fixed slope, e.g. $$$a=400, b=1$$$ should be the safest as it maximize the minimum gap. However, if this bound of $$$100$$$ is changed to $$$10000$$$, then we should still use the method by the editorial.
The $$$1e-3$$$ constraint does not matter as we can obtain coordinates from first two queries at the precision of $$$1e-4$$$.
The editorial says it has a fairly straightforward DP solution, but I feel, most of the people who solved it, skipped the mathematical proof of why it is okay to take the max $$$(b_l + l)$$$, thus converting the problem from find the max 3 elements and subtract $$$(r - l)$$$; to given an array, maximize $$$(b_l + l) + b_m + (b_r - r)$$$.
Proof: Let's say for a given $$$b_m$$$ there exists a $$$b_{l_1}$$$ and $$$b_{l_2}$$$ such that $$$b_{l_1} + l_1 < b_{l_2} + {l_2}$$$; given $$$l_2 > l_1$$$ and $$$b_{l_1} > b_{l_2}$$$. But in our segment, we have to take the maximum element so if $$$b_{l_1}$$$ stays we'll have to accept the value calculated using it. But we safely use $$$b_{l_2}$$$ which returns a higher value.
But this doesn't always work.
What if the question asked you to maximize $$$(b_l - l) + b_m + (b_r + r)$$$? I have seen some solutions for D, where people have tried looking for previous state of DP using LastGreater element, and I thought I am not the only one who doesn't find it straightforward.
"A more straightforward one, is checking all the numbers from 2 up to √n"
Hi can you please help me understand why we didn't go till n.
Can you please provide the dp approach for problem D. I understood the direct approach, I would really appreciate the help and thanks a lot for the effort.
https://mirror.codeforces.com/contest/1826/submission/204575344
Problem D , DP solution please explain!