### ilyakrasnovv's blog

By ilyakrasnovv, 5 months ago, translation,

Hello, Сodeforces!

We are very grateful for Your participation in our round.

Thanks to Qwerty1232 for the help with this editorial.

1715A - Crossmarket

Hint #1
Hint #2
Hint #3
Solution

1715B - Beautiful Array

Hint #1
Hint #2
Hint #3
Solution

1715C - Monoblock

Hint #1
Hint #2
Hint #3
Solution

1715D - 2+ doors

Hint #1
Hint #2
Hint #3
Solution

1715E - Long Way Home

Hint 1
Hint 2
Hint 3
Solution

1715F - Crop Squares

Hint #1
Hint #2
Hint #3
Solution

• +204

 » 4 months ago, # |   +41 TLE on D T.T
 » 4 months ago, # |   -35 Trash contest
•  » » 4 months ago, # ^ |   +4 no u
 » 4 months ago, # |   +17 Wow, such a fast tutorial!
 » 4 months ago, # |   +75 One of the best C
•  » » 4 months ago, # ^ |   +1 For experts or higher I guess
•  » » 4 months ago, # ^ |   +71 I don't think Monoblock's company is having many sales with such a complicated captcha.
•  » » » 3 months ago, # ^ |   0 XD
 » 4 months ago, # |   +8 Thanks for the really nice contest and also the editorial:)
 » 4 months ago, # |   +18 Though I couldn't perform as well as I expected, the contest and the problems were interesting :)
 » 4 months ago, # |   +59 I think convex hull trick is too complicated for div2 E, please don't add such tasks
•  » » 4 months ago, # ^ |   +76 You can also do it with D&C dp, I think this was a nice question. You learn these tricks but there aren't many "easy" questions on them because they are generally reserved for harder problems with more observation. This was a simple application and personally I got a nice Aha moment when realising I could use D&C, imo this way you get a chance to build an intuition for them
•  » » 4 months ago, # ^ |   +24 my hands finally knows about CHT by this task
 » 4 months ago, # |   +18 You can also solve E using Divide and Conquer DP because of the square cost functionMy submission
•  » » 3 months ago, # ^ |   0 can you elaborate on the divide and conquer dp?
•  » » » 3 months ago, # ^ |   +8 The objective of the D&C was to calculate the minimum distance after a flight(assuming the flight just landed at some point), so you have a set of distances you got from dijkstra in $dp$_$old$, then you calculate post flight distance for $i$, aka $dp$_$new[i]$ as $min_j (dp$_$old[j] + (i-j)^2)$I divided this up into two parts$min_{ji} (dp$_$old[j] + (i-j)^2)$ Both of these are what I solved using D&C DP, followed by more Dijkstra to calculate travel via roads
•  » » » » 3 months ago, # ^ |   0 nice get the divide and conquer now, using the optimal to cut up the array was cool wouldn't have thought of that
•  » » » » 3 months ago, # ^ |   0 Can you elaborate how to solve one of those partial minimums? I was able to do that only with some crazy math.
•  » » » » » 3 months ago, # ^ |   0 Let $opt[i]$ be the index $j, j  » 4 months ago, # | 0 Can someone explain the Convex Hull Trick mentioned in E? I can't figure a way to calculate the minimum for each node without iterating over all other nodes to get$d_{new}[v]$•  » » 4 months ago, # ^ | 0 Its a somewhat advanced DP optimisation trick that allows you to optimise dp of the type$dp[i] = max_{j
•  » » 4 months ago, # ^ |   0 You can also use Li Chao tree (it is just advanced segment tree) Both are data structures that allows you to find minimum/maximum of linear functions' values in O(log(n))
 » 4 months ago, # | ← Rev. 2 →   +40 For D, another solution is to simply build the answer from left to right, choosing the minimum value of $a_i$ each time.To do this, first we need to restrict which bit of each $a_i$ can be $1$. This can easily be done by looping through all the condition $(i, j, x)$: If the $k$-th bit is $0$ in $x$, then it must be $0$ in both $a_i$ and $a_j$. Let call $allowed_i$ the number that has all allowed 1-bit of $a_i$, then we can see that $a_i = allowed_i$ is a solution to the conditions, and for all solution, $a_i$ is a submask of $allowed_i$.Then we can loop from $1$ to $n$ and construct $a_i$.For $a_1$, we want to make it as small as possible, which mean we want each bit to be $0$, if possible. We can loop through all the condition $(1, j, x)$ to check which bit of $a_1$ must be $1$. Simply, if a bit is $1$ in $x$, but $0$ in $allowed_j$, then that bit must be $1$ in $a_1$.It's easy to see that after this process, the best $a_1$ is just all the forced bits. We can then loop over the conditions $(1, j, x)$ and force the $1$ bits on $a_j$. Just repeat this to get the answer.You can see my implementation here: 169201529. (Please excuse the weird syntax, I'm experimenting with it).My implementation is $O(n + mlog(m))$ due to sorting the initial conditions, but $O(n + m)$ is achievable as we can do the work for all bits at once in this solution.
