Reminder: in case of any technical issues, you can use the lightweight website m1.codeforces.com, m2.codeforces.com, m3.codeforces.com. ×

### BledDest's blog

By BledDest, history, 23 months ago, translation,

• +36

 » 23 months ago, # |   +15 Finally, the editorials are out.
 » 23 months ago, # |   0 Has any one solved the problem E like the tutorial? Please post your code.
•  » » 23 months ago, # ^ |   +2 https://codeforces.com/contest/1271/submission/66973530 I probably overcomplicated it, but there you go :)
•  » » 23 months ago, # ^ |   0 You can see my comment below.
•  » » 23 months ago, # ^ |   0
•  » » 23 months ago, # ^ |   0 https://codeforces.com/contest/1271/submission/67491916 check this one
 » 23 months ago, # |   0 And how about the challegne of problem F? Can anyone guide me?
 » 23 months ago, # |   +2 Can someone explain the other solution to E ? I saw many solutions which did not use the binary search idea. For example neal submission
•  » » 23 months ago, # ^ |   +1 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
•  » » 23 months ago, # ^ |   0 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
 » 23 months ago, # |   +4 Can Any one give a Dynamic Programming Solution with explanation for Problem B? Thanks in advance
•  » » 23 months ago, # ^ |   +1 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
•  » » » 23 months ago, # ^ |   0 Thanks for your efforts ... but i need Problem B ... not D ^_^
•  » » » 23 months ago, # ^ |   +1 It will be very helpful if you can briefly explain the dp transitions, I tried a lot but not getting it.
 » 23 months ago, # |   +1 Can anyone explain the count(x)>count(x+2) concept of the problem E?
 » 23 months ago, # |   0 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?
 » 23 months ago, # |   +1 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!
•  » » 23 months ago, # ^ |   +1 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.
 » 23 months ago, # |   +1 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.
•  » » 23 months ago, # ^ |   +1 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.
 » 23 months ago, # |   +1 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
•  » » 23 months ago, # ^ | ← Rev. 2 →   +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)$.
 » 23 months ago, # |   0 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)$.
 » 23 months ago, # |   0 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
 » 23 months ago, # |   0 In fact, F can be solve in $O(M)$. It's easy to know my AC code is run in $O(M)$.
 » 23 months ago, # |   0 Problem D is great:) But the description can be reduced???
 » 23 months ago, # | ← Rev. 8 →   0 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?
 » 18 months ago, # |   0 why cant answer of problem E always be 1
•  » » 18 months ago, # ^ |   0 oh he want the maximum sorry
 » 15 months ago, # |   0 Can anyone explain me the approach of problem B in the tutorial?
 » 5 weeks ago, # |   0 i can't see tutorial!. i can only see:-[problem:]Tutorial is not availble something like that.