### FieryPhoenix's blog

By FieryPhoenix, 4 years ago,

1307A - Cow and Haybales

Idea: FieryPhoenix

Tutorial
Solution
Alternative O(n) Solution:

1307B - Cow and Friend

Tutorial
Solution

1307C - Cow and Message

Tutorial
Solution

1307D - Cow and Fields

Idea: FieryPhoenix

Tutorial
Solution

1307E - Cow and Treats

Idea: FieryPhoenix

Tutorial
Solution

1307F - Cow and Vacation

Idea: FieryPhoenix

Tutorial
Solution

1307G - Cow and Exercise

Tutorial
Solution
• +159

| Write comment?
 » 4 years ago, # | ← Rev. 2 →   -10 wonderful problems and nice contest
 » 4 years ago, # |   0 Test Case 7 of C?
•  » » 4 years ago, # ^ |   0 probably something like aaaa (where the answer is 6 because aa occurs at (1,2),(1,3),(1,4),(2,3),(2,4),(3,4)), at least I also failed pretest 7 and was told afterwards that not covering this case was my error
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 case of 2 same letters I suppose, because I fixed that and got AC
•  » » 4 years ago, # ^ |   +6 I think it's 1e5 aaaa..... I got WA on Test 7 fixed after changing int to long long
•  » » 3 years ago, # ^ |   0 it is 100000 'j' and all other 0. so u might have missed the cases in which 2 'j' are there in AP. it will be nC2 == n*(n-1)/2 . then u will get AC in it.
 » 4 years ago, # |   +85 G already appeared many times. This is at least third time I see this. Fortunately first one where I get it accepted (at least on pretests), but I still have no idea what the solution is, I copied Marcin_smu's code from Petrozavodsk (Winter 2016 problem J2) and made some adjustments :P. It appeared on some Topcoder as well, but I couldn't find it (iirc setter was Lewin)
•  » » 4 years ago, # ^ |   +39 I wasn’t able to solve this version :(I think you might be referring to this problem: https://community.topcoder.com/stat?c=problem_statement&pm=13952. It’s a bit different though, and has a bound on number of edges which makes it a bit easier.
 » 4 years ago, # | ← Rev. 2 →   +10 During the contest I had the following solution for F:Do centroid decomposition. Each query will be solved at its centroid.For each node and depth in the centroid tree, I compute $up(node)$ being the special node that can be reached by going up as few edges as possible, making at most $k$ moves, and with a lower depth than $node$ (closer to the root). Then I computed $dp(node)$ the "closest" you can get to the centroid via special nodes with the formula $dp(node) = min(depth(node), dp(up(node)))$. To solve a query we just check that $dp(a) + dp(b) \leq k$. However, this gives incorrect on test 10. Do you have a counter-example?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 To solve a query you assume that you just have to check the inequality on the centroid that is $lca(a, b)$ but this is not sufficient. This breaks it11 3 1 11 9 2 11 6 4 7 1 5 3 1 9 8 10 6 3 10 3 9 8 8 1 2 7 In this test, the very first centroid is the only rest stop.EDIT: The first line of the test was not visible.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 Your test seems to be missing one edge. Could you please be more specific? I don't understand what you mean in your comment.
•  » » » » 4 years ago, # ^ |   +8 At line 42 you find cen which is the $lca(a, b)$ in the centroid tree and check if $dp(a) + dp(b) \leq k$. But the condition may be false for cen and true for CP[cen] or CP[ CP[cen] ] and so on.I fixed the test, the first line was missing.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +8 I see. Indeed, it seems that I should have checked extra that $dp(a) + dp(b) \leq k$ or that $dp(a) + closest(cen) \leq k$ and $dp(b) + closest(cen) \leq k$. Thanks a lot. I was struggling a lot to find the flaw in my reasoning. EDIT: It seems that even with the extra condition it's not passing test 10, so it wasn't because of that. Any ideas?
•  » » » » » » 4 years ago, # ^ |   +8 Early today I submitted your code but with a loop thought the $CP$'s and it TLE'd test 17 71358892. A counter test for your last code15 3 1 1 2 2 3 3 4 3 5 5 6 5 7 5 8 4 9 4 10 4 11 4 12 4 13 4 14 4 15 4 1 1 6 You can omit vertices 9-15 in a drawing, they just force the centroid to be 4.
 » 4 years ago, # |   0 Why does my B fail? 71327169.Answer is min over all ceil(x/itr) if itr>=x or 2 if itr
•  » » 4 years ago, # ^ |   +12 Why does $answer$ equal to $x$ in the beginning? Shouldn't it be $inf$ or something? Consider test $1$ $1$ $2$
•  » » » 4 years ago, # ^ |   +11 Dammit!! Thanks bud.
 » 4 years ago, # |   +30 Yo Chris,I really like to see the round authorship! I might not have done so hot (good thing I was on an alt!) but I have a lot to learn from here ;)It’s cool to see that you and Daniel are authoring problems for both USACO and CodeForces... I wish that I could learn to do the same too. See you in the next contest!Nathan