•  » » 4 months ago, # ^ |   +19 Submitted same thing, but with O(n+m) complexity: 169137143
•  » » 4 months ago, # ^ |   0 The code now gives WA on newer tests: 169199626I think you need to handle $l = r$ cases.
•  » » » 4 months ago, # ^ |   0 Updated.I thought it would be a problem at some point during the contest, but then I forgot about it. Because I got AC, I thought it wasn't necessary and the thing will handle itself somehow.
•  » » » » 4 months ago, # ^ |   +5 glad to see that REDs also think this way.
•  » » 3 months ago, # ^ |   0 Hello sir, I think I use the same solution with you, but why I get WA on test $4$?My submission: 169330231
•  » » » 3 months ago, # ^ |   0 Take a look at Ticket 16079 from CF Stress for a counter example.
•  » » » » 3 months ago, # ^ |   0 Thanks.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   -8 Hello sir, can you help me with my solution?: 169535486 Thank in advance!
•  » » » » » 3 months ago, # ^ |   0 Take a look at Ticket 16085 from CF Stress for a counter example.
•  » » » » » » 3 months ago, # ^ |   -8 Accepted!! TYSM <3 <3 <3
•  » » 3 months ago, # ^ |   0 Hi, same approach. Any idea why this does not pass: 170424532? Thanks a lot.
•  » » » 3 months ago, # ^ |   0 Take a look at Ticket 16141 from CF Stress for a counter example.
•  » » » » 3 months ago, # ^ |   0 Thanks a lot. Just missed it :S
 » 4 months ago, # |   0 Hello! Could you please tell the reason for contest extended? As for me, nothing was wrong, so I'm just curious. Thanks!
•  » » 4 months ago, # ^ |   0 During contest many contestants expirienced issues with Bad Gateway
•  » » 4 months ago, # ^ |   0 Because some people(including me) faced server error and were unable to submit.
 » 4 months ago, # |   +3 In problem C, Can Somebody explain why to add number of segments in initial answer? i.e After adding the number of subsegments, we get the answer: 6⋅72=21,21+14=35.
•  » » 4 months ago, # ^ |   +1 consider any subarray with no joints ,the answer will be one; if there are x joints in a subarray, the beauty value is actually x+1; so the number 21 that you see is actually number of segments when we consider them without joints and the we add 14 to compensate for all the joints that could be considered;
•  » » 4 months ago, # ^ |   0 Video Solution for Problem C and Problem D.
•  » » » 4 months ago, # ^ |   0 After seeing your handle name I was thinking "why it's look like I have seen this handle before?", but after clicking on the link, I realised that I have watched many tutorials of yours. Good work brother!!.
 » 4 months ago, # | ← Rev. 2 →   0 Hello, Can someone please explain why this failed (Problem B)? 169134990
