Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

awoo's blog

By awoo, history, 22 months ago, translation,

1455A - Strange Functions

Idea: BledDest

Tutorial
Solution (Ne0n25)

1455B - Jumps

Tutorial

1455C - Ping-pong

Idea: Neon

Tutorial
Solution (Ne0n25)

1455D - Sequence and Swaps

Idea: BledDest

Tutorial
Solution 1 (BledDest)

1455E - Four Points

Tutorial

1455F - String and Operations

Idea: Neon

Tutorial
Solution (Ne0n25)

1455G - Forbidden Value

Idea: MrPaul_TUser и BledDest

Tutorial
Solution (pikmike)

• +66

 » 22 months ago, # |   +41 When was the last time problem ratings were updated ?
 » 22 months ago, # |   0 Can someone explain those function proof in a simple way in C ques.
•  » » 22 months ago, # ^ |   +5 It looks too complicated. My thinking was slightly different. Since A has to start and make the first turn, she doesn't have options. B decides in this case if he wants to hit or miss. And since B wants to maximize his score, the maximum what he could get is if he misses everything from A and then with A having 0, he would able to get y points (it's impossible to get more) and A will have x points. But also as they want to minimize their enemy's scope as a second parameter, there is no need for B to miss everything, he could hit the last ball from A (A will have 0 energy already) so she will waste this point and B will get it. And in this case A will have (x — 1) and B will have y points. There is no better option for B because if he hits any ball except the last one A should respond not to loose her point. In this case B won't have maximum possible score.
•  » » » 22 months ago, # ^ |   0 Thanku i get it.
•  » » » 22 months ago, # ^ |   0 well that quite abrupt way to play the game. Anyway it is what it is. Great logic
•  » » » 22 months ago, # ^ |   0 Comments section is always Better than the editorial.
 » 22 months ago, # |   0 Problems A,B and C were simpler than Editorial.
 » 22 months ago, # |   0 can anyone help me understand problem B?
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 I thought it like that , simply go on with the process and keep adding 1 , 2, 3 ... until it is greater than or equal to required point , we will figure out what is going to subtract from our answer. If after the process we end with equal numbers, then simply the no. of steps is the answer , but in other case if it is greater thenif difference between them is 1 , then we can't subtract anything from it , because minimum step that we can do in backward direction is 1 , which will affect our answer by two( -1 because of the step and -1 because we are removing the 1st step). So , we have to go one step more.But if diff is greater than 1 , then notice we can compensate any difference , for ex if diff is 2 we can remove step 1 and we will get -2 , and if we remove 2nd step , then we get -3 and so on.so conclusion is , if at the end diff is 1 then we need one extra step , but in any other case ans is the no. steps we took until we reached our req. point or crossed it.
•  » » » 22 months ago, # ^ |   0 thanks for the help!
•  » » » 22 months ago, # ^ |   0 exact to the point +1
•  » » » 22 months ago, # ^ |   0 finally, thanks sourabh!
•  » » » 22 months ago, # ^ |   0 I kinda got it but i'm still a little confused, thanks for the help btw.
•  » » » 19 months ago, # ^ |   0 thanks
 » 22 months ago, # | ← Rev. 2 →   +117 I have an interesting solution (100067011) to problem E, involving minimum cost circulation. It might not be the best solution, but it involves no casework or geometric insight, and it might be educational in helping you approach other problems.First, I iterate over all permutations of the points, so let's assume $p_1$ will end up as the bottom left point of the square, $p_2$ the bottom right, $p_3$ the top left, $p_4$ the top right.For each point, let's create two variables $dx_i$ and $dy_i$, so that point $i$ should end up at position $(x_i+dx_i, y_i+dy_i)$. Then the objective is to minimize $\sum_i |dx_i|+|dy_i|$.Now, we need to set up the constraints so that the points will make a square. To make sure it's a rectangle, we need $x_1+dx_1=x_3+dx_3\tag{A}$ $x_2+dx_2=x_4+dx_4\tag{B}$ $y_1+dy_1=y_2+dy_2\tag{C}$ $y_3+dy_3=y_4+dy_4\tag{D}$To make sure it's a square, we need the side lengths to be equal. That is, $(x_2+dx_2)-(x_1+dx_1)=(y_3+dy_3)-(y_1+dy_1)\tag{E}$At this point, I noticed that each variable appears in at most 2 constraints, which reminds me of the constraints of a flow problem. I also notice that we can add a new (redundant) constraint to make each variable appear in exactly two constraints: $(x_4+dx_4)-(x_3+dx_3)=(y_4+dy_4)-(y_2+dy_2)\tag{F}$The equations can be interpreted as $\mathrm{flow\_in}_u=\mathrm{flow\_out}_u+\mathrm{demand}_u, \quad u\in \{A,B,C,D,E,F\}$where our variables $dx_i$ and $dy_i$ are undirected edges. And the cost of this flow is exactly what we seek to minimize. •  » » 22 months ago, # ^ | ← Rev. 2 → +54 I really want to understand this solution to the full extent. I understood up to (F) but am not sure 1) why two constraints should remind someone of a flow problem, 2) how to go from the equations to the flow graph, and 3) (the hardest/crucial part) why this graph solves the problem correctly. I am not the strongest in flow problems so understanding this unique solution in detail may prove very beneficial to me and hopefully others! •  » » » 22 months ago, # ^ | +80 1) why two constraints should remind someone of a flow problem The constraints of a flow problem are that for each node, the incoming flow equals the outgoing flow. So each edge $(u, v)$ is involved in $u$'s constraint as the outgoing flow, and in $v$'s constraint as the incoming flow. So if each variable appears in at most two constraints, it's a strong indicator of a flow problem. 2) how to go from the equations to the flow graph The nodes represent the constraints, so $A,\ldots, F$ are the nodes. To force it into the $\mathrm{flow\_in}_u=\mathrm{flow\_out}_u+\mathrm{demand}_u$ framing, we need the following: $\mathrm{flow\_in}_u$ and $\mathrm{flow\_out}_u$ should be sums of variables $dx_i$, $dy_i$. $\mathrm{demand}_u$ should be an exact value from the input of the problem, involving $x_i$, $y_i$. Each variable $dx_i$ and $dy_i$ should appear once as $\mathrm{flow\_in}$ and once as $\mathrm{flow\_out}$. So I will rewrite the equations like this. $(dx_1) = (dx_3) + (x_3 - x_1)\tag{A}$ $(dx_4) = (dx_2) + (x_2 - x_4)\tag{B}$ $(dy_2) = (dy_1) + (y_1 - y_2)\tag{C}$ $(dy_3) = (dy_4) + (y_4 - y_3)\tag{D}$ $(dx_2+dy_1) = (dx_1+dy_3) + (x_1+y_3-x_2-y_1)\tag{E}$ $(dx_3+dy_4) = (dx_4+dy_2) + (x_4 + y_2 - x_3 - y_4)\tag{F}$From here, the graph and demand values follow. An edge connects the two letters that involve it in the constraints. Now, $dx_i$ and $dy_i$ can be positive or negative, so they are actually undirected edges in the flow graph, but we still needed to set the equations up as incoming/outgoing flows. This ensures the sign of the demands are correct, and that the constraints really do correspond exactly to a flow graph. 3) (the hardest/crucial part) why this graph solves the problem correctly The constraints we set up are satisfied if and only if the points end up in an axis-aligned square. Our objective is exactly the cost of moving the points, and exactly the cost of a circulation in our flow. We know there is an optimal circulation where all values are integers. •  » » » » 22 months ago, # ^ | +8 Thanks for such a detailed explanation! After doing some research does this problem relate to linear programming at all? Because the way I understand flow problems (max flow min cut) is that you have a source and sink node with predetermined constant capacities on each edge. Maybe I am misunderstanding the graph that you created but I do not see any source/sink or how one could use flows to support unknown capacity on each edge? Or how a node represents an equation?If you/anyone has resources for problems very similar to this with solutions (I could not find any but maybe I am searching the wrong thing) that would also be helpful. Thanks! •  » » » » » 22 months ago, # ^ | +21 It relates to linear programming in that I approached the problem by setting it up as LP, then noticed it's a special case and can be solved with flow.You're right that I didn't mention a source or sink. That's because it's a circulation graph. You should read about circulation and how it reduces easily to min cost max flow, with an added source and sink. •  » » » » » » 2 months ago, # ^ | 0 I can understand your solution. However, I use Dinic instead of MCMF and still get correct answer(see my 167564314), which means that I even not take care of cost! I don't know why it is correct, it is amazing! •  » » » » » » » 2 months ago, # ^ | +8 Dinic's algorithm works by always selecting the augmenting path with the fewest edges. It turns out that a path of min number of edges happens to be equivalent to min sum of weights for this particular example, so Dinic's will work here.(You can see that all edges are weight $1$ except the edges from source and to sink, but we have to take exactly $2$ of those anyway. That's why min edges = min cost here.)  » 22 months ago, # | -18 why we r getting tutorial so late  » 22 months ago, # | ← Rev. 3 → +18 I thought that $O(tn^2)$ would not pass for problem F so I have a $O(tnk)$ solution. It is basically the editorial solution except we only keep the last 3 characters of our string, ensuring that all characters before that is of the optimal solution.code (very ugly): 100144988I think this can possibly be improved to $O(tn)$.Edit: 100146367. Yea there is a $O(tn)$ solution.  » 22 months ago, # | 0 Problem B:(My opinion)We keep adding 1,2,3....until it is greater than or equal to 'x'.In this way, suppose we are at position 'y' with 's' steps.Now, (x==y) it is easy to determine the ans is 's'.in other case we can also go '0' to 'x' with 's' steps if we can jump back at {(y-x)-1}th step.suppose x = 18y=21->1+2+3+4+5+6(with 6 steps)If we jump back at {(21-18)-1} or 2th step we will be at 18.x=18->1+(-1)+3+4+5+6but {(y-x)-1} = 0, which means we need to jump back at 0th step which is irrelevant.This time we need to go 'y' with 's' steps and then jump back.Thus the ans will be (s+1).  » 22 months ago, # | +59 On Problem E The first approach is to note that either both x1 and x2 coincide with some (pi.x)-s and y1 coincide with one of (pi.y) or both y1 and y2 coincide with some (pi.y)-s and x1 coincide with one (pi.x). WHY?????? •  » » 22 months ago, # ^ | ← Rev. 3 → 0 Same question! Does it have something to do with median? Like it will only be median points to generate smallest distance. •  » » 22 months ago, # ^ | ← Rev. 3 → +38 The way I came to that conclusion is the following. First, we have to fix something. Let's start by proving there is some $x$ in the input such that it's one of the optimal lines. For the simplicity, let's fix the permutation of points beforehand and prove for it.Let the square side be some length $a$. So we have found some optimal square such that neither of the original $x$ are in there. If it is entirely to the left or to the right of all points then you surely can move it closer and the cost decreases. Otherwise, what's the cost of moving the square one to the left or one to the right? It's basically some linear function on (number of points to the left of each $x$) and (number of points to the right of each $x$). Also, that cost is constant until we reach any of the original points while we move it. Moreover, moving to the left costs exactly the same as moving to the right but negated. So if the cost is non-zero, then we can at least move the square to the side where the function is negative and obtain a smaller cost. If it's zero then you can still move to any side and the cost won't change. So move until you hit some $x$. Thus, there always exists a square of side length $a$ such that it costs less than or equal than our assumed answer.Same proof goes for some $y$. You can notice that this proof relies only on one coordinate, so you can move any square of any side length independently on each coordinate. Thus, we've proven that there is some $x$ and some $y$ in the original input that is optimal for any side $a$.Now, let's fix some $x$, some $y$ and some permutation of points. Let $(x, y)$ be the lower left corner of the square. Cut the grid by all $x$-s of the input and all $y$-s of the input. Let the upper right corner of the square be between some $x_1$ and $x_2$ and between some $y_1$ and $y_2$. Notice that the cost to move the upper right corner by one by both $x$ and $y$ simultaneously is constant inside the entire rectangle between $x_1$ and $x_2$ and between $y_1$ and $y_2$ (basically, the same as in the first proof). Shrinking the square costs a negated price of expanding it. Thus, we can keep shrinking or expanding (choose the one that's non-positive) until we hit a border of the rectangle $x_1$/$x_2$, $y_1$/$y_2$. So we hit it and the cost has been decreasing (or staying the same) all the way to some $x$ or $y$ on the border of the rectangle. Thus, we came up to the conclusion that there's also some $x$ or $y$ besides the original $x$ and $y$ we fixed that is optimal. Apply the same proof to $(x, y)$ being any corner of the square and you got yourself a full proof.hujc, Whistleroosh, here you go. •  » » » 22 months ago, # ^ | 0 I understand this explanation!!Thank you very mach!!! •  » » » 22 months ago, # ^ | 0 Thank you so much!! •  » » » 22 months ago, # ^ | 0 Thank you for explanation •  » » » 21 month(s) ago, # ^ | 0 wow, that's a really nice proof.I really like how this proof is similar to the proof of the fact that the cost of moving all points (in one dimension) to a common point is minimum when the common point is the median of all the points. But this is of course in two dimensions. Cool! •  » » » 16 months ago, # ^ | 0 thank you so much, nice explanation!!  » 22 months ago, # | 0 Can someone explain to me question 5?  » 22 months ago, # | ← Rev. 3 → +13 My solution for Problem D is simpler, check it out: 100115447 •  » » 22 months ago, # ^ | 0 can you explain it a bit here? I am not able to understand the editorial completely. •  » » » 22 months ago, # ^ | 0 My solution for problem D is next: First because you only have n numbers and 1 x variable if you add them all to one array and sort it you will have n+1-element sorted array. And you know that if a solution exists for the problem when you do it you will get a n-element sorted array(if you have 1 2 3 5 4 and x = 0 you know that when you do the least possible switches you will get one of the following: 0 1 2 3 4, 0 1 2 3 5, 0 1 2 4 5, 0 1 3 4 5, 0 2 3 4 5, 1 2 3 4 5, and you can see that our n+1-element sorted array is 0 1 2 3 4 5 so those possible answers are nothing more than this array without one of its elements).So we can try to match the starting array 1 2 3 5 4 to any of those arrays created from our n+1-element array and save the minimum switches you needed to make for each try.So how to calculate the number of switches for each try? just look at each one of the elements from left to right and if they dont match then you need to switch your current x with that element(if you dont you wont be able to do it later because all the other numbers are bigger or equal to that one) so if x < current number that needs to be switched with x we switch them and we do that until we end with iteration(that means we equalised the arrays so we found number of switches for that array) or until we need to switch the number that is greater than x(that means, in this iteration, we cant sort it in which case the answer is -1).Here is a solution if you dont get what im saying 100264317 •  » » » » 22 months ago, # ^ | 0 •  » » » » » 22 months ago, # ^ | +1 Your solution is great, it's also memory-wise efficient than mine. •  » » » » » » 22 months ago, # ^ | 0 Thanks man, really appriciate it. •  » » 22 months ago, # ^ | 0 Thanks a lot for sharing your solution! it helped me a lot  » 22 months ago, # | 0 The proof of C is really interesting but I just can't accept the fact that the solution is one line. •  » » 22 months ago, # ^ | +5 I thought of it this way. Since Bob can atmost hit y shots, the maximum score he can have is y. Then I formulated the strategy for how Bob can always achieve that maximum score. I too was really surprised on finding a O(1) solution. •  » » » 22 months ago, # ^ | ← Rev. 2 → 0 Nice way to look at it. I saw that Bob can always score y but at first I thought that Alice can also always get x until I saw the samples.Oh, and I it was crucial that they don't want to win but to maximize their score and after that minimize the opponent's score.  » 22 months ago, # | 0 I have a question...!in problem E. Four Points,it is noted that a square with side 0 is allowedso for the 2nd test case in the example, why not making four points as (2,0), (2,0), (4,0), (4,0), which makes the output 3 ? •  » » 22 months ago, # ^ | 0 This is a line segment with length 2, not a square. •  » » » 22 months ago, # ^ | 0 I thought a square with side 0 means the side with the length 0, so then what's the difference between a square with side 0 and a line ? •  » » » » 22 months ago, # ^ | 0 The length of the line from a square must be the same. So we can assume that a square with side 0 has four line whose length is 0, which actually is just a single point.However, we can assume that a segment with length 2 not only has side 2, but also has side 0.So it isn't a square. •  » » » » 22 months ago, # ^ | +7 According to Wiki (and all dictionaries I saw), a square "has four equal sides". If a square has a side equal to 0 then all his sides are equal to 0, i. e. it's a point — not a segment. •  » » » » » 22 months ago, # ^ | 0 I see. I misunderstood between square and rectangle... like what you said, a square with side 0 should be a point.Thanks a lot...! @mcqueen1, @adedalic •  » » 22 months ago, # ^ | ← Rev. 2 → 0 In fact, (2,0),(2,0),(4,0),(4,0) cannot form a square with side 0.Four points which can form a square with side 0 must be the same with each other completely.For example, (2,0),(2,0),(2,0),(2,0) can form a square with side 0.Hopefully, my answer will help you.(Sorry for my poor English.)  » 22 months ago, # | 0 can someone elaborate the DP solution for problem D?? •  » » 22 months ago, # ^ | 0 Because of the observations mentioned in the editorial, we can go in increasing order of indices, and keep taking decisions on whether to make the switch or not.Let $dp(i, prev, cx)$ represent answer for $a[1...i]$ sorted prefix where number put on the $i^{th}$ index was $prev$ and now we are deciding what to do on the next index with value of $x$ equals $cx$. Now we can either let the value of $a[i+1]$ stay the same (possible only when $prev <= a[i+1]$ ): $dp(i+1, a[i+1], cx) := min(self, dp(i, prev, cx))$ Or we can actually swap $a[i+1]$ with $cx$ (when $prev <= cx$ and $cx < a[i+1]$ ) with the following transition: $dp(i+1, cx, a[i+1]) := min(self, dp(i, prev, self) + 1)$ To optimise space complexity, dont store dp table for all the indices. Store them only for the current and the immediate-next index.My Code: 100219452 •  » » 22 months ago, # ^ | ← Rev. 2 → 0 100731689 Here is a simpler version of code. Thanks iprakhar22, for idea. •  » » » 16 months ago, # ^ | 0 can you please explain your approach, i didnt get it..  » 22 months ago, # | 0 In E what is the proof for the statement that: - either both x1 and x2 coincide with some (pi.x)-s and y1 coincide with one of (pi.y) - or both y1 and y2 coincide with some (pi.y)-s and x1 coincide with one (pi.x)?  » 22 months ago, # | ← Rev. 2 → -9 On problem B : the sum of natural numbers S=1+2+3+4+..n. If we remove any of the term and replace it by -1 then S will reduce by (ith term +1). So for any natural number sum we can reduce the sum by -2(by replacing the first term), -3 (by replacing the second term and so on). We cannot only reduce the sum by -1 by replacing extra steps. So its better to find the closest natural numbers sum just greater than the input and if the given number is less by 1 then one extra step is required or else no extra step is required. here is my solution 100082004  » 22 months ago, # | ← Rev. 2 → 0 Hi MikeMirzayanov The last 6 or 5 contest doesnt have difficuty tagPlease correct it  » 22 months ago, # | 0 How to solve D with $O(n^2)$ DP?  » 22 months ago, # | 0 Please can anyone better explain the Problem D i am unable to understand the editorial. •  » » 22 months ago, # ^ | 0 •  » » » 22 months ago, # ^ | 0 Dude you gotta change you profile picture ! ! ! there can be only one !  » 22 months ago, # | 0 Can anyone tell me why am i wrong ? :'< https://codeforces.com/contest/1455/submission/100029658 •  » » 22 months ago, # ^ | +1 Yeah i had same problem, consider the following portion of test 4 for which you have done computation for previous input and while iterating through 42 42 43 46 44 45 46 48 48 48 62 51 51 you will have x=46 while iterating you are counting 48 three times while you require only one swap so that accounts for 2 extra moves in your answer.You can refer to my code on same logic in O(n) https://codeforces.com/contest/1455/submission/100248902 •  » » » 22 months ago, # ^ | 0 Omg thank you so much, i get it! >.<, I hope u can reach high rate in next contest, people like you deserve it ^^ •  » » » » 22 months ago, # ^ | 0  » 22 months ago, # | 0 work out a good solution for D.100057578  » 22 months ago, # | 0 Thank you so much!  » 22 months ago, # | 0 question c, shortest code till date !!  » 22 months ago, # | 0 Although the intended solution for problem D wasnt dp but since I saw that it can be solved using dp I gave it a try and I have solved it using recursion. But I couldn't find any recomputation of subproblem so I removed the memoization and the solution works just fine . I want to ask whether it is because the test cases were too small or I am missing any test cases which may have recomputations which need memoization . Correct me if I am wrong My solution : https://codeforces.com/contest/1455/submission/100313636  » 22 months ago, # | +3 For 1455E - Four Points I want to describe other solutions. In my opinion they are easier to understand. Yet another wall of textFirst one, which I came up during round but didn't polish enough is following.Trying to find out where square should be is mess if you know nothing. So, lets assume we know which point goes where. I'll use word "go" and think about points as walking. Now it's easy to calculate total distance traveled by each point. Let's say $x,y$ are coordinates of one corner and $w$ is width of square, so all coordinates of points is simply $(x,y),(x,y-w),(x-w,y),(x-w,y-w)$. Then, separate coordinates, and total distance by x coordinate is: $|x_1-x|+|x_2-x|+|x_3-(x-w)|+|x_4-(x-w)|$. Similarly, total distance by y coordinate is: $|y_1-x|+|y_2-(y-w)|+|y_3-y|+|y_4-(y-w)|$. With this two formulas we can start analyze.First, we see that both formulas are sums of abs functions. Second: we see three unknowns. Third: for fixed $w$ you can minimize both separately. Suppose you know $w$, then how to find out best $x$ and best $y$? Hypothesis: best x is among $x_1,x_2,x_3,x_4$, similarly for $y$. Looks promising. What about $w$? Well... I need to argue why hypothesis about best $x$ and $y$ is like this. This is because $|x_1-x|$ reach minimum when $x = x_1$, because $|x_1-x_1|=0$. Similarly $|x_2-x|$ reach minimum when $x=x_2$, so intuitive candidates for minimum sum is when some of operands is minimum. Applying same argument regarding $x$ we wee that $|x_3-(x-w)|$ should turn into zero, and it's when $x_3-x+w=0$ or $w = x-x_3$. But by our previous hypothesis $x$ should be among $x_1,x_2,x_3,x_4$, so this makes us think that $w$ should be some difference between coordinates.Trying to submit solution like following: try all permutations of which point goes where, then for each permutation try to make points $(x,y),(x,y-w),(x-w,y),(x-w,y-w)$ using all four $x$, and all four $y$, and try $w$ to be every difference between x coordinates or y coordinates. WA2. Why? Well... Just because of little ignorance. We should notice that $|x_3-(x-w)|$ becomes zero when $x = (x_3+w)$, so among candidates for best $x$ we should also try $x_1+w, x_2+w, x_3+w, x_4+w$. Similarly for $y$. AC! 100123201Proof! Again we fix which point goes where. And again we analyze formulas: $|x_1-x|+|x_2-x|+|x_3-(x-w)|+|x_4-(x-w)|$ and $|y_1-x|+|y_2-(y-w)|+|y_3-y|+|y_4-(y-w)|$. Second formula is similar, so focus on first one. Imagine plot of function $|x|$, it's just two infinite line segments meeting at point zero. How about $|x+C|$ where C is some constant: it is again two line segments meeting this time at coordinate $(-C)$. What if we add two functions like that? We get at most three segments. But main point here is: we still get line segments! Thus, any sum of functions like that is set of line segments with points located at corresponding $(-constants)$. Where minimum of function like this can be achieved? only at one of points. Our function for fixed $w$ has this kind of plot. So minimum of it for fixed $w$ is determined by constants. Similarly, our function for fixed $x$ has this kind of plot, and best $w$ determined by constants.Now, most tricky part. We can't say that "we have just sum of functions, so we need pick best candidates for each variable", or may be you can but I don't know why. So, instead we prove by contradiction. Suppose best solution is $(x,y,w)$, then look at formula of travel distance by coordinate $x$. For fixed $w$ we know candidates for which it may take minimum. If one of points is better, then take it and we have better answer and we have contradiction. Otherwise we can change $x$ to one of candidates and total cost will be same. Similarly for $y$. Now we have $x,y$ from our candidates. All we have to show now is that $w$ is also from our set. Candidates for $x$ is $x_1, x_2, x_3+w, x_4+w$, for $y$ is $y_1, y_2+w, y_3, y_4+w$. I won't describe each case, they are similar. Suppose that candidates we get is $x_1,y_2+w$. For $x$ coordinate candidates for $w$ are $x_1-x_3$ and $x_1-x_4$. For $y$ coordinate candidates for $w$ are $y_1-y_2,y_3-y_2$. Most difficult right now to realize, that sum of both formulas for coordinates for fixed kind of (x,y): in this case it is $(x_1,y_2+w)$ resulting formula still line segments with points with $w$ at positions $x_1-x_3,x_1-x_4,y_1-y_2,y_3-y_2$ and for any $(x,y)$ of form $(x_1,y_2+w)$, best $w$ is among $x_1-x_3,x_1-x_4,y_1-y_2,y_3-y_2$, or at least not worse. Similarly any other case.And, as you can see from proof, for each permutation you can pick crafted shorter list of candidates: only those values which can take best for this permutation. It is not dramatically better. For each $x$ candidate there is two $w$ candidate, same for $y$, then candidates unite, so for each $(x,y)$ candidate there are four $w$ candidate. 4*4*4 variants for each permutation. 100217389Now, second solution. Take a look at formula for one coordinate. If we open brackets we will get $|x_1-x|+|x_2-x|+|x_3-x+w|+|x_4-x+w|$. You can rephrase this formula as: what if there four people standing at coordinates $x_1,x_2,x_3+w,x_4+w$. It's classic problem, and solution is to take median. Why? imagine they meet at some point $x$, then if we move meeting point x to the right, each one from the right should move 1 less, and each from the left should move 1 more, so you can do better if from the right is more people than from the left. Also you can do better by moving meeting point to the left if from the left there are more people than from the right. So, the best is when number of people from the left is equal to number of people from the right. It's achieved if you're at median. Or, if there are even number of people: at any of "two medians".Now, suppose we have people at $x_1,x_2,x_3+w,x_4+w$ and $w$ is initially equal to zero. Then, repeatedly pick median and increase $w$ each time. Median can only change when one point goes over other point. It happens when $x_3+w = x_1$ or at $x_3+w=x_2$ and so on. First equation is when $w = x_1-x_3$ — again, difference between two of $x$. Thus, medians can change only at those $w$. Hypothesis: only those $w$ are candidates for best $w$. How to prove without proof above? I don't know. At least I show how we can get this intuition. Anyway, for each permutation we can try each $w$ and use median to find $x,y$. 100106479  » 22 months ago, # | ← Rev. 7 → 0 Hello everyone, I meet a very very strange problem when i am trying to solve 'Problem G'. ⁣At first, I commited this code 100780041, and the result was 'Wrong answer on test 11'. The reason to lead the WA is I used the erase(x) method of multiset to delete one item, but obviously I deleted all the items valued x. ⁣So I replaced this wrong applying with multiset.erase(multiset.find(x)) which only will delete one item valued x. But I got the TLE!!! on test 5!!! 100780082 ⁣In theory, these two ways have the same time complexity. So I am so confused that having to ask someone else to help me have a look. ⁣Thanks. The differents of two code: 28c28 < s.erase(m[k]); --- > s.erase(s.find(m[k])); 39c39 < s.erase(m[k]); --- > s.erase(s.find(m[k])); 69c69 < costset[x].s.erase(xv - xoff); --- > costset[x].s.erase(costset[x].s.find(xv - xoff)); 136a137 > // s.erase(s.find(x));  •  » » 22 months ago, # ^ | 0 And because the contest is finished for a little long time, I probably knows maybe little people focus on this. So, may I please ask you for help? awoo •  » » 22 months ago, # ^ | 0 OK，I got it! In line 113 costset[rt[End[i]]].remove(y[i]);, I will erase a item valued x that can not exist. So when I use multiset.erase(multiset.find(x)), the inner return of find method will return multiset.end() that can cause the TLE when I erase it.  » 22 months ago, # | 0 Problem B can be solved in $O(t)$ time. (100963724)(Editorial solution is $O(\sqrt{x}\cdot t)$ I believe)For each test case, we can calculate the lower bound of $n$ as n = int( 1 + floor(sqrt(1+8*x) ) // 2 - 1 You arrive to this by solving for $n$ in Baby Gauss' formula. $x=\frac{n(n+1)}{2}$ $n=\sqrt{2x+\frac{1}{4}}-\frac{1}{2}$The code is a little different, in that I multiply and divide the square root by 4 in order to deal with integers and not worry about floating point errors. And of course we take the floor to get the lower bound.This implies that our inputx\$ is between $x_1$ and $x_2$. x1 = (n * (n+1)) // 2 x2 = ((n+1) * (n+2)) // 2 Finally, by the same logic as explained in the editorial. if(x == x1): print(n) elif(x2 == x+1): print(n+2) else: print(n) If our $x$ is the lower bound, we output the $n$ of the lower bound.In all the other cases, we can account for the difference between the lower bound and our input by taking one more number and changing another one for $-1$.The only exception being when the difference is $1$, in which case we have to take 2 more numbers, subtract one of them and add the other.I hope it's clear enough. It's my first time commenting. The only difference is that we remove the inner while loop.
 » 22 months ago, # |   0 Hello everybody, this is my first question here so wish me luck xDI submitted code for D problem here https://codeforces.com/contest/1455/submission/100985682 and the result was "Wrong answer on test 3". When i test with the same test case i get 3 as output, but when i submit it gives the 74 as output! Can anyone explain me how did it come about throwing out 74 or any other number greater than 3 instead of 3?
