### BledDest's blog

By BledDest, history, 10 months ago, translation,  Tutorial of Codeforces Round #608 (Div. 2) Comments (30)
 » Finally, the editorials are out.
 » Has any one solved the problem E like the tutorial? Please post your code.
•  » » https://codeforces.com/contest/1271/submission/66973530 I probably overcomplicated it, but there you go :)
•  » » You can see my comment below.
•  » »
•  » » https://codeforces.com/contest/1271/submission/67491916 check this one
 » And how about the challegne of problem F? Can anyone guide me?
 » Can someone explain the other solution to E ? I saw many solutions which did not use the binary search idea. For example neal submission
•  » » https://codeforces.com/blog/entry/72164?#comment-565091I think he also used the same technique as neal used.So you can refer to his submission
•  » » I don't think this problem should use binary search, and I can't understand how to use it.https://codeforces.com/contest/1271/submission/66962068
 » Can Any one give a Dynamic Programming Solution with explanation for Problem B? Thanks in advance
•  » » dp[i][j] = maximum answer if we start from city i and have j soldiers We first store what cities last city are the city i, and sort them by array c. so we can now choose how many of them we want to defend. my submission==> https://codeforces.com/contest/1271/submission/67000853
•  » » » Thanks for your efforts ... but i need Problem B ... not D ^_^
•  » » » It will be very helpful if you can briefly explain the dp transitions, I tried a lot but not getting it.
 » 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!
•  » » If you decide to defend city $i$, then at the end you'll have one warrior less than you would have had if you had decided not to defend the city. Now the question is, at what point will you lose this one warrior? You would definitely want to lose it as late as possible, so that this warrior might prove to be of some use between the city $i$ and the city ($x$) from which you sent this warrior.
 » 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.
•  » » bro i used similar technique but getting wrong answer. I used BIT , 1)->after storing the maximum difference between the total warriors available and warriors needed at index i in an array(called 'dp').2)->Then from right end I stored the minimum value at index i present to the right of that index and including that index in 'dp' array.So for this(Test case 5) example my dp array would look like this:5 5 0. 0 1 1738. 0 1 1503. 0 0 4340. 0 1 2017. 0 2 3894.'dp' array = 0 1 2 2 3 and ith element shows how many defended castles we can have before that.Now i used 'set,greater>> s' to store the gains at index i in decreasing order. So we traverse the set and check whether this castle index can be defended at later stage or not(we take the maximum index if possible).Now we check whether the prefix sum if smaller than dp[i+1].If possible then we update in BIT and add the gains to 'sum' variable. But I am getting wrong answer,pls help.
 » 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
•  » » 10 months ago, # ^ | ← Rev. 2 →   Yeah, I had the same confusion. So, if you look at the loop $fore(k, 1, N)$, you enter that loop only if $last[j] == i$ i.e. only if the last portal of the $j^{th}$ castle is in $i^{th}$ castle. In other words, in the worst case, the loop runs only once for each castle making it $O(n^2)$.
 » Idea for $O(M^2)$ for problem F: SpoilerIterate on the number of students of type 1, and the total number of students of type 2, 3 and 5. This will result in all inequalities being reduced to the form of either a single variable on one side, or the difference of two variables on one side, and a constant on the other. Even better, the inequalities will form three sets which can be solved independently, and this can all be done in $O(1)$.
 » 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???
 » 10 months ago, # | ← Rev. 8 →   Problem D: My code got accepted but failing at following testcase:https://codeforces.com/contest/1271/submission/675155863 2 10 0 200 0 100 0 52 13 1Did I miss any constraint?
 » why cant answer of problem E always be 1
•  » » oh he want the maximum sorry
 » Can anyone explain me the approach of problem B in the tutorial?