instant editorial

What? Hints are in Russian and solutions are in English.

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.

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).

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：

• When the transition can be from F[i] to F[j], I ommit the nodes of the solution chain of F[i]. This may be hack by this array:

1 2 3 4 5

1 2 3 4 5

...

1 2 3 4 5

1 1 1 1 1

• So I add another strategy: If [line x] causes j to be unable to connect to i. The next link judgement will start from [line x].

https://mirror.codeforces.com/contest/1826/submission/204635663

shit as predickted

Worst div.2 that I've ever participated in.

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

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.

Accepted 1872 ms submission

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 the total time complexity would be O(n2m/64)
, which is fast enough.

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 elements in time complexity of O(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, erase a[i]-i from set and find maximum value in set(mx) and set b[i] = a[i]+mx+i. b[i] now contains the answer for maximum 2 values. Now you repeat this by inserting b[i]-i and setting as c[i] = a[i]+mx+i again. Repeating this allows to pick k best elements in O(k*nlogn)

What is the fairly straightforward solution using DP for D mentioned in the editorial?

Thank you for preparing for this round, despite the A problem is hard than B,C hh:)

Problem B was written before:

• https://mirror.codeforces.com/problemset/gymProblem/102035/I

MikeMirzayanov

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 ?

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.

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

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?

Am I the only one not getting the solution of A? :(

Petition: set at least 2.5-3 seconds time limit when the intended solution requires >1e8 operations. :)))

For A, in the case that everyone says that nobody lied, then everyone may have lied, but that is not an accepted answer.

Can anyone give submission link for recursive dp solution of problem D?

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?

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

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

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?

6
3 3 3 5 5 6

The above test case gives 3 as answer even though what the 4th element is saying is never possible.

In the same sense:

9
0 1 1 2 2 4 7 8 9

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

Не даёт посмотреть решение. Недостаточно прав для просмотра запрошенной страницы

why still I can't see the authors implementation?

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).

Where does the number 64 come from in time complexity of Problem E. O(n^2m/64)

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 set EPS = 1E-6 I get TLE, while EPS = 5E-4 will get AC in 200ms. However this is weird since smaller EPS means it is more likely to achieve the condition.

EPS = 1E-6 (TLE): 204744948

EPS = 5E-4 (AC): 204744799

How to solve problem D with the DP method

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.

• Never mind understood.

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.

Problem D , DP solution please explain!

why solution of O(m) getting TLE for problem C

bool f(ll n, ll m){ if (n == 1) return true; if (m >= n) return false; while (m > 1){ if (n % m == 0) return false; m--; } return true; }

Why does this approach doesn't work? This solution is more nature for me than GCD one. It's not the TLE, but the answer isn't correct and I can't see failure testcase. Thanks for future replying!

n = int(input()) d = list(map(int, input().split())) mx_mod = max(d) if mx_mod == 0: print(0) continue flag = True for i in range(n // 2): if d[i] != d[-i — 1]: flag = False while d[i] % mx_mod != d[-i — 1] % mx_mod: mx_mod -= 1 if flag: mx_mod = 0 print(mx_mod)

Problem $$$E$$$ can also be cheesed.

The crux of the problem is to efficiently determine if model $$$i$$$ can go before model $$$j$$$. To do this, we know that:

(1) If $$$sum[i] + n > sum[j]$$$, then we know that model $$$i$$$ cannot come before $$$j$$$.

(2) If $$$mx[i] \ge mx[j]$$$, then model $$$i$$$ cannot come before $$$j$$$, where $$$mx[i]$$$ is the max rating of the $$$i$$$th model. Likewise, if $$$mn[i] \ge mn[j]$$$, then model $$$i$$$ cannot come before $$$j$$$.

Only if the above $$$3$$$ conditions are not met do we naively check the ratings in $$$O(m)$$$ time.

Once we check these constraints, we know that model $$$i$$$ must go before model $$$j$$$. But we also know that all models that come before model $$$j$$$ must also come before model $$$i$$$, so we add those to the graph.

Apparently, this approach passes. 211357168

Would be interested if someone could hack me...

For Problem D, I tried using a two-pointer approach, basically moving l or r depending on which value is smaller. Now instead of repeatedly computing maximum in [l,r] , I maintained 3 variables m1,m2,m3 and adjusted accordingly. Here is my implementation.

It is failing on tc 4, can someone help me figuring the error please ?

Hello guys i know it's been a while for this div but i have an idea on D that got me ACC so we can make it using seg tree because b1+b3+b2-(r-l) to be maximized we can see it like this : (b1+l)+b2+(b3-r) and for every element from 2 to n-1 we can get max element which is (bj+j) and j from 1 to i-1 and max (bc-c) where c from i+1 to n so result will be max(bi+max(bj+j)+max(bc-c)) and we can query using the seg tree to see the two element we are looking for because both B1 and B3 needs to be the left and right itself