•  » » 4 months ago, # ^ |   +3 Your solution failed because: 1. The lower bound for s would be b * k (handled properly) 2. The upper bound for s would be b * k + n * (k — 1) (your code does not handle this properly).As, after setting first element to b * k, you can still add k — 1 to each element of the array.Counter Test Case: 1 2 3 1 6Correct Answer: (5, 1) or (4, 2) Your Code output: -1
•  » » » 4 months ago, # ^ |   0 Thanks bro, I got it.
 » 4 months ago, # |   0 Hi, anybody can explain, why my solution is wrong? WA test 4 https://codeforces.com/contest/1715/submission/169168903
•  » » 4 months ago, # ^ |   +5 Hi! It seems like you forgot that if the ith bit of (a | b) is equal to 0, then the ith bits of both a and b must be equal to zero.
•  » » » 3 months ago, # ^ |   0 thank you!
 » 4 months ago, # |   +36 An alternative randomized solution for Problem F:Disclaimer: My solution fails on test 65, but I think it is probably an implementation error. Please correct me if this solution is just completely wrong.The basic idea is to draw a lot of rectangles of the width of the field. Draw the first one at $y=0$ with height $1 \cdot \varepsilon$. Draw the next one at $y=1 + \varepsilon$ with height $2 \cdot \varepsilon$, and so on, each one exactly $1$ apart and $1 \cdot \varepsilon$ taller. We choose $\varepsilon$ as a very small number.Since we have to draw one polygon we can just connect all rectangles on one side.The square can only intersect one rectangle since they are each $1$ apart. We don't want any rectangle to only partially intersect with the square, so we offset everything by a random number between 0 and 1. This makes a partial intersection very unlikely since the height of our rectangles is very small.With the answer to our query we can determine which rectangle the square intersects with and we know the $y$-coordinate is within the interval $[y_{rectangle}-1, y_{rectangle}]$. To determine the exact coordinate we can just query this interval and calculate $y$ with the intersection area.We can repeat this for $x$ to get the answer in $2+2=4$ queries.
•  » » 3 months ago, # ^ |   0 My solution is similar to yours. But I chose to randomly set a small value for the width of each rectangle, and fixed the interval between each rectangle to 1.It passed all the test points. Here it is.169490864I'm so sorry that I am poor in English.
 » 4 months ago, # |   0 Can anybody tell why my solution for D doesn't pass? It has same complexity. O((n + m) * log(x)).Here is solution: 169156511
•  » » 4 months ago, # ^ |   0 I have not gone through your code, but I can tell you the Test case where it fails Counter Test Case: 2 2 1 2 7 2 2 6Correct Answer: 1 6 Your code output: 0 6I hope this would help you :)
•  » » » 4 months ago, # ^ |   0 Ok. Thanks so much.
 » 4 months ago, # |   +94 The evolution of $Div2$ $E$
•  » » 4 months ago, # ^ |   0 May I take the picture away?
•  » » » 4 months ago, # ^ |   0 Sure.
 » 4 months ago, # |   0 can someone tell the rating of the C problem ?
