### FieryPhoenix's blog

By FieryPhoenix, 8 months 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

 » 8 months ago, # | ← Rev. 2 →   -10 wonderful problems and nice contest
•  » » 8 months ago, # ^ |   -8 its an editorial, not sufficient in this case)
 » 8 months ago, # |   0 Test Case 7 of C?
•  » » 8 months 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
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 case of 2 same letters I suppose, because I fixed that and got AC
•  » » 8 months ago, # ^ |   +6 I think it's 1e5 aaaa..... I got WA on Test 7 fixed after changing int to long long
•  » » 6 weeks 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.
 » 8 months 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)
•  » » 8 months 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.
 » 8 months 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?
•  » » 8 months 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.
•  » » » 8 months 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.
•  » » » » 8 months 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.
•  » » » » » 8 months 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?
•  » » » » » » 8 months 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.
 » 8 months ago, # |   0 Why does my B fail? 71327169.Answer is min over all ceil(x/itr) if itr>=x or 2 if itr
•  » » 8 months ago, # ^ |   +12 Why does $answer$ equal to $x$ in the beginning? Shouldn't it be $inf$ or something? Consider test $1$ $1$ $2$
•  » » » 8 months ago, # ^ |   +11 Dammit!! Thanks bud.
 » 8 months 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
•  » » 8 months ago, # ^ |   +67 Thank you for the positive feedback! We tried our best to make a round everyone would enjoy.
 » 8 months ago, # |   -96 Thanks a lot for this contest.Another name added to my shit problemsetters list. :)
•  » » 8 months ago, # ^ |   +64 Hi! I am open to constructive feedback. Which part did you have problems with?
•  » » » 8 months 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.
•  » » » » 8 months 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).
•  » » » » » 8 months ago, # ^ |   0 Hmm that's true, I hadn't thought of that.
 » 8 months 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".
•  » » 8 months 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
•  » » 8 months ago, # ^ |   0 I also did the same, but this approach gives WA. I couldn't understand the reason behind it.My code : 71327190
•  » » 8 months 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 
•  » » 8 months 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?
•  » » » 8 months ago, # ^ |   +8 Indeed pretty weird that people are downvoting. Im simply trying to learn where i went wrong
 » 8 months ago, # | ← Rev. 2 →   +35 .
 » 8 months ago, # |   0 Your solution to second problem is O(nlog(n)), not O(n), because you are using set.
•  » » 8 months 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.
 » 8 months 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.
•  » » 8 months ago, # ^ |   0 Similar approach, same question :( 71327933
•  » » 8 months 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.
•  » » » 8 months 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
•  » » 8 months 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!
•  » » » 8 months 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?
•  » » » » 8 months 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.
•  » » » » » 8 months ago, # ^ |   -21 Pretty cool, do you know any other problems that use this idea?
•  » » » » 8 months 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$.
•  » » » » » 8 months ago, # ^ |   +3 Really good intuition. Thank you!
•  » » » » » 8 months 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 :)
•  » » » » » » 8 months ago, # ^ |   0 I don't get it. Can you please explain why would it always be smaller than or equal to xb + ya ?
•  » » » » » » » 8 months ago, # ^ |   0 Coz you sorted according to the constraint
•  » » » » » » » » 8 months ago, # ^ |   0 Much appreciated ,but i still don't get it.
•  » » » » » » » 8 months 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.
•  » » » » » » » » 8 months ago, # ^ |   +5 Thank you so much. Your explanation was really helpful.
•  » » » » » » » » 8 months ago, # ^ |   0 Wow, that is the most clear explanation of this trick here. Thanks a lot.
•  » » » » » » » 4 months ago, # ^ |   +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 $i$ and all $j > i$: $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 :)
•  » » » 8 months ago, # ^ |   0 Thanks that helped me. But one question isn't connecting 7 and 8 is also a solution here.
•  » » » » 8 months ago, # ^ |   +3 Yes, that works as well.
 » 8 months 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 :(
 » 8 months ago, # |   +19 Very Fast Editorial. Thanks FieryPhoenix
 » 8 months 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 ?
•  » » 8 months ago, # ^ |   +1 24 I guess
•  » » » 8 months ago, # ^ | ← Rev. 2 →   +1 according to the code of sol, the answer is 15 !!
•  » » » » 8 months ago, # ^ |   0 Sorry, I forgot what the taks is, I counted all the subsequences that equal to given string
•  » » » » 8 months 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"
•  » » » 8 months ago, # ^ |   0 It has to be in AP as well !
 » 8 months ago, # |   -13 Write solutions in C++ or python please, C is messy and unreadable (especially for D).
 » 8 months ago, # |   0 Can anyone explain me the editorial of C?
•  » » 3 months 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 weeks ago, # ^ |   0 thanks a lot, A_Campaigner
 » 8 months 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?
•  » » 8 months 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.
•  » » » 8 months ago, # ^ |   0 I got it later...Thanks
•  » » 8 months ago, # ^ |   0 You would end up bouncing away from the intended position. If you take a jump of 15 length and you want to reach 10. You would end up jumping over. So you need two jumps since the plane is 2D you can take a jump of let's suppose x,y such that the euclidean distance is of 15 then take another jump of same distance to reach 10.
•  » » » 8 months ago, # ^ |   0 I found out the logic later that I had to get exactly at the point x,y..Thank you.
 » 8 months ago, # |   0 1307D — Cow and Fields Can anyone explain the editorial in more detail?
•  » » 8 months 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
 » 8 months ago, # |   0 How would C change if the subsequences's indices didn't have to be in an arithmetic progression?
•  » » 8 months 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.
•  » » » 8 months ago, # ^ |   0 I know I was asking if someone has a solution for this
•  » » » » 8 months 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); 
 » 8 months 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.
