### seland's blog

By seland, 6 years ago,

545A - Toy Cars

We can find all information about i-th car collisions in the i-th row of the matrix A. More specific, if there is at least one 1 or 3 at i-th row, then i-th car isn't good (it was turned over in at least one collision). Otherwise, i-th car is good. We just need to check this condition for each car.

545B - Equidistant String

One can see, that if si = ti for some i, then the value of pi isn't important for us. Really, if we make pi equal to si then it also be equal to ti. And if we make pi not equal to si then it also be not equal to ti. So, we have an answer that is closer or further to both of s and t.

So we interested about such position i that si ≠ ti. If we make pi equal to si we make p further from t. If we make pi equal to ti we make p further from s. It means that we need to divide these positions into two equal parts to have equidistant string. For example, we can make first of these positions closer to s, second closer to t and so on. If the number of these positions is even, we find an answer, if it is odd, answer doesn't exist.

Time complexity — O(n).

545C - Woodcutters

One can solve this problem using dynamic programming or greedy algorithm. Start with DP solution.

Define stayi, lefti and righti as maximal count of trees that woodcutters can fell, if only trees with number from 1 to i exist, and i-th tree isn't cutted down, i-th tree is cutted down and fallen left, i-th tree is cutted down and fallen right correspondingly. Now we can compute this values for each i from 1 to n by O(n) time because for each next we need only two previous value. Answer is maximum of stayn, leftn, rightn.

Also this problem can be solved by the next greedy algoritm. Let's fell leftmost tree to the left (it always doesn't make an answer worse). After that, try to fell the next tree. If we can fell it to the left, let's do it (because it also always doesn't make an answer worse). If we can't, then try to fell it to the right. If it is possible, let's do it. Last step is correct because felling some tree to the right may only prevent the next tree's fallen. So we may "exchange" one tree to another without worsing an answer.

Time complexity — O(n).

545D - Queue

We can solve this problem by greedy algorithm. Let's prove that it is always possible find an answer (queue with the maximal number of not disappointed people), where all not disappointed people are at the begin of queue. Assume the contrary — there are two position i and j such that i < j, persons at position from i to j - 1 are disappointed, but j-th person isn't. Then just swap persons at positions i and j. After that all persons from i to j - 1 will be still disappointed (or become not disappointed) and j-th person will be still not disappointed. So the answer isn't maked worse.

So, we need to find person with minimal ti, that can be served now and will be not disappointed. We can do that by sorting all the people by time ti and try to serve them one by one. If somebody will be disappointed, we may send he to the end of queue, and doesn't add his serve time to the waiting time.

Time complexity — O(n + sort).

545E - Paths and Trees

It's true, that Dijkstra modification, where in case of equal distances we take one with shorter last edge, find an answer.

For prove that let's do some transformation with graph. At first, find all shortest paths from u to other vertices. Define di as the length of shortest path from u to i. After that, we can delete some edges. Specifically, we can delete an edge with ends in x and y and weight w if |dx - dy| ≠ w, because it isn't contained in any shortest path, so it isn't contained in shortest path tree. After that, we can direct all edges from vertices with less distance to vertices with greater distance (because of all weight are positive). It's easy to prove, that if we take one edge that entering each vertex, we have a shortest path tree. Then we only need to take for each vertex minimal egde, that entering this vertex. Why? Because we have to take at least one edge, that entering each vertex to make a graph connected. We can't take edges with less weights than minimal. And if we take minimal edges, that entering each vertex we will have an shortest path tree. So that is minimal possible total wieght of shortest path tree.

You can see, that Dijkstra with modification do exactly the same things.

Time complexity —

• +38

 » 6 years ago, # |   0 Thank you for the editorial. I ended a 4-hour contest about one and a half hour ago, and I'm not that good at greedy, so I hope I can get a better score next time...
 » 6 years ago, # |   +22 I think time complexity of D is O(n log n) due to sort.
•  » » 6 years ago, # ^ |   -19 I think we don't count 'sort' in when we calculate time complexity.
•  » » » 6 years ago, # ^ |   +8 on the contrary, we do count 'sort' while calculating time complexity.
•  » » » » 6 years ago, # ^ |   +4 thx
•  » » 6 years ago, # ^ |   +3 Thanks, fixed.
 » 6 years ago, # |   -6 For Problem E, there is a O(m) solution by using SPFA algorithm.