•  » » 4 years ago, # ^ |   +67 Thank you for the positive feedback! We tried our best to make a round everyone would enjoy.
 » 4 years ago, # |   -96 Thanks a lot for this contest.Another name added to my shit problemsetters list. :)
•  » » 4 years ago, # ^ |   +64 Hi! I am open to constructive feedback. Which part did you have problems with?
•  » » » 4 years ago, # ^ |   0 For C, it would probably have made sense to write explicitly what you mean with 'arithmetic progression' (in particular since you were not referring to the usual definition which allows negative differences). That would probably have saved a lot of people some time and WA.
•  » » » » 4 years ago, # ^ |   +3 Valid point, but on the other hand, strings with negative index difference cannot be called subsequences, since they're impossible to obtain by crossing out letters in the original string (which is the definition of subsequence).
•  » » » » » 4 years ago, # ^ |   0 Hmm that's true, I hadn't thought of that.
 » 4 years ago, # |   0 Would this be a simpler solution to D?Use BFS to find the shortest path, now, first sort the shortest path, and for each integer not in the path, check if it is in the special fields — if it is, print the length of the shortest path.Otherwise we loop over each node in the shortest path until we have found one that is special, once we have found this we loop until we have found the next one. We save the distance, and keep only the minimum distance at the end. we now return the length of the shortest path minus this distance plus one. It essentially corresponds to the two cases "we can place a path that is not on the shortest path"(in which case the shortest path will have the same length) or "We must place the path inbetween two nodes in the shortest path, reducing the length of the shortest path by the distance between those two nodes plus one".
•  » » 4 years ago, # ^ | ← Rev. 4 →   +6 As the graph is not always a tree(can have cycles), there can be multiple paths from 1 to n. Consider this case 6 6 2 3 5 1 2 2 3 3 6 1 4 4 5 5 6 Connecting 3 and 5 will not reduce the shortest path
•  » » 4 years ago, # ^ |   0 I also did the same, but this approach gives WA. I couldn't understand the reason behind it.My code : 71327190
•  » » 4 years ago, # ^ |   0 Try this testcase 10 10 2 5 7 1 2 2 3 3 4 4 5 5 6 1 7 7 8 8 9 9 6 6 10 
•  » » 4 years ago, # ^ |   0 And instead of down-voting, can you guys please point out where is the mistake? I also thought of the same approach but it gave WA. I found a counter-example but are there any more possibilities where this approach could go wrong?
•  » » » 4 years ago, # ^ |   +8 Indeed pretty weird that people are downvoting. Im simply trying to learn where i went wrong
 » 4 years ago, # | ← Rev. 2 →   +35 .
 » 4 years ago, # |   0 Your solution to second problem is O(nlog(n)), not O(n), because you are using set.
•  » » 4 years ago, # ^ |   0 As the author said in the code, you don't have to use set. Set is just used to check if some number in it, this could also be done in O(n) easily.
 » 4 years ago, # | ← Rev. 2 →   0 In D, can anyone explain why my solution is wrong?my solutionMy Logic was: 1.normal bfs to get the level of each node. 2.sorting special nodes in order of their distance from node 1.3.getting the pair of nodes which has the minimum amount of difference w.r.t distance from node 1.4.connect them then do the bfs again to get the distance from node 1 to node n.