•  » » 4 months ago, # ^ |   +6 I guess somewhere around 1700...
•  » » » 4 months ago, # ^ |   0 ok thanks, it is harder than the usual Div2 C problems
•  » » » » 4 months ago, # ^ |   0 Agree.I felt the same XD
•  » » » » » 3 months ago, # ^ |   0 Excuse me, but I'm just curious about the meaning of "XD".
•  » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 see the XD by rotating your device, it is text form of laughing emoji (this one)Similar to ;) or :)
•  » » » » 4 months ago, # ^ |   0 I think C was reasonable for Div 2 since the only major (intellectually) hard part was figuring out how to compute the cost at the start. Transitions between queries were really simple (albeit long) and didn't require much thinking.
 » 4 months ago, # |   +35 Oh no! I got the solution of F during the contest, but it only cost 2 steps.So I didn't dare to write:(
 » 4 months ago, # |   0 Hey guys, could problem D be solved by sqrt decomposition?
 » 4 months ago, # | ← Rev. 2 →   +24 A solution I thought of for E was to use a segment tree, what you would do is take the old distance and add $i^2$ to each $a_i$, doing that and taking the minimum of the array gives the answer for $i = 0$, then for moving forward from $i-1$ to $i$, you add the AP -1,-3,-5.. To the suffix and ...5,3,1 to the prefix — essentially adjusting the square terms we added. For this we of course need a segment tree that can add an AP to a range and take the minimum of all elements, can anyone confirm if that's possible? If it is can you point me to some resource?
 » 4 months ago, # |   0
 » 4 months ago, # |   0 Saw square cost function and shortest path type dp for E and was wondering if convex hull trick might come in handy. That was in the back of my mind but didn't consider it seriously. I also liked C and D.
 » 4 months ago, # | ← Rev. 3 →   +5 D does not require any graph theory knowledge at all. Initially, there are $30n$ unknown bits. We can do a first pass over the queries to find all bits $p$ and $q$ such that $p \mid q = 0$, which means $p = q = 0$. These are the only bits that must be 0 in order to satisfy the statements (you can hypothetically set all remaining bits to 1 and this will satisfy the statements, but likely will not be lexicographically least).Then we can do a second pass over the queries to find all bits $p$ such that $p \mid 0 = 1$ or $p \mid p = 1$, which means $p = 1$. The former can arise due to forced 0 bits from the first pass, while the latter can arise from statements where $i = j$. These are the only bits that must be 1 in order to satisfy the constraints (though you can't simply turn all remaining bits into 0 this time, since our remaining equations have the form $p \mid q = 1$).With the fixed bits out of the way, we can greedily clear all non-fixed bits of $a_1$ to 0. If any of these bits were involved in an equation of the form $p \mid q = 1$, then the other bit in the equation becomes fixed to 1 to satisfy it. We can then repeat for $a_2$ and so on. Runtime: $O(m + n)$, with a constant 30 iterations for everything. My Submission: 169185957 (I checked for $i = j$ and $p \mid q = 0$ while reading the statements)
•  » » 4 months ago, # ^ |   +35 Spoiler
 » 4 months ago, # | ← Rev. 2 →   -62 E is trash
•  » » 3 months ago, # ^ |   +12 No
 » 4 months ago, # |   0 About C, It confuses me that where n*(n+1)/2(in the tutorial is 6*7/2)comes from?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 In my opinion, it is easier to have an initial array filled with the same number. The initial answer is $n \cdot (n+1)/2$ since that is the number of subarrays, and each subarray will have an awesomeness of 1. After that, we only have to know how to handle the changes after each operation.
•  » » » 4 months ago, # ^ |   0 Thanks!I think I get that.
 » 4 months ago, # |   0 In my opinion, the difficulty of question C is relatively wide from that of the first two questions, which has a negative impact on the rationality of the ranking.
 » 4 months ago, # | ← Rev. 2 →   0 C is fraudulent, as I am amazed by the simple solution. (My friend typed a segment tree to solve it)D is too easy, because the train of thought is obvious and normal.
 » 4 months ago, # | ← Rev. 2 →   0 when i looked at my submission after contest, i was surprised when i saw wrong answer Statement not true: (i, j, x) = (78387, 31267, 38016256)after that i used assert to check if the limit on every bit is satisfied. to my surprise, the assert doesn't happen.can anyone tell me why? the submission id is 169192815
•  » » 4 months ago, # ^ |   0 There are $q$ statements, but your solution reads $n$ statements only.
•  » » » 4 months ago, # ^ |   0 ohhhhhh thanks!!when i noticed it, i really laughed out very loud
 » 4 months ago, # |   0 thanks for tutorial !!!!
 » 4 months ago, # |   +8 In problem E, could anyone explain the Dijkstra part mentioned in the editorial? How to transfer from "ending with air travel" to "ending with a usual edge"?
