In problem D, I am struggling to understand the statement. According to my perception, the answer to the first test case should be 7. I will choose i = 4. The chain of the indices to strike will be like 4->3->5->6->2->1. Please someone correct me.

Reached Specialist, in this round.

problem E is a art.

It takes a lot of effort to achieve perfection in whatever any direction.

for C, if we have min = 2 & max = 11. since min is even then x=0 & min = 1, max = 5 now if I go according to the editorial. it would take a total of 4 steps (1,3 -> 1,2 -> 1,1). but when min = 1 & max =5, I can take x =0 and reduce in 1 step less (1,2 -> 1,1) total of 3.

am I missing something here?

Problem D: If it's necessary to check all indices as a first target point (according to tutorial), then why problem statement says that "Vasya chooses the first target optimally"?

[Problem C] Can someone help me understand why choosing $$$x$$$ as the average between $$$max$$$ and $$$min$$$ (or $$$a$$$ and $$$b$$$) doesn't work?

I guess it has somethings to do with parities and rounding down, but I honestly cannot figure it out myself.

Nice contest! I've learned a lot from it.

Question no. C, what does the line " You can consider all cases of parities of a and b to discover that it's always possible to divide the difference by 2, rounding down, and it's never possible to make it less than that. ".

I am struggling to understand the solution. Please help me understanding the solution.

Why there is a binary search tag in problem D. Although at first glance, it seems that we can go for a approach like BS in D. But NO!!!! so why there's a tag of BS

Why there's a tag of binary seach in problem D: although it seems at first glance that we can go for a approach like BS. But then realised there's nothing to do with BS.

Thanks for the fast editorial !

I've added hints and thought process for problems:

• A. Line Trip
• B. Chip and Ribbon
• C. Add, Divide and Floor
• D. Yet Another Monster Fight

on CF Step

For problem D, my after-contest solution only involved checking the first location, the last location, and the location with the monster that needs the most spell power to kill.

Submission: https://codeforces.net/contest/1901/submission/234308715

Is the test data weak, or is the strategy described above valid? Thanks.

In ques. D , I have trouble understanding the worst case, for eg in 2 1 5 6 4 3 can someone explain what will be the worst case and why ? according to me 2->1>5->6->4->3 should be the worst case

In problem D, according to my understanding the worst case for 2 1 5 6 4 3 should be 2->1->5->6->4->3 and that would not be possible with 8 damage ?

I think for Solution for problem D author wanted to write min(max(A[j]+n-j),A[i],max(A[j]+j-1)). Instead of max(max(A[j]+n-j),A[i],max(A[j]+j-1))

nvm I set my dp = -1 if it's not visited but I forget that the dp might be negative

i got accepted on F (237389815) by computing the overall hull in each step of the transition from old points to new points (the hardest part is to update the segment L = PQ that goes from a point P of the prefix hull to a point Q of the suffix hull).

we have to keep the prefix hull, the suffix hull and L = PQ updated. for each point y of the suffix hull, consider the segments that goes from y to each point x of the prefix hull. if we fix y, we can binary search for the first x which cross product changes sign in relation to the point x-1. with this we can find the point x_best of the prefix hull such that the line that contains the segment (x_best, y) necessarily covers all points of the prefix hull. we now need only to verify if this line also covers the suffix hull, which can be done with a cross product in relation to y+1. the first point of the suffix hull that this happens is the point Q.

in each step we should update the point Q based on the removals and insertions of new points of the current prefix and suffix hull. in order to keep it correct, we can do the following steps:

1) update the suffix hull by removing its current leftmost point and undoing the points that have been removed by it (inserting them back). for each of these added points, we must verify wether or not its line covers the prefix hull. this can be done in O(log n) for each point with binary searching in the prefix hull + some cross products for verification, as explained. doing this we are locating the new position of point Q.

2) update the prefix hull and change the suffix hull point Q status accordingly. since the added point covers all the prefix hull removed points (afterall, it defines the new prefix hull), we only verify if the point added changes the status of Q, with a binary search on the suffix hull, and update the point Q (basically, it can only make the point Q go more to the right).

3) now we have an updated point Q, and can binary search again the prefix hull to find the other point P that makes segment L.

There is a small error in the editorial for problem D. In the last three lines, the minimum spell power needed is $$$\displaystyle \min (\max_{j = 1} ^ {i - 1} a_j + (n - j), a_i, \max_{j = i +1} ^ {n} a_j + (j - 1))$$$, instead of the original $$$\displaystyle \max(\max_{j = 1} ^ {i - 1} a_j + (n - j), a_i, \max_{j = i +1} ^ {n} a_j + (j - 1))$$$. Guess it's just a typo.

There is a small error in the editorial for problem D. The minimum spell power needed is $$$\displaystyle \min (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$$$ instead of the original $$$\displaystyle \max (\max_{j = 1} ^{i - 1} a_j +(n - j), a_i, \max_{j = i + 1} ^ {n} a_j + (j - 1))$$$. Guess it's just a typo.

In Problem C, I was thinking in terms of binary representation. Taking x as the most appropriate number to shift the prefix of same bits to the right considering left as the largest similar bit (with all before it as same) but didn't went very far with it. Any suggestion with approach?

For problen D, for this case

6

1 6 1 1 6 1 , the accepted ans is 10, but shouldn't it be 9?

1 6 1 1 6 1

5 6 7 8 9 4. <--- Like this?