•  » » 4 years ago, # ^ |   0 Similar approach, same question :( 71327933
•  » » 4 years ago, # ^ |   0 Why do you want to minimize the distance w.r.t. distance from node 1? That makes about as much sense as the number of points you got for your solution. Suppose two special fields already have a road between them, but your algorithm instead will place a road between some other nodes which have minimum difference. Might as well choose two random nodes. At least the probability of correct solution will be uniform.
•  » » » 4 years ago, # ^ |   +1 if one node lets say x is Xi distance from 1 and another node lets say y having Yi distance from 1. Then I want to minimize the difference between (Xi-Yi). Placing another road will have no effect which is independent of the fact you suggested  Suppose two special fields already have a road between them, but your algorithm instead will place a road between some other nodes which have minimum difference
•  » » 4 years ago, # ^ |   +36 Hi! Consider this case: Test case$8$ $7$ $3$$1 7 8$$1$ $2$$2 8$$1$ $3$$3 4$$4$ $5$$5 6$$6$ $7$Your solution incorrectly connects node $1$ and $8$. Optimal solution connects $1$ and $7$. Hope this makes sense!
•  » » » 4 years ago, # ^ |   0 Hi! Thank you for the test case. I had written a similar solution. However, I am still struggling to understand the solution in the editorial. What is the intuition behind sorting on the difference of the distances from source and destination? Could you help?
•  » » » » 4 years ago, # ^ |   0 We assume without loss of generality that $x_a+y_b \le y_a+x_b$. If you rearrange this inequality, you get $x_a-y_a \le x_b-y_b$. We see that sorting on the difference $x_i-y_i$ leads us to the rest of the solution.Hope this helps.
•  » » » » 4 years ago, # ^ |   +20 My understanding of the intuition behind the sorting is to order the fields so that when you iterate through them, $min(x_{prev} + y_{cur}, y_{prev} + x_{cur}) = x_{prev} + y_{cur}$. In other words, as you iterate, you can achieve the longest distance by taking the biggest $x$ seen so far and pairing it with the current $y$.
•  » » » » » 4 years ago, # ^ |   +3 Really good intuition. Thank you!
•  » » » » » 4 years ago, # ^ |   +8 Yea exactly, reduces from n^2 to nlogn by gauranteeing that if we take a max yb for a given xa it will indeed be smaller than or equal to xb + ya and we avoid additional checks. Nice Question :)
•  » » » » » » 4 years ago, # ^ |   0 I don't get it. Can you please explain why would it always be smaller than or equal to xb + ya ?
•  » » » » » » » 4 years ago, # ^ |   0 Coz you sorted according to the constraint
•  » » » » » » » » 4 years ago, # ^ |   0 Much appreciated ,but i still don't get it.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +6 The idea is similiar to following. Given array of numbers $a$, find $max$ of $(\min\limits_{i,j}$ $(a_i, a_j))$.Naive solution is $O(N^2)$, where you select both indices. But, alternatively, you can sort the array, and then you know that for some $i$, taking $min$ with anything to the right will give $a_i$, and anything to the left will give that thing. So, now, you only need to go through the sorted list and take best value of adjacent indices.Basically, for maximizing $min(A,B)$, we try to keep $A$ and $B$ as close as possible. In particular, for the given problem, we need maximum of $min(x_a + y_b, x_b + y_a)$, so we try to keep $x_a + y_b = x_b + y_a$, i.e. $x_a - y_a = x_b - y_b$. This tells you, sorting by $x_i - y_i$ should give adjacent ones which you should compare and take max over them.
•  » » » » » » » » 4 years ago, # ^ |   +5 Thank you so much. Your explanation was really helpful.
•  » » » » » » » » 3 years ago, # ^ |   0 "So, now, you only need to go through the sorted list and take best value of adjacent indices." why do we have to iterate? Think of sorting them, say in ascending order, isn't the answer N-1th element? Because Nth element is the biggest element all over the array, and N-1th element is the second-biggest element, and when we get min of them it gives second biggest element.
•  » » » » » » » » » 3 years ago, # ^ |   0 It was an example to give some insight towards the intuition behind sorting. Ofcourse, from the function itself you can see that the second max is the required answer for the example.
•  » » » » » » » » » 3 years ago, # ^ |   0 Hi Samarth thank's for your explanation can you please simplify a bit more. i not able to understand it completely.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +7 Lets pick out subtask. There are two arrays: $x[1..n]$, $y[1..n]$. We need to maximize $min(x[i] + y[j], y[i] + x[j])$ for all $i$ != $j$.We can simply iterating $i$ and $j$ and update ans, but complexity is $O(n^2)$, not so good. But what happens, if we rearrange pairs $x[i],\,y[i]$ so that for fixed $j$ and all $i < j$: $min(x[i] + y[j],\,y[i] + x[j]) = x[i] + y[j].$Lets see the sample: [i] x y [0] 3 9 [1] 3 8 [2] 0 5 [3] 4 8 [4] 7 9 [5] 0 2 [6] 7 9 [7] 0 2 [8] 2 2 [9] 7 3 Let $j = 7$. As we can see, for all $i < 7$ $min(x[i] + y[7],\,y[i] + x[7]) = x[i] + y[7].$Considering this we can simply take the maximum value of all previous $x[i]$. This value we can take by maintaining $max_x$ on the preffix.Ok, but how we can rearrenge elements $x[i],\,y[i]$ to take $min(x[i] + y[j],\,y[i] + x[j]) = x[i] + y[j]$ for all $i < j$? Simply: $x[i] + y[j] <= y[i] + x[j]$equals to $x[i] - y[i] <= x[j] - y[j]$So, we can sort $x[i],\,y[i]$ by value $(x[i] - y[i])$ in not decreasing order.Total algorithm: vector > a(n); for (int i = 0; i < n; i++) a[i] = { x[i] - y[i], i }; sort(all(a)); int ans = 0, max_x = 0; for (int i = 0; i < n; i++) { ans = max(ans, max_x + y[a[i].second]); max_x = max(max_x, x[a[i].second]); } Explanation is turned out toooo long, but I hope it will be understood by everyone :)
•  » » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thank you a lot for your explanation, I think I got the idea, but I think there is a little typo over there : "But what happens, if we rearrange pairs x[i],y[i] so that for fixed i and all j>i:" Did you intend to say "for fixed j and all i
•  » » » » » » » » » 3 years ago, # ^ |   0 Yes, it is a typo... Ill fix it now!
•  » » » 4 years ago, # ^ |   0 Thanks that helped me. But one question isn't connecting 7 and 8 is also a solution here.
•  » » » » 4 years ago, # ^ |   +3 Yes, that works as well.
 » 4 years ago, # |   0 I found the distance of all the special nodes from node 1 then sorted the special nodes by their distance. Then added an edge between a pair of special nodes, which are closer than other pairs of special nodes. Finally calculated the shortest distance again and printed it. Where my approach gone wrong?71327933 :(
 » 4 years ago, # |   +19 Very Fast Editorial. Thanks FieryPhoenix
 » 4 years ago, # |   +1 I wonder in problem C let s be "aababaabb" and suppose the hidden message is : "aab" what's the number of occurrences of it ?