•  » » 4 months ago, # ^ | ← Rev. 5 →   0 My solution of E:Let's just use Dijkstra algorithm with only roads. Now repeat next thing k times:For each v:dp[new_layer][v] = min(dp[previous_layer][v], minimum_of(cost_of_flight + dp[previous_layer][from]))Run Dijkstra on updated distancesAnswer for vertex i after k repeats is dp[k][i]Submission using Li Chao tree for finding minimum_of(): 169168040
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 What does it mean to "Run Dijkstra on updated distances"? How is it different from normal Dijkstra?
•  » » » » 4 months ago, # ^ |   0 It is not any different. You have some precounted distances, use them instead of INF you use usually and run usual Dijkstra
 » 4 months ago, # |   0 Fast editorial and great questions, thanks, authors.
 » 4 months ago, # |   +3 Great contest! I like A,C and F personally.
 » 4 months ago, # |   0 Can someone please explain why this failed? https://codeforces.com/contest/1715/submission/169120109I thought I did it right. Thanks in advance
•  » » 4 months ago, # ^ |   0 Take a look at Ticket 16061 from CF Stress for a counter example.
•  » » » 4 months ago, # ^ |   0 Thanks!
 » 4 months ago, # |   -25 The system tests of problem D are too weak. Will it be retested?
 » 4 months ago, # |   0 Thanks for tips, try to finish it up myself
 » 4 months ago, # |   0 I used a slightly different approach to D that didn't require a seperate pass for each bit: Create a weighted graph For each vertex AND together the weights of all its neighbouring edges. This tells you what bits can be set for that vertex. Call this the available value for the vertex. Now go through the vertexes in order. If a vertex is its own neighbour then that gives you its value. Otherwise, OR together values for each edge: If the edge goes to a lower numbered vertex, include those bits that are required by the edge but are not included in the solution for the other vertex. This can be calculated as (Edge weight) AND NOT (Other vertex value) If the edge goes to a higher numbered vertex, include those bits that are required by the edge but are not available for the other vertex. This can be calculated as (Edge Weight) AND NOT (Other vertex available value) This gives each vertex its smallest possible value subject to the values given to previous vertexes, so gives the lexically smallest possible sequence of values.See my solution 169149168I think one could create a similar solution without creating a graph by doing two passes through the data, which might be more efficient.
•  » » 4 months ago, # ^ |   0 My last comment is wrong. On the second pass one needs to go through the array values (vertexes) in order, and to know the final values of all lower numbered adjacent vertexes before calculating the value of current vertex, so this needs full adjacency information (i.e a graph).
 » 4 months ago, # |   0 The time complexity between 169232632 and 169236193 is the same. The only difference is I scanned in increasing order instead of decreasing order. I wonder whether it is a trick to cut down time.
 » 3 months ago, # | ← Rev. 3 →   0 This solution is easy for problem A.