•  » » 21 month(s) ago, # ^ |   0 I also wrote the same wrong code as yours.In fact, in this method you need to check everytime if the suffix array is already sorted. It is only when the array is still not sorted that you need to do the swapping. (checking everytime can be done in O(1) or O(n), both will pass)
 » 21 month(s) ago, # |   0 It says wrong answer on test case 18. I cant find what am I missing out. Can somebody help please. https://codeforces.com/contest/1455/submission/102259323
 » 21 month(s) ago, # |   0 I can't understand asymptotics of my D solution. It has passed and it is none of authors solutions. https://codeforces.com/contest/1455/submission/102979769If someone can hack it or prove some good asymptotics, you're welcome.
 » 21 month(s) ago, # |   -7 When I saw this blog in Recent Actions, I initially thought "Who the hell is this awoo guy and why does he copy-paste our editorial blogs?"
 » 21 month(s) ago, # |   0 There can be many answers of problem C. What should we focus on?
 » 21 month(s) ago, # | ← Rev. 2 →   0 for the problem D,if all elements before it are smaller and elements after it are greater then the element is in sorted position.if an array is unsorted then x has to be there in the array. this observation will be used.cnt =0.for i from 1 to n,check every element a[i] for the following criteria:1) if array is now sorted then return cnt.2) if a[i] and x are candidate for position i then we have conditions: A) if swap can be done, swap them make add 1 to cnt and move to next element. (swap is done because subarray after i is not sorted and if greater element is assigned this position( which is arr[i] ) then x will be there in the subarray after i(the fact stated above) which will make array unsorted as a whole.) B) if swap cant be done then just move to next element. if a[i] is candidate for the position but x is not the candidate for the position: then just move to the next element. 3) if a[i] is candidate for the position but x is not the candidate for the position: then just move to the next element.4) if a[i] is not the candidate for the position but x is the candidate for the position: we have only one choice to swap them and add 1 to cnt and move to next element. if any other situation is encountered then say it is impossible.print cnt(BEING A CANDIDATE FOR A POSITION means all elements before it are smaller and all elements after it are greater.)