•  » » 4 years ago, # ^ |   +1 24 I guess
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 according to the code of sol, the answer is 15 !!
•  » » » » 4 years ago, # ^ |   0 Sorry, I forgot what the taks is, I counted all the subsequences that equal to given string
•  » » » » 4 years ago, # ^ |   +10 Notice that you can't consider all the "aab" subsequences. "She considers a string t as hidden in string s if t exists as a subsequence of s whose indices form an arithmetic progression"
•  » » » 4 years ago, # ^ |   0 It has to be in AP as well !
 » 4 years ago, # |   -13 Write solutions in C++ or python please, C is messy and unreadable (especially for D).
 » 4 years ago, # |   0 Can anyone explain me the editorial of C?
•  » » 3 years ago, # ^ |   +1 As we are only searching for those sub sequence, which have arithmetic progression, if the size is >2 like if we get a sub-sequence abc 5 times, we will obviously get subsequence ab 5 times,or even more :D . Thats why we are only checking between sub-sequence of size 1 and 2. Now, lets come to the code, there we have two array for memoization. In the first array arr1, we simply count the occurrence of char c upto i. In the second array arr2 ,at arr2[j][c] we add the occurrence of character j, before character c. Which ends up calculating, how many times we got sub-sequence jc upto ith position of the string. Then we find the maximum of occurrence of all those, sub-sequences of length 1 and 2. Which is the answer! :D Well, I know, you have solved this problem, but still wrote this whole just to "memoize" this technique in my memory! :p
 » 4 years ago, # |   0 On problem B in test case 1,15 is the maximum number and we have to reach at the point 10.So only 1 hop is needed in my opinion.So why max(2,ceil(d/max)) is the solution?
•  » » 4 years ago, # ^ |   0 I suppose you haven't completely understood the problem. It is not sufficient to go past the endpoint. On the last hop, you must land exactly at the endpoint. In the given example, just taking one hop can get you to x = 10 but your y would be sqrt(125). Hence, a minimum of two hops would be required. (0,0) -> (5,sqrt(200) -> (10,0). Hope you understood.
 » 4 years ago, # |   0 1307D — Cow and Fields Can anyone explain the editorial in more detail?
•  » » 4 years ago, # ^ |   +8 Sure, correct me if i am wrong tho. So basically we need max ( min(xa + yb,xb + ya)) over all a and b. Prev point is obv. Ok now , Suppose xa are x1 , x2 , x3 , .. xn and corrosponding yb are yb are y1, y2, y3 , ..... yn Now suppose u start with the first x1 and get max(y2,y3,y4, .. yn) this can be done using a suffix max array and thus u get max with O(1) . Suppose for x1 u get y5 to be max but here comes the most important part u don't know if x1 + y5 <= x5 + y1 or not !!!. So if not u check 2nd to largest number and thus overall complexity would be O(n^2) as u need to consider all cases of y for each x.So the trick here that is used is sorting on the basis of xi — yi. Now suppose we do what we were doing previously x1 + y5 we choose y5 from suffix max , so we are sure now that x1 + y5 <= x5 + y1 and we can proceed to the next x to get optimal y for it. and after considering all cases we get the max answer which is required. Also suppose the optimal path dosen't include any magic points. So we also check dist[0][n — 1] which is the distance from last point to 1st or vice versa . Thus we reduce complexity from O(n^2) to O(n logn).Hope it Helped
 » 4 years ago, # |   0 How would C change if the subsequences's indices didn't have to be in an arithmetic progression?