•  » » 6 years ago, # ^ |   0 Wow! Could you tell me this method?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 You may read about SPFA here.
•  » » 6 years ago, # ^ |   +10 Actually, SPFA does not run in O(m) time complexity. It's just really fast on random-generated testcases, and in other special cases, it can be O(nm), the same as the original Bellman-Ford.Not a good choice on some platform which allows hacking, isn't it? :P
 » 6 years ago, # | ← Rev. 2 →   -12 RIP English!
 » 6 years ago, # |   0 man, next time no 'greedy'
•  » » 6 years ago, # ^ |   +3 what is wrong with 'greedy'?
•  » » » 6 years ago, # ^ |   +3 Because too much of everything is bad.. Eg me commenting too much
 » 6 years ago, # |   0 Can someone explain how to approach problem E ? I didn't quite get it from editorial. i.e What it means by saying where in case of equal distances we take one with shorter last edge . Thanks in advance.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Running the dijkstra's algorithm gives you a tree with minimum distances from source to any other vertex ( tree rooted at source ). Suppose this case : Path 1 : A->B->C where A->B and B->C edge weights are 1. Path 2 : A->C where A->c edge weight is 2. Now if we have to make a choice between these two in terms of minimum distance, we can see that choosing either is fine. But in case of forming the tree with minimum weight , we need to minimise sum of edge weights. If we choose A->B and A->C , it is a valid dijkstra tree with sum of edges = 3 , whereas choosing A->B and B->C is also a valid tree with sum of edges = 2. So whenever distance is same during relaxation in dijkstra, choose the smaller edge.
•  » » » 6 years ago, # ^ |   0 Did you mean that we have to find MST here?
•  » » » » 6 years ago, # ^ |   0 sorry , edited. We dont have to find the MST. Rather we have to find a spanning tree which satisfies dijkstra. If multiple trees are possible, then the one with minimum cost should be taken.
•  » » » 6 years ago, # ^ |   0 Cant you just consider the weights to be the distances between the nodes and run a normal Dijsktras on it.
•  » » » » 6 years ago, # ^ |   0 It would be easier if you read my explanation above once and read up my code : 11189526 .. I have added lots of comments in the code to make it clear for everyone to understand.. Feel free to ask doubts.A test case where normal dijkstra might fail :1 2 1 2 3 1 1 3 2 source : 1Here you can go from 1->3 in cost 2 , but you should select 1->2->3 instead of 1->2 and 1->3 in your tree. You can easily see that both the solutions are valid dijkstra trees.
•  » » » » » 22 months ago, # ^ |   0 Thanks himanshujaju u explained very well
 » 6 years ago, # |   0 'maked worse'?
 » 6 years ago, # |   0 Can anyone tell me why this solution gave WA for test 11 question C? I used DP where prev=0 means previous tree wasn't cut, prev=1 means previous tree was cut to left, prev =2 means previous tree was cut to right Solution Also I always cut the 1st tree to the left and when I am at i-th tree, I check if prev value was 0,1,2 and accordingly I move forward. And I cut the last tree to the right