•  » » 8 months 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.
•  » » 8 months 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?
•  » » » 8 months 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
•  » » » » 8 months 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).
•  » » » » » 8 months 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.
•  » » » » » » 8 months ago, # ^ |   0 Oh right , that works. Mind Blown :O
•  » » » » » » 8 months ago, # ^ |   0 Gotcha, thanks for the explanation.
•  » » » » » » 8 months 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.
•  » » » » » » » 8 months 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.
•  » » » » » » » » 8 months ago, # ^ |   0 Oh got it thanks a lot
 » 8 months ago, # |   0 In problem D, can anyone see why picking the two special fields farthest from n would not work?
•  » » 8 months 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$.
•  » » » 8 months 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").
•  » » » » 8 months 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$
•  » » » » » 8 months ago, # ^ |   +8 Thank you!
•  » » » » » 8 months 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 ^_^
 » 8 months ago, # |   +13 Thanks for the fast tutorial <3 Thanks for the problems <3 Thanks problem setters <3
•  » » 8 months ago, # ^ |   +12 Thanks for participating <3
•  » » » 8 months ago, # ^ |   0 Thanks for answering my questions <3 But sorry for not having done C-problem ;-;
 » 8 months 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.
 » 8 months ago, # | ← Rev. 2 →   +1 Can someone explain Problem B more intuitively ?
•  » » 8 months ago, # ^ |   0 emm，I think the picture maybe ...
•  » » 8 months ago, # ^ |   +1 yes, I too couldn't really get the mathematical intuition behind the problem.
•  » » 8 months 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.
•  » » » 8 months 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)
•  » » » » 8 months 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.
•  » » 8 months ago, # ^ |   0 You can reach up to (5* k) distance to any point using k jumps (chosen favourite number 5)
 » 8 months ago, # |   0 community,I am concerned about recent plag. detector.Just change some code structure and just see how this guy https://codeforces.com/submissions/genotepic named Mohan Sirvi,shamelessly copied code from https://codeforces.com/profile/NoLongerRed from ideone and he should not go unpunished. Look at submission of C and at some extent B. NoLongerRed forgot private,and result this genotepic copied.I found it because i was going through some random submissions for problem C which i can understand apart from solution provided.After that i thought this issue should be brought in front of public. I think there should be award section who successfully get a cheater.
 » 8 months 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 ?
•  » » 8 months ago, # ^ |   +8 I got it
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you explain how could you get it ?
•  » » » 8 months ago, # ^ |   0 The best case is straight forward.You just check whether the number exists or not in your list. But In the worst case If you reach (d,0) as explained then you have to understand that you can generate any number by your last 2 hops.Suppose you are in (x1,y1) = (d,0) and your destination is (x3,y3) where y1 & y3 are always 0 . You can pick any intermediate stage (x2,y2) so that the euclidean distance is always a favorite number because x2,y2 can be floating point number and you can pick independently
 » 8 months 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
•  » » 8 months ago, # ^ |   +3 Yes, you are right. That line is unnecessary and was from debugging. Edited the code :)
 » 8 months 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.
•  » » 8 months ago, # ^ |   0 I was wrong
•  » » 8 months 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!
•  » » » 8 months ago, # ^ |   0 Replace "if (a[i] = x)" with "if (a[i] == x)"
 » 8 months ago, # |   0 For the problem E Does anyone have another solution to the E problem?
 » 8 months ago, # | ← Rev. 2 →   0 Sorry my solution is wrong.[deleted]
 » 8 months ago, # | ← Rev. 2 →   -16 .
 » 8 months 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 ^_^
 » 8 months ago, # |   0 In 1307D - Cow and Fields, can someone explain how to maximize min(xa+yb,ya+xb)?
•  » » 4 months 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.
•  » » » 4 months ago, # ^ |   0 Thanks a lot bro, it really helped.
 » 8 months ago, # |   0 Can someone explain to me the main idea of C, please?
 » 8 months 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.
 » 8 months ago, # |   0 Why sort in problem D is needed? I cant imagine why is necessary. Can anyone help?
•  » » 8 months 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).
 » 8 months 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