•  » » 4 years ago, # ^ |   0 Consider this example "aaabbbccc", there would be 27 occurrences of the string "abc". However, if we consider AP, there would only be 3.
•  » » » 4 years ago, # ^ |   0 I know I was asking if someone has a solution for this
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I think "aaaaabcbaaaabbbbbb" you should chose "aabaabbb" so the number of choice res = 2 * 3 * 2 * 2 * 2 * 2 so you count the longest continues string each part -- if the size is >= 2 ---- you will mutiple res with (1 << (cnt - 2) / 2) * (2 + cnt % 2) -- if the size is 1 ---- you skip it but remeber it to a save array with its charactor, then used it if meet it again bignum res = 1 int last[26] for i = 0 -> s.size() - 1 -- cnt = last[s[i] - 'a'] -- for j = i -> s.size() - 1 ---- if (s[j] != s[i]) ------ break; ----/ else cnt++ -- i = j -- if (cnt >= 2) ---- res = pw2((cnt - 2) / 2) + (2 + cnt % 2) -- last[s[i] - 'a'] = (cnt == 1); 
 » 4 years ago, # |   +56 In D solution can be made simpler by following observation. If there are two special fields with distances to $1$ and $n$ being $(x1, y1)$ and $(x2, y2)$ such that $x1 \le x2$ and $y1 \le y2$ then putting an edge between them won't make shortest path shorter. Because of that if we sort them by x they are automatically sorted by y as well :) (but in a different order). Then it makes sense to check only the neighbouring pairs in this order.
•  » » 4 years ago, # ^ |   +57 wtf I checked the neighboring pairs at first. But I thought it's incorrect and then resubmitted it before the end of the contest.
•  » » 4 years ago, # ^ |   0 Can you please tell me how are y automatically sorted if pairs are sorted by x. If I suppose I have distances to 1 and n be (x1 y1), (x2 y2), (x3 y3) be sorted by x. Then if we compare only the adjacent elements we never compare y1 and y3.How do we know that y2 < y1 and y3 >= y1 won't exist?
•  » » » 4 years ago, # ^ |   +22 Maybe I oversimplified my description, sorry for that. I meant the following:1) Sort pairs in nondescending order2) Check if there is any pair of pairs (x1, y1) and (x2, y2) such that x1<=x2 and y1<=y2. That can be done by checking only neighbouring pairs in that sorted order.2)1) If there is such a pair of pairs you can simply output original distance from 1 to n 2)2) If there isn't you can assume that y values are sorted in descending order
•  » » » » 4 years ago, # ^ |   0 Can you explain a bit more . I don't get how if we sort according to pair and check only neighbors we are assured x1 <= x2 and y1 <= y2. Is it not possible that (x1 <= x2 and y1 >= y2) and (x1 <= x3 and y1 <= y3).
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +16 But in your example if we sort by x then x2<=x3 and y2<=y1<=y3, so second and third pair are ones we are looking for. The fact that I use is that if sequence is not sorted in our favourite order there is a pair of neighbouring elements witnessing that.
•  » » » » » » 4 years ago, # ^ |   0 Gotcha, thanks for the explanation.
•  » » » » » » 4 years ago, # ^ |   0 Also u only take pairs for which x1 <= x2 and y1 <= y2. Can't there be a case where it's ok to take points for which x1 <= x2 and y1 >= y2.
•  » » » » » » » 4 years ago, # ^ |   0 Again. I distinguish two cases on whether a pair like x1<=x2 and y1<=y2 exists or not. If there is such a pair, I put an edge between corresponding vertices. If there isn't I know sorting by x in ascending order is equivalent to sorting y in descending order and I have a different reasoning for this case which amounts to basically the same thing done again — checking putting an edge between neighbouring vertices cause suffix maximum of ys is always in the beginning of that suffix.
 » 4 years ago, # |   0 In problem D, can anyone see why picking the two special fields farthest from n would not work?
•  » » 4 years ago, # ^ |   0 Consider the case: Test case$6$ $5$ $4$$1 3 5 6$$1$ $2$$2 3$$3$ $4$$4 6$$6$ $5$Connecting the farthest fields $1$ and $3$ is suboptimal compared to connecting $5$ and $6$.
•  » » » 4 years ago, # ^ |   0 Sorry, I should have specified: except for cases where there's already an edge between any two special fields (in such cases the answer will be "just build the extra bridge between two special fields that are already connected").
•  » » » » 4 years ago, # ^ |   +1 If you modify the test case slightly, the same reasoning holds. Connecting the farthest fields $1$ and $3$ is suboptimal compared to connecting $7$ and $8$. Test case$8$ $7$ $4$$1 3 7 8$$1$ $2$$2 3$$3$ $4$$4 5$$5$ $8$$8 6$$6$ $7$
•  » » » » » 4 years ago, # ^ |   +8 Thank you!
•  » » » » » 4 years ago, # ^ |   0 Problem D: I sorted d1[a] < d1[b] and maximized result by getting sum of the neighboring pairs d1[a[i]] + dn[a[i+1]]. It was accepted. But i think it go wrong if a[i] or a[i+1] is not on the path from 1 to n because dn[] is not decreasing. Was my observation is wrong ?? And does my compare function really work ?? Thank advance ^_^
 » 4 years ago, # |   +13 Thanks for the fast tutorial <3 Thanks for the problems <3 Thanks problem setters <3