•  » » 13 months ago, # ^ |   0 Hii, in the line 47 use this : "if(p[i].first-p[i].second>p[i-1].first+p[i-1].second) x=func(i+1,1);" instead of: "if(p[i].first-p[i].second>p[i-1].first+p[i].second) x=func(i+1,1);".
 » 6 years ago, # |   0 Not sure... what did I do wrong here http://codeforces.com/contest/545/submission/11155373
 » 6 years ago, # | ← Rev. 2 →   0 THis is my first submission 11159431. I got runtime error in pretest 3.I changed two lines s[i]=t[i]; printf("%s",s);tot[i]=s[i]; printf("%s",t);IT got accepeted!! what is the difference?
 » 6 years ago, # |   0 Getting WA on 5th test case for E problem. Does someone have an idea what is wrong with my code? Or maybe I can somehow view input of 5th test case :-) ? http://codeforces.com/contest/545/submission/11175222
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I've managed to get AC on problem E. But I'm still confused and don't understand one fact. These are 2 solutions:http://codeforces.com/contest/545/submission/11195293 (WA on 5th test case)The difference is only in 1 line (line #40) // if (dist == o.dist) return Integer.compare(v, o.v); vs if (dist == o.dist) return Integer.compare(v, o.v); Can someone explain me why does its really matter?
•  » » » 6 years ago, # ^ |   0 if you don't compare v and o.v when distance is equal, vertiсes (5, 0) and (5, 1) are equal
•  » » » » 6 years ago, # ^ |   0 Exactly. But why is it a problem? They will be processed both in some order
•  » » » » » 6 years ago, # ^ |   0 TreeSet qif you insert (5, 0) and after it (5, 1), it will not be added. I think you don't want such behavior
•  » » » » » » 6 years ago, # ^ |   0 No, it seems that set will contain both because vertices are not really equal. (compareTo == 0 isn't the same as equals == true)
•  » » » » » » » 6 years ago, # ^ |   +5
•  » » » » » » » » 6 years ago, # ^ |   0 Yes, you're right :-) Thank you very much for help!
 » 6 years ago, # |   0 hi, can anyone explain where i went wrong for 545b problem , link is http://codeforces.com/contest/545/submission/11158712 ,,,,, what i done is ,if the no of mismatch positions are odd then cout<<"impossible" else im flipping the first half of mismatch bits of first string and displaying it.
•  » » 6 years ago, # ^ |   0 char ...n; It's wrong. You need n up to 10^5, it should be int.
•  » » » 6 years ago, # ^ |   0 thanks you Totktonada
 » 6 years ago, # | ← Rev. 2 →   0 Hello, can anyone please explain why are why we delete edges in which " |Dx-Dy| != w " ? In tutorial its written that "that edge will not be in shortest path". Can you please wxplain why not ?Is it because of this statement in problem -> "The shortest-path tree from vertex u is such graph G1 = (V, E1) that is a tree with the set of edges E1 that is the subset of the set of edges of the initial graph E, and the lengths of the shortest paths from u to any vertex to G and to G1 are the same."
 » 6 years ago, # | ← Rev. 2 →   0 Why am I getting WA in my solution ? I have covered all possible cases selandhttp://codeforces.com/contest/545/submission/11184421
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 Maybe this can help you:41 12 26 27 1The answer is 3 while your answer is 4.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 I think that for this test case , 1st tree fell left, 2nd tree fell right, 3rd — left ( it can fall left ) , 4th — right==> all 4 fell Please check u128
•  » » » » 6 years ago, # ^ |   0 Sorry , I just forgot this case
•  » » » » 6 years ago, # ^ |   +3 If 2nd fell right, it'll take [2, 4] and 3rd fell left, it'll take [4, 6], which overlapped 2nd. So the answer is 3.
 » 6 years ago, # |   0 I tried to solve the problems after the contest and is successful for three(solved one during contest) and for 545E — Paths and Trees I am getting wrong answer on test 8. Here is my source http://codeforces.com/contest/545/submission/11186979 can someone help me where does it go wrong?
•  » » 6 years ago, # ^ |   +3 I debugged and found an overflow.
 » 6 years ago, # |   0 "It's true, that Dijkstra modification, where in case of equal distances we take one with shorter last edge, find an answer." Why do we take the shorter last edge in case of equal distances? No matter what edge we choose, it leads to shortest distance from source to that vertex. I don't see how this affects the weight of the shortest path tree. Any test case where not choosing shorter last edge fails?
•  » » 6 years ago, # ^ |   0 The one from problem statement with 3 vertices
 » 6 years ago, # |   0 there is another solution for E where u can run dijkstra on the graph from u , then sort the nodes by distances , then add each node to the tree for further details check this out 11271206
•  » » 6 years ago, # ^ |   0 I think it is the same solution
 » 6 years ago, # | ← Rev. 2 →   0 Hi anyone can please tell me why my code is getting memory limit exceed? It passes much larger cases but get memory limit exceed in a small case! My submitted code For E. Thanks.
