Finally, the editorials are out.

Has any one solved the problem E like the tutorial? Please post your code.

Can someone explain the other solution to E ?

I saw many solutions which did not use the binary search idea. For example neal submission

Can Any one give a Dynamic Programming Solution with explanation for Problem B? Thanks in advance

Can anyone explain the count(x)>count(x+2) concept of the problem E?

Well, I use a weird method for E: We first calculate the path of n and store it in one list, then for every even number x in path(n), add x-2 to another list. And a weird (but probably true) statement is that the answer will only occur in the two lists. Since the size is O(log n) and checking can be done in O(log n), This solution is O(log^2 n). But, I don't know whether the statement is true, so do anyone know how to prove or disprove it?

In editorial of problem D it's written that: "The key observation is that it's always optimal to defend castle i (assuming we decided to defend it) in the latest possible castle. Since it gives you more warriors in between of i and X (more freedom), it's always optimal." How is this true? Suppose there are two X1 and X2 from where you can go to i and X1 is near to i than X2. But it doesn't guarantee that you will have more warriors during X1 than X2. It depends on how many warriors are you gaining after each win. Please correct me if I'm missing something here. Thanks in advance!

It is also possible to solve D in a greedy way without undoing your actions by using a $$$min$$$-Segment Tree and some precalculations. Keep an array that represents the last point from where you will be able do defend the $$$i-th$$$ castle ($$$l$$$) and another array that keeps the maximum amount of soldiers you can leave behind when you reach castle $$$i$$$ and still conquer all castles if you never defend a castle ($$$v$$$). To calculate it just iterate from castle $$$n$$$ to castle $$$1$$$ where $$$v[i] = min(v[i+1], S_{i} - a_{i})$$$ and $$$S_{i}=k + \sum_{j=1}^{i-1}b_{j}$$$. Append $$$S_{n+1}$$$ in $$$v$$$ and build the $$$min$$$-Seg from the nem $$$v$$$ (this is needed as we can defend using all soldiers in the last castle). Now just iterate over the castles from the most valuable one to the least valuable and if $$$query([l[i], n+1]) > 0$$$ we can take this castle and apply $$$update([l[i] + 1, n+1], -1)$$$, else we can just continue, as taking the current castle over a previous one would either make no difference in our answer or worsen it. $$$O(nlogn)$$$ complexity as well.

Can someone tell me why the dp solution of problem D won't get TLE, i think in the in the for loop, the complexity is O(n*n*n). Thanks in advance. 67195351

Idea for $$$O(M^2)$$$ for problem F:

You don't actually need two binary searches for the problem 1271E - Common Number. Let $$$S_x$$$ be the set of numbers that have $$$x$$$ in their paths and $$$ count(x)=|S_x|$$$. For example $$$S_4 =$$$ { $$$4, 8, 9, 16, 17, 18, 19...$$$ } . Clearly, for every odd number $$$x$$$ (except $$$1$$$)

$$$x$$$ has $$$x-1$$$ in its path.

$$$\implies$$$ all of the $$$count(x)$$$ numbers of $$$S_x$$$, has $$$x-1$$$ in its path.

$$$\implies$$$ $$$x-1$$$ appears in more numbers' path than $$$x$$$ does i.e. $$$count(x-1)>count(x)$$$

On the other hand, it can be seen that for $$$x$$$ is even and $$$x>2$$$, $$$count(x)\leq count(x-2)$$$. The $$$k^{th}$$$ element of $$$S_{x-2}$$$ is always less than the $$$k^{th}$$$ element of $$$S_x$$$. You can observe it from the pattern of the elements of $$$S_x$$$, as $$$S_x[k]=2*S_x[\frac{k}{2}]+$$$[$$$k$$$ is odd]. So, using this information, we can iterate over only even numbers as $$$x$$$ using binary search to find the largest $$$x$$$ such that $$$count(x)\geq k$$$, and check whether $$$count(x+1)\geq k$$$ as well. This essentially deals with the odd numbers' binary search as well.

To find the $$$count(x)$$$ for any given $$$x$$$, notice the pattern of $$$S_x$$$. It's almost like a binary tree. So you know the number of nodes in every level and the highest labeled node. Whenever that gets $$$>n$$$, just take the trimmed portion of the level.

My contest time submission: 66958024

In fact, F can be solve in $$$O(M)$$$. It's easy to know my AC code is run in $$$O(M)$$$.

Problem D is great:) But the description can be reduced???

Problem D: My code got accepted but failing at following testcase:

https://codeforces.com/contest/1271/submission/67515586

3 2 1

0 0 20

0 0 10

0 0 5

2 1

3 1

Did I miss any constraint?

In Problem D according to editorial it is optimal to defend the castle i with latest possible castle x but what if we are not able to reach castle x ?In that case we will miss the castle i .someone help please

In problem D according to the editorial it is always optimal to defend castle i with the latest possible castle x, but what if we are not able to reach castle x? In that case we will miss the castle i .someone help please.