•  » » 4 years ago, # ^ |   +12 Thanks for participating <3
•  » » » 4 years ago, # ^ |   0 Thanks for answering my questions <3 But sorry for not having done C-problem ;-;
 » 4 years ago, # |   0 Maybe it was a big deal of fault on me. I failed to notice the possibility of precisely an favorite number of $x$. so I only counted on the $Maximum$ and failed on pretest 2.
 » 4 years ago, # | ← Rev. 2 →   +1 Can someone explain Problem B more intuitively ?
•  » » 4 years ago, # ^ |   0 emm，I think the picture maybe ...
•  » » 4 years ago, # ^ |   +1 yes, I too couldn't really get the mathematical intuition behind the problem.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Lets name the biggest number in array a ,L.At first move to right until your dour distance to destination is less than l.If your not at the destination you just need to make sure that you can move to destination with two moves.Imagine tor in point y and destination is in point x. Draw a two circle with diameter l. One from the central point x and one from y. You can go to the intersection of these two circles from y and then go to x.This picture might help.
•  » » » 4 years ago, # ^ |   0 Is it necessary that he will always use one single number. How about the rabbit moves to right until the destination is less than L(the largest fav. number) but the remaining distance is one of the fav number. He can complete it in 1 single move instead of making 2 moves using the L(the largest fav. number)
•  » » » » 4 years ago, # ^ |   +3 Hi! I think that the official solution works in both cases (1st case: we can use multiple times a single [favorite] number; 2nd case: we can use multiple times all [favorite] numbers). Regarding the situation you described above, look at the following example:Input:2 103 1Output:4 1st case (4 hops): (0, 0) -> (3, 0) -> (6, 0) -> (8, sqrt(5)) -> (10, 0);2nd case (4 hops): (0, 0) -> (3, 0) -> (6, 0) -> (9, 0) -> (10, 0).So, the answer is the same in both cases. The main idea is to use the last 2 hops to cover the range [6, 10], not the range [9, 10] as you initially thought.
•  » » 4 years ago, # ^ |   0 You can reach up to (5* k) distance to any point using k jumps (chosen favourite number 5)
 » 4 years ago, # |   0 In problem B , after reaching (d,0) what is the guarantee that the last two hops will cover the remaining distance and it's always will be a favorite number ? Can anyone explain a bit further ?
•  » » 4 years ago, # ^ |   +8 I got it
 » 4 years ago, # |   0 In the solution of problem F , does someone could tell me what does int A2=walk(A,B,K+1),B2=walk(B,A,K+1); mean ? It seems that A2,B2 hasn't been used. Thanks in advance.FieryPhoenix
•  » » 4 years ago, # ^ |   +3 Yes, you are right. That line is unnecessary and was from debugging. Edited the code :)
 » 4 years ago, # |   0 In my code, the output is the next input.https://codeforces.com/contest/1307/submission/71311150if you input : 2 4 230023 12 12 2000 124 230023 19 43 200 434 1000you will find the second test is print 531.
•  » » 4 years ago, # ^ |   0 I was wrong
•  » » 4 years ago, # ^ |   0 help me! B!https://codeforces.com/contest/1307/submission/71377477if you input 1 2 4 1 3.i use the arrays to keep the favorite numbers.but the a[0] sunddenly become 4.i do not understand why the a[0] is change.please help me! thanks!
•  » » » 4 years ago, # ^ |   0 Replace "if (a[i] = x)" with "if (a[i] == x)"
 » 4 years ago, # |   0 For the problem E Does anyone have another solution to the E problem?
 » 4 years ago, # | ← Rev. 2 →   0 Sorry my solution is wrong.[deleted]
 » 4 years ago, # | ← Rev. 2 →   -16 .
 » 4 years ago, # |   0 Problem D: I sorted d1[a] < d1[b] and maximized result by getting sum of the neighboring pairs d1[a[i]] + dn[a[i+1]]. It was accepted. But i think it go wrong if a[i] or a[i+1] is not on the path from 1 to n because dn[] is not decreasing. Was my observation is wrong ?? And does my compare function really work ?? Can anyone explain to me ?! Thank advance ^_^
 » 4 years ago, # |   0 In 1307D - Корова и поля, can someone explain how to maximize min(xa+yb,ya+xb)?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Okay I'll try. Let's iterate over x_a and find some y_b s.t b>a (we can maintain a suffix maximum array and check for b from [a+1,n]), and let's say for all iterations it is the maximum answer. So are we done ? No because we never checked that if x_a + y_b <= x_b + y_a or not. So to check this as well simply means complexity goes to O(n**2).So what should we do ?We have two arrays x and y right. Let's sort them according ( x_i — y_i ) in ascending order and let's again follow the above procedure (In mind just think that field number's have been changed). Now again I iterate over x say I am at x_a and every time suing suffix maximum array I select a some value from [a+1,n]. say we get y_b. Using sorting we now don't have to worry than if weather x_b + y_a is smaller than x_a + y_b or not because the former one will always be greater. In short we reduced the some unnecessary computation and still being able to find the actual answer.
