FieryPhoenix's blog

By FieryPhoenix, 7 weeks ago, In English,

1307A - Cow and Haybales

Idea: FieryPhoenix

Tutorial
Solution
Alternative O(n) Solution:

1307B - Cow and Friend

Idea: dragonslayerintraining

Tutorial
Solution

1307C - Cow and Message

Idea: dragonslayerintraining

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

Idea: dragonslayerintraining

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +159
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

wonderful problems and nice contest

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Test Case 7 of C?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    case of 2 same letters I suppose, because I fixed that and got AC

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I think it's 1e5 aaaa..... I got WA on Test 7 fixed after changing int to long long

»
6 weeks ago, # |
  Vote: I like it +85 Vote: I do not like it

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)

»
6 weeks ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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?

Code: https://pastebin.com/62MjcNeL

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 it

    In this test, the very first centroid is the only rest stop.

    EDIT: The first line of the test was not visible.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +8 Vote: I do not like it

      Your test seems to be missing one edge. Could you please be more specific? I don't understand what you mean in your comment.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it +8 Vote: I do not like it

          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?

          New code: https://codeforces.com/contest/1307/submission/71366378

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            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 code

            You can omit vertices 9-15 in a drawing, they just force the centroid to be 4.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why does my B fail? 71327169.
Answer is min over all ceil(x/itr) if itr>=x or 2 if itr<x for all itr

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Why does $$$answer$$$ equal to $$$x$$$ in the beginning? Shouldn't it be $$$inf$$$ or something?
    Consider test
    $$$1$$$ $$$1$$$
    $$$2$$$

»
6 weeks ago, # |
  Vote: I like it +30 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +67 Vote: I do not like it

    Thank you for the positive feedback! We tried our best to make a round everyone would enjoy.

»
6 weeks ago, # |
  Vote: I like it -96 Vote: I do not like it

Thanks a lot for this contest.

Another name added to my shit problemsetters list. :)

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +64 Vote: I do not like it

    Hi! I am open to constructive feedback. Which part did you have problems with?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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).

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Hmm that's true, I hadn't thought of that.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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".

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    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
    

    graph

    Connecting 3 and 5 will not reduce the shortest path

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I also did the same, but this approach gives WA. I couldn't understand the reason behind it.

    My code : 71327190

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Indeed pretty weird that people are downvoting. Im simply trying to learn where i went wrong

»
6 weeks ago, # |
  Vote: I like it +35 Vote: I do not like it

Managed to solve D during the contest for the first time :) thanks a lot for the hybrid contest

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Your solution to second problem is O(nlog(n)), not O(n), because you are using set.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In D, can anyone explain why my solution is wrong?

my solution

My 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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Similar approach, same question :( 71327933

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    Hi! Consider this case:

    Test case

    Your solution incorrectly connects node $$$1$$$ and $$$8$$$. Optimal solution connects $$$1$$$ and $$$7$$$. Hope this makes sense!

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it -21 Vote: I do not like it

          Pretty cool, do you know any other problems that use this idea?

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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$$$.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Really good intuition. Thank you!

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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 :)

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I don't get it. Can you please explain why would it always be smaller than or equal to xb + ya ?

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Coz you sorted according to the constraint

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Much appreciated ,but i still don't get it.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
              Rev. 2   Vote: I like it +6 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                6 weeks ago, # ^ |
                  Vote: I like it +5 Vote: I do not like it

                Thank you so much. Your explanation was really helpful.

              • »
                »
                »
                »
                »
                »
                »
                »
                3 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Wow, that is the most clear explanation of this trick here. Thanks a lot.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks that helped me. But one question isn't connecting 7 and 8 is also a solution here.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :(

»
6 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Very Fast Editorial. Thanks FieryPhoenix

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

I wonder in problem C let s be "aababaabb" and suppose the hidden message is : "aab" what's the number of occurrences of it ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    24 I guess

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      according to the code of sol, the answer is 15 !!

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Sorry, I forgot what the taks is, I counted all the subsequences that equal to given string

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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"

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It has to be in AP as well !

»
6 weeks ago, # |
  Vote: I like it -13 Vote: I do not like it

Write solutions in C++ or python please, C is messy and unreadable (especially for D).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me the editorial of C?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I found out the logic later that I had to get exactly at the point x,y..Thank you.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