•  » » 3 months ago, # ^ |   0 which topic this problem belongs to ? as i want to learn more about it to solve similar problems
•  » » » 3 months ago, # ^ | ← Rev. 2 →   +3 No topic Greedy and Math
•  » » » » 3 months ago, # ^ |   0 Thnx and thnx for your solution btw
•  » » » » » 3 months ago, # ^ |   0 You're most welcome (✿◠‿◠)
 » 3 months ago, # |   0 I'm having an hard time understanding the normal proof of problem A. Case 3 doesnt match with the description, it should be $(n-1) + (m-1)$ moves for Megan and either $n-1$ or $m-1$ for Stanley. In case 1 and case 2, Stanley has to make at least, respectively, $m$ and $n$ moves (and not $m-1$ and $n-1$).
 » 3 months ago, # |   0 Upvoted just for the Advice #0 :kekw:
 » 3 months ago, # | ← Rev. 2 →   +3 In problem E, I'm facing a weird issue, when I initialize the distance to all the arrays with >= 1e14, it gives WA on test case = 37, otherwise, it passed all the test cases.https://codeforces.com/contest/1715/submission/169246634https://codeforces.com/contest/1715/submission/169246972Can someone help me?All that I'm changing between the two submissions is for(int i=2;i<=n;i++) dist[i] = ll(1e14);
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 [Removed, as it was an in invalid test case].
•  » » » 3 months ago, # ^ |   0 The test you provided isn't valid because $k$ must be at least $1$. In fact, when $k$ is at least $1$, taking a direct flight from $1$ to $n$ is always an option, so the answer is bounded by $(n - 1)^2 < 10^{10}$.
•  » » » » 3 months ago, # ^ |   0 Sorry, my bad. I actually got a counter example locally, but it was too big to analyze, hence I manually tried to set $k$ to 0 to verify Dijkstra. You're right that I forgot that a positive $k$ reduces the upper bound as well.
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 My guess is that you overflow in your HullDynamic class. ks and bs can both overflow int, and so multiplication might overflow long long:(x->b - y->b) * (z->m - y->m)UPD: Changed long longs to int128 in your HullDynamic class, AC now: 169286182
•  » » » 3 months ago, # ^ |   0 Thanks mate.
 » 3 months ago, # |   0 Why in authors code of C.Monoblock, they used (n — (i + 1) + 1) instead of (n-i)? As both will give same answer. Why to use (n — (i + 1) + 1). (In for loop)
•  » » 3 months ago, # ^ |   0 for our understanding...
 » 3 months ago, # | ← Rev. 2 →   0 Why am I getting TLE in problem B? Solution
•  » » 3 months ago, # ^ |   0 Your solution has complexity $O(n + \dfrac{s}{k-1})$ where $\dfrac{s}{k-1}$ could also be $10^{18}$. The complexity would then be $O(10^{18})$. Even worse, it could be that for all 1000 tests, bringing the complexity up to $O(10^{21})$. The solution proposed in the editorial has complexity $O(2*n)$, which, in the worst case, is $O(2*10^5)$. Now, if you "translate" your solution (in worst case scenario) to be based upon paramater $n$ ( $n$ in the worst case), it would be $O(n^3)$ in the single test-case and $O(n^4)$ if $t = 1000$.
 » 3 months ago, # |   0 What's that in C++ code for E? for (int i = 0; i < k; ++i) { for (int i = 1; i < n; ++i) { } for (int i = 0; i < n; ++i) { } } 
 » 3 months ago, # |   0 Can anyone help me find out why my solution didn't pass for D ?Here's my solution: for each index 1<= i <=n, let's find the bits that must be set to zero. Now let's iterate over the array starting from the last element, for each element we will only consider the statement that include another element with smaller index. For each statement that include that element, let's set to 1 all of the bits that are set to 1 in the OR value and can be set to 1 in the current index, the other bits will be set to 1 in the other element since we can't set them in the current one.Here is a link to my submission: https://codeforces.com/contest/1715/submission/169171341Any help will be more than appreciated.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Simple counter: 3 2 1 2 1 2 3 1 Your code gives 0 1 1, answer should be 0 1 0.
•  » » » 3 months ago, # ^ |   0 Oh I see where I went wrong, thank you !
 » 3 months ago, # |   0 Problem F: Life will be harder if the query polygon must have all of its points lying inside the field. (This is the problem statement came from my misunderstood :)).
 » 3 months ago, # |   +13 rockstar_an is the best, thanks to him I'm an Expert.PS : He is my dad :)
•  » » 3 months ago, # ^ |   +3 Thanks my son.
•  » » » 3 months ago, # ^ |   +5 Best father-son duo. Tears :')
•  » » 3 months ago, # ^ |   +3 Best duo.
 » 3 months ago, # |   0 Problem F is brilliant! Liked it very much :)
 » 3 months ago, # |   0 Can anyone help me find out why my solution didn't pass for D ?I think I have written as what have been talked in blog. I have tried to fix it, but I failed. My submission：169346279
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16078 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 Thanks.
 » 3 months ago, # | ← Rev. 2 →   0 Can someone tell me why my code for problem D is failing? here's the code: https://codeforces.com/contest/1715/submission/169397612