•  » » » 3 years ago, # ^ |   0 Thanks a lot bro, it really helped.
 » 4 years ago, # |   0 Can anyone tell me where I went wrong.(https://codeforces.com/contest/1307/submission/71392396) I used Dijkstra to find the shortest path, and checked the special fields in the shortest path. If the count of special fields equals k then I take those special fields which are closest, else print the shortest path length in dijkstra.
 » 4 years ago, # |   0 Why sort in problem D is needed? I cant imagine why is necessary. Can anyone help?
•  » » 4 years ago, # ^ |   +8 I got it. My main problem was the second inequality (where it comes from). So if we want maximize this inequality (without loss of generality, suppose): xa + yb ≤ ya + xb.We can now modify this inequality to: xa — xb ≤ ya — yb and now this is prove, sort is helpful (sort do this).
 » 4 years ago, # |   0 Please explain to me the greedy strategy for D: Now we want to maximize xa+yb subject to xa−ya≤xb−yb. This can be done by sorting by xi−yi and iterating a over x while keeping a suffix maximum array of y to compute maxb>ayb. FieryPhoenix
•  » » 4 years ago, # ^ |   0 yes please. I couldn't get how to maximize??
 » 4 years ago, # |   +22 Problem 1307D - Корова и поля can be solved in linear time 71305246 doing a topological sort over the shortest paths graph.
•  » » 4 years ago, # ^ |   0 How does your code work? Can you explain more detailly ? Thanks.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +19 Every edge that don't belong to the shortest paths graph from node $1$ can be deleted, because it isn't optimal traverse along it before take the added edge, so the graph now is a DAG and have a topological order, in that order the added edge connect two special nodes so for every special node $u$ if it's a extreme of the new edge is optimal connect $u$ with the node that maximize the distance from $n$(in the original graph) and is at the right of $u$ in the topological order.
•  » » 4 years ago, # ^ |   0 We can also use the bucket sort in $O(n)$ instead of $O(n \log n)$.
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +11 Yeah, But I wanted to share another solution that involve more thinking about graphs and for my it's cool and simple. Btw you are one of my favorite L$\color{red}{\textrm{GM}}$.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 thanks for your code.I was stuck on the problem for a long time, and through your thought, write a reduced version 71464704It can use the order of bfs queue instead the topological sort. because for v in g[u] there does not exist a node q such that have an edge (q, v) and d[q] != d[u], so we can ignore the degree of a node.
•  » » » 4 years ago, # ^ |   +3 You can ignore the degree of a node because the bfs order is a topological order of the shortest paths graph, awesome ;)
•  » » » 4 years ago, # ^ |   +8 I have another explanation from bfs order.let special node a, b satisfy d(a) < d(b) and have an edge, then it can prove d(a) + 1 + dn(b) <= d(b) + 1 + dn(a)there are 3 cases would be consider:d(n) < d(a) < d(b) then the shortest path just consider 1 to nd(a) < d(n) < d(b) then the shortest path just consider 1 to n or 1 to a to nd(a) < d(b) < d(n) d(a) + 1 < d(b) + 1, |dn(b) — dn(a)| = 1 since they have an edge note if x ∈ {a, b} s.t. d(x) + dn(x) > d(n), then the shortest path would not walk through x.
 » 4 years ago, # |   0 Can someone explain problem B more elaborately. I am not able to understand this part "This is true because clearly the answer is at least ⌈d/y⌉: if it were less Rabbit can't even reach distance d away from the origin."
•  » » 4 years ago, # ^ | ← Rev. 4 →   +8 consider y = 2, d = 7then 2 + 2 + 2 + 2 > 7 if less than d would be like 2 + 2 + 2 < 7 2 + 2 < 7 2 < 7 all above can not reach the (d, 0)the key point is if the last hop exceed (d, 0), it should hop 2 steps with different directions to the target.my code: 71503153
 » 4 years ago, # |   0 https://codeforces.com/contest/1307/submission/71438968 Can anyone please tell why my code is giving RUNTIME ERROR on testcase 6 ?
 » 4 years ago, # | ← Rev. 2 →   -8 problem D can be solved using a random)
 » 4 years ago, # | ← Rev. 2 →   0 In problem D, I'm getting Wrong answer on Test case 9 if I am using STL map in c++, while on submitting using vector pair and sorting I'm getting Accepted. Can you help why is this happening.Solution with map : https://codeforces.com/contest/1307/submission/71540983solution with Vector pair : https://codeforces.com/contest/1307/submission/71540823map and vector are initialized on Line 71.