•  » » 6 years ago, # ^ |   0 Found it. When only updating the smallest weight no need to push into the queue again.
 » 6 years ago, # |   0 Even After reading the solution I thought of implementing a solution for problem C Could not find why it is wrong. TLE ok it can come as the answer is m*n may besubmissionThe strategy I have implemented is All the students attack the problem from the front. For each block ai student remain and the rest go forward and go to the next state. If a[i]>students arrived at the spot then all the student stay and remove until a[i]
 » 6 years ago, # |   0 For the E question cant we just add the nodes in the order the that they get popped from the priority queue as this will ensure that sum of distances is also the least. Please correct me if wrong :)
 » 6 years ago, # |   0 In problem C (Woodcutters) , my solution got accepted even though I used only one previous state rather than using two , as it is mentioned in the editorial . Is that approach wrong ? if it is wrong, why it got accepted ?
 » 5 years ago, # | ← Rev. 3 →   0 The editorial for the problem C says:__ Also this problem can be solved by the next greedy algorithm. Let's fell leftmost tree to the left (it always doesn't make an answer worse). After that, try to fell the next tree. If we can fell it to the left, let's do it (because it also always doesn't make an answer worse). If we can't, then try to fell it to the right. If it is possible, let's do it. Last step is correct because felling some tree to the right may only prevent the next tree's fallen. So we may "exchange" one tree to another without worsing an answer.If we follows this approach then for the following:135 916 1024 730 534 336 1would be 3 bu isn't the correct answer 6? (Fell all trees except the second one)
•  » » 5 years ago, # ^ |   0 number of trees = 13 . You only printed 6 of them .
 » 5 years ago, # |   0 Couldn't understand dp solution of C? Can anyone explain with code?
•  » » 10 months ago, # ^ | ← Rev. 2 →   0 I had done that using greedy ,i am attaching my solution Your text to link here...
 » 4 years ago, # | ← Rev. 2 →   0 Wrong ANswer: 28141525 Accepted:28141822 But,whats the problem into first submission?Could anyone please help me to find that out?
 » 3 years ago, # |   0 Guys, I didn't understand the DP solution of problem C ... Can anyone help ?
•  » » 3 years ago, # ^ |   0 So, the idea is that you have these three DP arrays stay, left and right and you have that: stayi denotes the maximum number of trees you can cut down if you had the first i trees as input and the ith tree was not cut down. Therefore you would have that stayi = max(stayi - 1, lefti - 1) if xi - 1 + hx - 1 >  = xi (i.e. if cutting down the tree i - 1 and making it fall to the right is impossible. Otherwise if xi - 1 + hx - 1 < xi and you can cut that tree, you would have stayi = max(stayi - 1, lefti - 1, righti - 1) lefti denotes the maximum number of trees you can cut down if you had the first i trees as input and the ith was cut down and fell to the left. Now, here things get a little tricky. First you need to check wheather xi - hi > xi - 1 as if that is not true its impossible to cut that tree and you should not be looking at that case. If it is possible you would have lefti = max(stayi - 1, lefti - 1) + 1. The  + 1 comes from the fact that you are cutting down tree i. Finally, if you want to check righti - 1 you must have righti - 1 + hi - 1 < xi - hi. righti denotes the maximum number of trees you can cut down if you had the first i trees as input and the ith was cut down and fell to the right. Calculations apply similar logic to above.. Finally, you answer is given by max(stayn, leftn, rightn). I hope that was good enough for you. If not, don't hesitate to ask more questions.
•  » » » 3 years ago, # ^ |   +3 Thanks a lot!
•  » » » 3 years ago, # ^ |   0 can you explain with diagram plz
•  » » » 2 years ago, # ^ |   0 Sol pls
•  » » » 15 months ago, # ^ |   0 Thanks a lot for detailed explanation. Here is the implementation of the above idea 74361898
•  » » » » 14 months ago, # ^ |   0 Can you explain why are we saying stay[i] = max(stay[i-1],left[i-1])? Because if it is not possible to fell (i-1)th tree to left side, then we will not have value of left[i-1]. If it is impossible for a tree to fell left side, then we are leaving that case, as a result we don't have any value of left[i-1]. My question is in stay[i], why are we not checking if it is possible for (i-1)th tree to fall left side?
•  » » » 14 months ago, # ^ |   0 Thank you so much...it was very helpful
•  » » » 11 months ago, # ^ |   0 Great explanation! But shouldn't there be ${x_{i-1}}$ instead of ${right_{i-1}}$ in the last line of ${left_i}$ bullet?
•  » » » 10 months ago, # ^ |   0 Thanks alot, nice explanation...
•  » » 3 years ago, # ^ |   0 see quora ans;
 » 3 years ago, # |   0 Here is my solution for Div 2 — C using Top-Down DP/Memoization. 44734044