•  » » 3 months ago, # ^ |   0 Take a look at Ticket 16081 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 yea I'm such an idiot it should be bfs not dfs lol, thanks for the test :) now I got AC thank God.
 » 3 months ago, # |   0 TLE On test case 8 for Problem D Solution — 169441708 (https://codeforces.com/contest/1715/submission/169441708)Can Anyone tell what i am doing wrong , its the same approach as mentioned in tutorial.Thanks in Advance
 » 3 months ago, # |   0 I disagree with Advice #0. You should always consider risk of wasting time on implementation of solution. And thinking about proof and trying to prove may save you from that.
 » 3 months ago, # |   0 For those who 1715E - Long Way Home for some reason don't understand why this thing can be applied here: within min first square component may be considered as parameter and second square term can be extracted from min because it's being constant in query.
 » 3 months ago, # | ← Rev. 2 →   0 Could anyone help me find why this submission https://codeforces.com/contest/1715/submission/169450718 which is O(32(m+n)) gets TLE but https://codeforces.com/contest/1715/submission/169452067 which could be O(32 * 32(m+n)) passes? The only difference is that I changed from a two-dimension vector to one-dimension vector, where bit information are added in edges instead of one-bit-one-graph. I have been thinking for the whole night. Thx...
 » 3 months ago, # |   0 can C be solved using a segment tree? this was my intial thought but its not clear what data should each segment hold
 » 3 months ago, # |   0 Is there anyone who can help with my failed submissions? I can't find any differences between the answer and my solution. It always turns out to be WA on test 8. my submission is here
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 Take a look at Ticket 16151 from CF Stress for a counter example.
•  » » » 3 months ago, # ^ |   0 I see. Thanks a lot!
 » 3 months ago, # |   0 In author solution for problem E why is it: while (ll.size() >= 2 && l.intersect(ll[ll.size() — 2]) <= x.back())and not: while (ll.size() >= 2 && l.intersect(ll[ll.size() — 2]) >= x.back())won't the authors solution remove lines from the Convex Hull that actualy need to be in it.
•  » » 3 months ago, # ^ |   0 Figured it out.. brain fartWe are searching for Min not Max .
 » 3 months ago, # |   0 Why does my solution for Problem D give TLE, pls someone explain.172482735
»
2 months ago, # |
0

problem 1715B in testcase 1 even if my beaty is equal to given beauty it's showing wrong answer

input : 5 4 7 38 (5:- no. of elements in array,4 is beauty,7 is k and 38 is sum of elements of array)

given answer : 0 3 3 3 29 my answer : 0 0 1 6 31

will some one help me to find the mistake in my code written in c++ ::

# include<bits/stdc++.h>

using namespace std;

int main(){ int q; cin>>q; while(q--){ long long int n,k,b,s,j;\ vector v; cin>>n>>k>>b>>s; j=b-1; if(s>(b+n)*k || s<b*k){ cout<<-1<<endl; } else{ --n;
if((b+1)*k-1>=s){ // cout<<s<<" "; v.push_back(s); s=0; } else{ // cout<<(b+1)*k-1<<" "; v.push_back((b+1)*k-1); s-=((b+1)*k-1); }

while(n--){
if(s<=0){
// cout<<0<<" ";
v.push_back(0);
}
else if(s>=j){
v.push_back(j);
// cout<<j<<" ";
s-=j;
}
else{
// cout<<s<<" ";
v.push_back(s);
s=0;
}
}
for(int i=v.size()-1;i>0;i--){
cout<<v[i]<<" ";
}
cout<<v[0]<<endl;
}
}

}

 » 4 weeks ago, # |   0 Interestingly, D has similar idea to https://codeforces.com/problemset/problem/1594/D, but you have to do it 30 times