•  » » 4 years ago, # ^ |   -10 the map store only one value for the same key. You may use multimap
•  » » » 4 years ago, # ^ |   +1 Got it thanks, how could I forget about it. Anyways Thanks
•  » » » 4 years ago, # ^ |   +8 Why down voting? I just wanted to help
 » 4 years ago, # | ← Rev. 2 →   +3 I'm gonna explain other approach for D cows and field, it is somewhat similar as explained in tutorial but is easier to understand first of all find distance of each node from source and destination which can be easily done by bfs . now sort all the special nodes with respect to their distance from destination now consider two special nodes 'a' and 'b' , dist of 'a' from source is x, dist of 'b' from destination is y and dist between 'a' and 'b' is z (z>1) and as of now shortest path was x+z+y but if we connect 'a' and 'b' the shortest path becomes x+y+1 which is lesser than the previous one as soon as we connect two special nodes some intermediate nodes are skipped and shortest path is decreased. we want to minimize the skipped nodes such that decrease in shortest path is minimum. now the special nodes are sorted with respect to their distance from destination Traverse the special nodes and try connecting each special node with next special node and calculate shortest path after each connection and return maximum answer here is my solution https://codeforces.com/contest/1307/submission/71542301
 » 4 years ago, # |   0 can anyone explain in problem B why are we doing ceil(x/far) for x>=far?? Thanks in advance:)
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 lets assume x = total distance to cover and far = max jump size if x == far then the ans is 1 straight away. In this question a greedy approach is, we can just do all the jumps horizontally with max jumps size, if x is divisible by max jump size then ans will be just (x/far) no need of ceil function but if x is not divisible by far then a small distance will be left at the end, so to handle that last two jumps will not be horizontal they will make a triangle like this due to which we will have to use ceil functionthis image will help you understand better https://postimg.cc/ctMvVrCg
 » 4 years ago, # |   +16 I can't understand this part of code in your solution for problem F. if(depth[A]+depth[B]-2*depth[C]<=2*K){ return true; } Should't it look like these? if(depth[A]+depth[B]-2*depth[C]<=K){ return true; } 
•  » » 4 years ago, # ^ | ← Rev. 3 →   +16 To make the implementation easier, we split every edge into two (as described in the editorial). Therefore, two nodes can reach each other directly if their distance $\le$ $2K$.
•  » » » 4 years ago, # ^ |   +8 Why splitting each edge into two with an additional node makes the implementation easier?
•  » » » » 4 years ago, # ^ |   0 ok, I am kinda get it. Basically the idea is rest stop groups expand their reach radius by k/2, and non rest stop cities make are trying to walk distance of k/2 to reach any rest stop groups.But when k is odd, it's complicated to divide the breaking point.Am I right?
•  » » » » » 4 years ago, # ^ |   +19 Well, the complicated case is when the distance between two nodes is odd, because there is no easy breaking point for our parallel BFS. Splitting edges into two guarantee that all pairwise distances between nodes are even.
•  » » » » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # | ← Rev. 2 →   +8 If someone failing in D, he/she can try this case too. 13 12 2 1 9 1 2 2 3 3 4 4 5 1 6 6 7 7 8 8 9 1 10 10 11 11 12 12 13
 » 4 years ago, # | ← Rev. 2 →   0 What is the intuition in sorting x_i - y_i? I needed to sort the special vertices in such a way that in any shortest path involving two special vertices x and y, x comes before y in the shortest path. I did sorting by {-y_i, x_i} because I want to get farthest from n first, then tie break by closest to 1`. I got AC for this.
 » 4 years ago, # | ← Rev. 2 →   0 This is deleted
 » 4 years ago, # |   0 Editorial for problem C turns out to be wrong.for case aabbccit gives answer 4 but answer is supposed to be 8abc (1,3,5) (1,3,6) (1,4,5) (1,4,6) (2,3,5) (2,3,6) (2,4,5) (2,4,6)correct me if i am wrong
•  » » 4 years ago, # ^ |   0 indices are not in AP (1,3,6) (1,4,5).....
 » 3 years ago, # |   +1 Nice Editorial and wonderful problems
 » 2 years ago, # |   +3 editorial is not working for me, is there any way to fix
 » 5 months ago, # |   0 For those who dont really understand 1307D - Корова и поля, here's my code that might help u. I have put some personal notes in there: 214379142
 » 4 months ago, # |   0 For question C https://codeforces.com/problemset/problem/1307/C In test case lolollll lol will be 8 and lo will be at max 3 times. So here the explaination provided for question C proves wrong can anyone pls verify.