1307D — Cow and Fields Can anyone explain the editorial in more detail?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How would C change if the subsequences's indices didn't have to be in an arithmetic progression?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider this example "aaabbbccc", there would be 27 occurrences of the string "abc". However, if we consider AP, there would only be 3.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know I was asking if someone has a solution for this

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it
        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);
        
»
6 weeks ago, # |
  Vote: I like it +56 Vote: I do not like it

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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +57 Vote: I do not like it

    wtf I checked the neighboring pairs at first. But I thought it's incorrect and then resubmitted it before the end of the contest.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Maybe I oversimplified my description, sorry for that. I meant the following:

      1) Sort pairs in nondescending order

      2) 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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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).

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 2   Vote: I like it +16 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Oh right , that works. Mind Blown :O

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Gotcha, thanks for the explanation.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, can anyone see why picking the two special fields farthest from n would not work?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Consider the case:

    Test case

    Connecting the farthest fields $$$1$$$ and $$$3$$$ is suboptimal compared to connecting $$$5$$$ and $$$6$$$.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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").

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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
        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          Thank you!

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 ^_^

»
6 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

Thanks for the fast tutorial <3 Thanks for the problems <3 Thanks problem setters <3

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Thanks for participating <3

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for answering my questions <3 But sorry for not having done C-problem ;-;

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 weeks ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

Can someone explain Problem B more intuitively ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    emm,I think the picture maybe ...

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    yes, I too couldn't really get the mathematical intuition behind the problem.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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)

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        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 10
        3 1
        Output:
        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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can reach up to (5* k) distance to any point using k jumps (chosen favourite number 5)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I got it

  • »
    »
    6 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you explain how could you get it ?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes, you are right. That line is unnecessary and was from debugging. Edited the code :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In my code, the output is the next input.

https://codeforces.com/contest/1307/submission/71311150

if you input : 2 4 230023 12 12 2000 12

4 230023 19 43 200 434 1000

you will find the second test is print 531.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem E Does anyone have another solution to the E problem?

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Sorry my solution is wrong.[deleted]

»
6 weeks ago, # |
Rev. 2   Vote: I like it -16 Vote: I do not like it

.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ^_^

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

In 1307D - Cow and Fields, can someone explain how to maximize min(xa+yb,ya+xb)?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain to me the main idea of C, please?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why sort in problem D is needed? I cant imagine why is necessary. Can anyone help?

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Problem 1307D - Cow and Fields can be solved in linear time 71305246 doing a topological sort over the shortest paths graph.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How does your code work? Can you explain more detailly ? Thanks.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    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.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can also use the bucket sort in $$$O(n)$$$ instead of $$$O(n \log n)$$$.

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 3   Vote: I like it +11 Vote: I do not like it

      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}}$$$.

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    thanks for your code.

    I was stuck on the problem for a long time, and through your thought, write a reduced version 71464704

    It 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.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      You can ignore the degree of a node because the bfs order is a topological order of the shortest paths graph, awesome ;)

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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 n

      d(a) < d(n) < d(b)
      then the shortest path just consider 1 to n or 1 to a to n

      d(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.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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."

  • »
    »
    6 weeks ago, # ^ |
    Rev. 4   Vote: I like it +8 Vote: I do not like it

    consider y = 2, d = 7

    then 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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1307/submission/71438968 Can anyone please tell why my code is giving RUNTIME ERROR on testcase 6 ?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain solution of problem c in more detail?

»
6 weeks ago, # |
Rev. 2   Vote: I like it -8 Vote: I do not like it

problem D can be solved using a random)

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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/71540983
solution with Vector pair : https://codeforces.com/contest/1307/submission/71540823

map and vector are initialized on Line 71.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    the map store only one value for the same key. You may use multimap

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Got it thanks, how could I forget about it. Anyways Thanks

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Why down voting? I just wanted to help

»
6 weeks ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain in problem B why are we doing ceil(x/far) for x>=far?? Thanks in advance:)

  • »
    »
    6 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    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 function
    this image will help you understand better https://postimg.cc/ctMvVrCg

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

FieryPhoenix

Can you please simply explain the use of array 'q' in problem D ?

thanks.

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey can anyone explain me solution for 1307C I am not able to understand why considering only string length of 2 works. Thank you!