•  » » 7 months ago, # ^ |   0 yes please. I couldn't get how to maximize??
 » 8 months ago, # |   +22 Problem 1307D - Cow and Fields can be solved in linear time 71305246 doing a topological sort over the shortest paths graph.
•  » » 8 months ago, # ^ |   0 How does your code work? Can you explain more detailly ? Thanks.
•  » » 8 months 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.
•  » » 8 months ago, # ^ |   0 We can also use the bucket sort in $O(n)$ instead of $O(n \log n)$.
•  » » » 8 months 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}}$.
•  » » 8 months 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.
•  » » » 8 months ago, # ^ |   +3 You can ignore the degree of a node because the bfs order is a topological order of the shortest paths graph, awesome ;)
•  » » » 8 months 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.
 » 8 months 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."
•  » » 8 months 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
 » 8 months ago, # |   0 https://codeforces.com/contest/1307/submission/71438968 Can anyone please tell why my code is giving RUNTIME ERROR on testcase 6 ?
 » 8 months ago, # |   0 Can anyone explain solution of problem c in more detail?
 » 8 months ago, # | ← Rev. 2 →   -8 problem D can be solved using a random)
 » 8 months 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.
•  » » 8 months ago, # ^ |   -10 the map store only one value for the same key. You may use multimap
•  » » » 8 months ago, # ^ |   +1 Got it thanks, how could I forget about it. Anyways Thanks
•  » » » 8 months ago, # ^ |   +8 Why down voting? I just wanted to help
 » 8 months 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
 » 8 months ago, # |   0 can anyone explain in problem B why are we doing ceil(x/far) for x>=far?? Thanks in advance:)
•  » » 8 months 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
•  » » » 8 months ago, # ^ |   0 thanks alot bro....great explaination:)
 » 8 months ago, # |   0 I'm not sure if the solution to 1307C is correct because of the case where s = aabcc. In this case, the hidden string is 'abc' with 'a' being s[0], 'b' being s[2] and 'c' being s[4]. Please correct me if I'm wrong.
•  » » 8 months ago, # ^ |   0 Nevermind, I misunderstood a requirement of the problem
 » 7 months ago, # |   0 FieryPhoenixCan you please simply explain the use of array 'q' in problem D ?thanks.
 » 7 months ago, # |   0 Hey can anyone explain me solution for 1307C I am not able to understand why considering only string length of 2 works. Thank you!
 » 7 months 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; } 
•  » » 7 months 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$.
•  » » » 7 months ago, # ^ |   +8 Why splitting each edge into two with an additional node makes the implementation easier?
•  » » » » 7 months 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?
•  » » » » » 7 months 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.
•  » » » » » » 7 months ago, # ^ |   0 Thanks
 » 6 months ago, # |   0 Can anyone explain me the Cow and message problem in more details please ?
•  » » 3 months ago, # ^ |   0 In this problem, you need to find the maximum repeated subsequence that can be formed by the characters present in AP (Arithmetic Position) indices. Example if you are given a string "aaabb" then one of the subsequences may be "aab" how many times it occurs in a string such that all the characters you choose in the original string for matching are in AP (Arithmetic Progression).The basic idea behind this problem is simple if you are quite observing this- If you were to find the maximum repeating subsequence from the given string then it can only be possible when you are considering 2 character string or a single character string. Think this in the following way, if a subsequence can occur with the foundation of being 3 or more in length then wouldn't it be more when only there are 2 characters in it. So a string greater than length 2 would be limiting the subsequence from occurring more times. For example, if aab can occur in the above string "aab" 2 times (set of indices) (1, 3, 5) and (2, 3, 4) then what about subsequence "ab"? It would be** occurring more or equal to "aab"**. "ab" will claim its own existence in a string as well as where it occurs in "aab". This becomes the origin of this problem, no subsequence of length 3 or greater is significant since corresponding to each of them we can get 2 length string which would be occurring more or equal number of times. "ab" occurs for 6 times (following the rules of AP indices) and "aab" occurs twice (in which "ab" is included as a subsequence) so of course length 2 subsequence would be occurring more than others or equal to others without any conditions. The second line of thought you can go through is, what is the best way possible to have an AP having a common difference of your choice and having a length greater than 1? "Its length 2" So a 2 character sequence can take any values of d (common difference in AP) in order to match with our target sequence. "ab" can be matched more easily with any subsequence of "aaabb" more easily and more frequently than "aab" and if you generalize this to higher numbers 3, 4, 5... then you will get that. Hope that helps
 » 6 months 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
 » 6 months 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.
 » 6 months ago, # | ← Rev. 2 →   0 This is deleted
 » 5 months 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
•  » » 5 months ago, # ^ |   0 indices are not in AP (1,3,6) (1,4,5).....
•  » » » 5 months ago, # ^ |   0 Yeah I realised that recently but forgot to delete this comment.Anyways Thanks for concern.
 » 6 weeks ago, # |   +1 Nice Editorial and wonderful problems