•  » » 3 years ago, # ^ |   0 Thanks, This is what i was looking for!
•  » » 2 years ago, # ^ |   0 can you please help me out ??? my solution for C using dp , wa on testcase 8 although it seems correct
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 i think u forgot 1 condition when u can fell both i and i+1 tree in same segment when height[i]+height[i+1]
•  » » » » 2 years ago, # ^ |   0 Thanks (^_^), though I solved this recently.
 » 18 months ago, # | ← Rev. 2 →   0 Not able to understand why greedy is giving AC. In case tree fall in right direction then it may cover more than 1 trees right ?. Which will lead to bad result
•  » » 18 months ago, # ^ |   0 It cant cover more than 1 tree, because even if it is covering the coordinate of first right tree, we can't make it fall on the right (thus not counting this in our answer). In fact, it can't cover any tree. Thus at worst case, we will be taking possible left "fall" of right tree, if we make the tree fell to its right (but its ok, since at the expense of 1 right tree, we are increasing the answer by 1).
•  » » » 18 months ago, # ^ |   0 Thanks got it
 » 17 months ago, # |   0 Why sorting works for D? Quick sort gives O(n^2) complexity in the worst case ( when all numbers already sorted ) , doesn't it? So Time Complexity is O(n^2+n), why I didn't get TLE? Can u explain me, please?
•  » » 13 months ago, # ^ |   0 Because the time complexity of sort() function in C++ library is O(n*log(n)).
 » 15 months ago, # |   0 bro cutted is wrong :) the pp and past tense of cut is cut
 » 14 months ago, # |   0 Did Greedy Approach in 545C. Getting WA on prob. 4. What is wrong with my code? https://codeforces.com/contest/545/submission/75346533 Thanks:)
•  » » 12 months ago, # ^ |   0 You have to start using occ_y in your code: if you can't fall a tree to the left or to the right, the next tree can only be fell left iff it's not occupied already by another tree.
 » 14 months ago, # |   0 vovuh could you plz explain your DP approach of 3rd problem
•  » » 10 months ago, # ^ |   0 Greedy based approach Your text to link here...
 » 12 months ago, # |   0 SamosaMeAAloo loved that name
 » 4 months ago, # |   0 dp code for c... /////////////////////////////////////////////////////////////////////// void solve(vector &x, vector &h, int n) { /*int left[n]; int right[n]; int stay[n];*/ int dp[n + 1][3]; memset(dp, 0, sizeof(dp)); //-->k 0->stay 1->left 2->right; //dp[i][0]->number of tree you can cut if ith tree is not cut //dp[i][1]->number of tree you can cut if ith tree is cut and fall left //d[i][2]->number of tree you can cut if ith tree is cut and fall right dp[0][0] = 0; dp[0][1] = 1; if (x[0] + h[0] < x[1]) { dp[0][2] = 1; } else { dp[0][2] = 0; } for (int i = 1; i < n; i++) { int c1 = -1, c2 = -1, c3 = -1; dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]); if (x[i - 1] + h[i - 1] < x[i]) { dp[i][0] = max(dp[i][0], dp[i - 1][2]); } if (x[i] - h[i] > x[i - 1]) { dp[i][1] = 1 + max(dp[i - 1][0], dp[i - 1][1]); if (x[i - 1] + h[i - 1] < x[i] - h[i]) { dp[i][1] = max(dp[i][1], dp[i - 1][2] + 1); } } if ((i + 1 < n) and (x[i] + h[i] < x[i + 1])) { dp[i][2] = 1 + max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])); } if (i == n - 1) { dp[i][2] = 1 + max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])); } } int ans = max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])); cout << ans << endl; } 
 » 4 months ago, # |   0 Hi! Can anyone please explain me where I have done wrong in problem E. My submitted solution is https://codeforces.com/problemset/submission/545/107779160 .I am getting wrong answers on test case 8. Thanks in advance.