chokudai's blog

By chokudai, history, 5 years ago, In English

We will hold AtCoder Beginner Contest 137.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

  • Vote: I like it
  • +92
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

This comment has been deleted

»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

This will be my first contest at AtCoder. Lets see how it goes.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

A+B quickies as usual. I had difficulties on C getting the combinatorics right, needed 3 submissions.

Then misundestood D. The word (and concept) "one-off jobs" was unknown to me. So I thougt a job needs a[i] days to be done, and implemented knapsack.

Later understood the wording and then was able to do a working solution.

Not enough time then to do E, but I am ok whith this. E is error prone anyway, one has to find the loops in the graph and things... complicated code.

Thanks to problem setters doing all the work!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did the exact same mistake with D but realised that about 5 minutes before contest ended, pretty sure it was greedy but definitely not enough time to implement D.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain problem B and C? Or give a link which can explain them?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can help you

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please explain.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Problem C means:Given n strings and you need to calculate how many pairs (i,j) which string i can become string j after rearranging.n<=10^5

          (Sorry my English is poor)

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thank You and your English is good. :) I understood the question C. But I don't know how to take multiple inputs as strings.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              just the "string[n]" so every string[i] can also be a string

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Oh ! I missed that :( Thanks. i will try my best.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  I didn't solve C because I missed that too:-(

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You know you can see all submission after a contest, iE https://atcoder.jp/contests/abc137/submissions

      Most users use the same account name on both sites.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D??

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

    Loop backward while maintaining all possible job in multiset/priority queue, pick with maximum pay everyday (if its not empty).

    https://atcoder.jp/contests/abc137/submissions/6821855

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    On last day use the job with the max(b[i]) among all jobs with a[i]<=1 On last day -1 use the job with max(b[i]) among all jobs with a[i]<=2 ... Sort the jobs once by a[i], use a multiset of the available values of b[i].

    https://atcoder.jp/contests/abc137/submissions/6825550

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Notice that the i-th job can be done at any day starting from today (0-th day) until ( m-A_i ) So, we just loop starting from (M-1)-th day, see which jobs can we choose, pick the maximum, using a priority queue for example, then go the previous day, add the new jobs that can be done, pick the maximum and so on...

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

    I'll explain my greedy solution: sort all jobs based on rewards. Go through all jobs from the one with the highest reward to the one with the lowest. Do every job on the latest unoccupied day if that day exists. My submission

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

      I implemented the same using DSU,

      My Submission

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Okay,

          I first eliminated all the jobs that required more than '$$$m$$$' days.

          Then, I sorted all the jobs based on their reward, in descending order.

          Then start selecting jobs from the beginning. Let us suppose we choose a job which requires '$$$X$$$' days for completion, Now for any such job try to do it on a day as late as you can. i.e at $$$(m-X)^{th}$$$ day.

          But there's a catch, what if the $$$(m- X)^{th}$$$ day is already assigned to any previous job. That's where DSU comes in.

          If the $$$(m - X)^{th}$$$ job is completed we traverse back from the $$$(m - X)^{th}$$$ day to $$$(m-X-1)^{th}$$$, $$$(m-X-2)^{th}$$$, $$$(m-X-3)^{th}$$$ day and so on.

          Whenever we find a day number less than or equal to $$$(m-X)$$$ and greater than equal to zero, we assign the job to that day and mark it as visited.

          Finding the day that is less than or equal to a given day and is not already visited can be done using DSU. We use connected chains, and for each occupied day the next job is assigned to the day before the head or the parent of the chain.

          I might not be very good at explaining this, but I can share a similar problem.

          Problem

          the editorial of this problem is very well explained, and you will definitely get the gist of this idea.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can F be solved using Lagrange's Interpolation better than O(n^3)? I had solution of O(n^3) but ofcourse it didn't work.

  • »
    »
    5 years ago, # ^ |
    Rev. 9   Vote: I like it +19 Vote: I do not like it

    My solution works in $$$O(P^2)$$$. Let $$$S(i,x) = \frac{\prod_{j=0}^{p-1} (x-j)}{x-i}$$$

    The answer is $$$f(x)=$$$ $$$\sum_{i=0}^{p-1} \frac{\prod_{j=0}^{p-1} (x-j)}{x-i}*(\frac{a[i]}{S(j,j)})=\sum_{i=0}^{p-1}S(i,x)*\frac{a[i]}{S(i,i)}$$$

    You can compute this in $$$O(P^2)$$$

    Notice that when we compute $$$f(t)$$$ if $$$i \ne t$$$, $$$S(i,t)*\frac{a[i]}{S(i,i)}$$$ is always equal to $$$0$$$

    So the only value left is $$$S(t,t)*\frac{a[t]}{S(t,t)} = a[t]$$$ which is what we want.

    I don't know if this technique is well-known, but this was taught at my school about how to construct polynomial when we get set of $$$(x,f(x))$$$.

    submission

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +33 Vote: I do not like it

    I solved F without Lagrange's interpolation in $$$O(p^2 \log{p})$$$, which can be improved to $$$O(p \log^2{p})$$$ as follow.

    We take out the indices $$$u$$$ where $$$a_u = 0$$$ to the set $$$A$$$ of $$$k$$$ integers, and the indices $$$v$$$ where $$$a_v = 1$$$ to the set $$$B$$$ of $$$p - k$$$ integers. Construct $$$F(x) = (x - A_1)(x - A_2)...(x - A_k)$$$, and $$$G(x) = (x - B_1)(x - B_2)...(x - B_{p - k})$$$, then the answer would be $$$F(x)^{p - 1}(G(x) + 1)$$$. Be careful of the index 0 though.

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

      My $$$O(P^2 log(P))$$$ (I was just naively computing power by binary exponential) got TLE, so I had to optimize to $$$O(P^2)$$$. :( What is execution time of your solution?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      May I ask how can you solve this problem in $$$O(p \log^2{p})$$$?

      It seems to me that the calculation of $$$F(x)^{p - 1}$$$ is $$$O(p^2 \log{p})$$$ and can hardly be improved.

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

        Using FFT to multiply two polynomials in $$$O(p\log{p})$$$ is the speed-up :)

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

      Why are you multiplying by (G(x) +1)?? How would the answer differ without it?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ... You are actually correct. I have no idea why I multiplied by $$$G(x) + 1$$$.

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

    https://atcoder.jp/contests/abc137/submissions/6823284

    This is my solution...

    My solution works in $$$O(p^2)$$$

    $$$y=\sum\limits_{i=0}^{p-1}a_i\prod\limits_{j \not= i}\frac{x-j}{i-j}$$$

    $$$=\sum\limits_{i=0}^{p-1}a_i\prod\limits_{j \not= i}{(x-j)}\prod\limits_{j \not= i}\frac{1}{i-j}$$$

    And I used dp to calculate $$$\prod\limits_{j=0}^{p-1}{(x-j)}$$$ .And this dp is reversible and we can erase one element to calculate $$$\prod\limits_{j \not= i}{(x-j)}$$$.

    PS:

    $$$dp[i][j]$$$ means the coefficient of $$$x^j$$$ of $$$\prod\limits_{j=0}^{i}{(x-j)}$$$

    $$$dp[i][0]=dp[i-1][0]*i$$$

    $$$dp[i][j]=dp[i-1][j]*i+dp[i-1][j-1]$$$

    And actually:

    $$$dp[i][0]=\frac{dp[i+1][0]}{i+1}$$$

    $$$dp[i][j]=\frac{dp[i+1][j]-dp[i][j-1]}{i+1}$$$

    so you can use this to erase a element from $$$\prod\limits_{j=0}^{p-1}{(x-j)}$$$

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

    I have found an interesting solution by int_cl.

    I think that it works because

    $$$ \sum_{i=1}^{p-1} x^i \equiv \begin{cases} -1, &x=1\\ 0. &x\ne 1 \end{cases} $$$

    so $$$S(i,x)=\sum_{j=1}^{p-1}-i^{p-j-1}x^j$$$. (using Lucina's S(i,x))

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u suggest optimized solution for C?

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E?

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +7 Vote: I do not like it

    Replace each edge with weight $$$c$$$ with an edge of weight $$$- c + p$$$. Now the problem becomes to find the minimum weight path from $$$1$$$ to $$$n$$$. This can easily be done by Bellman-Ford. The answer would be the maximum of $$$0$$$ and the negative distance from $$$1$$$ to $$$n$$$ in the new graph.

    One thing to note however is that it is not sufficient to check if a negative weight cycle exists but to find a negative weight cycle on the path from $$$1$$$ to $$$n$$$. However, a slight modification in the negative weight cycle detection algorithm allows it. Here's the code.

    Edit: As AlwaysMerlin pointed out there's indeed a problem with my submission. The main idea is correct, it is the handling of negative weight cycles that cause a problem. The code above tries to check if there exists a negative weight cycle from $$$1$$$ to $$$n$$$ by checking if the distance of vertex $$$n$$$ ever changes after $$$n - 1$$$ rounds, if so there exists a negative weight cycle on the path from $$$1$$$ to $$$n$$$. While this indeed is sufficient, this is not necessary. Since the number of rounds required to reduce the distance from $$$1$$$ to $$$n$$$ maybe on the order of the weight of the edges.

    The way to fix it is to assign $$$-\infty$$$ distance to any node whose distance decreases after the first $$$n - 1$$$ rounds and run the algorithm for $$$n - 1$$$ more rounds. This way, if the distance of a node reduces, the distance of all its neighbours is guaranteed to reduce in the next turn, unlike with our previous algorithm. Eventually, all the nodes whose distance can be reduced will become $$$-\infty$$$ by the end of it and we simply need to check if the distance of $$$n$$$ is $$$-\infty$$$. Here's the submission with that correction in mind.

    This is effectively the method described by oversolver.

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

      Your "a slight modification" is very elegant! I instead modified the graph to only include nodes which lie on the paths from 1 to n. Rest is pretty much the same.

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

      This solution is not correct. Try the following case:

      3 4 99999
      1 3 8
      3 2 10
      2 2 100000
      2 1 3
      

      It seems like many of the accepted submissions can be broken this way.

      A better solution is to find the negative cycles reachable from node 1, then check if N can reach any of them along the transposed graph.

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

        a classic solution is run n-1 iteration of FB, remember distances, run one more iteration and if old[i]>new[i] then dist[i] = -inf

        then run n-1 of FB again, properly processing cases with inf

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

        We can basically delete such nodes which are not reachable from 1 and nodes from which we cannot reach n. In that graph just finding negative cycles suffices.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          bro if we delete all edges which are involved in self loops and after that if we keep track of edges(using dfs) which are involved in cycles and after that delete them also(deleting means removing them from the adjacency list). after this we will be remaining with a DAG, in this we can do topological sort, and in one pass we can find the minimum distance to reach node n(with storing weights as "-c+p")..this approach will be kinda nlogn ... what about this? please reply

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

            If you delete edges which are in a cycle, it might be that node n will not be reachable from node 1. Example say n is 5 and edges are 1 2, 2 3, 3 4, 4 2, 4 5, There are going to be many more cases difficult to handle.

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              thanks bro,let's suppose if there exists a path from 1 to n which contain a node i such that i is involved in a cycle then i can infinitely enlarge this path(by moving through cycle and coming to i again), so it means i should never go through to a node which is innvolved in a cycle, so isn't it good to delete all edges which are involved in those cycles ??.. also if there exists no path from 1 to n such that it doesn't have a node involved in cycle then we should answer -1 as we can't reach n with a maximum finite path.. bro i am getting my test cases passes partially.. also in example you mentioned if we delete edges 2->3, 3->4, 4->2 , then also we can't reach reach n which is correct answer in this case isn't it??

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                If you delete the cycle then how will you know if it was a positive cycle or negative cycle? In one case -1 is the answer and in the other, the answer is finite depending on the model you choose.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for showing me what went wrong!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The solution doesn't pass all cases though..there are a few cases added after the contest, I guess. Take a look and please reply with the solution.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      islingr Check this test case I think it should give -1 and your code gives 0.

      4 2 3
      1 2 1
      3 4 1
      
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        The problem states that both $$$n$$$ is reachable from $$$1$$$, so such a situation won't arise.

        With that said, it is possible to figure out if $$$n$$$ is reachable from $$$1$$$ or not. Just note that the distance of $$$n$$$ from $$$1$$$ would be $$$\inf$$$ if it is not reachable, so adding a single check at the end of the code should be enough.

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

Tried to sort by descending order of job payout and then binary search to capture best days for each job but got WA for problem D. Somebody help me please.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am not sure about your approach, but instead you have to notice that the i-th job can be done at any day starting from today (0-th day) until ( M — A_i )

    So, it is like ranges on a number line, each range is [0,R_i]; where R_i = m — A_i i.e. the last day we can pick the i-th job.

    Now you just have to loop from the (M-1)-th day until the 0-th day, and add the jobs in a priority queue, pick the max. at each day.

    https://atcoder.jp/contests/abc137/submissions/6820010

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I've been solving D for 1 hour and 10 minutes but didn't manage to solve it at last:)

»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

After how much delay are ratings usually updated?

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

    Like ten minutes or so. Its quick.

    Edit: Still no update after 25 minutes... ;) Edit2: Now it's done :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi guys! I dont understand why my solution for D doesnt work.

https://atcoder.jp/contests/abc137/submissions/6812607

Can you give sample, which can destroy my solution?

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

    This test case will not work with your solution. The answer should be 6, but your solution would give 5.

    3 5
    4 3
    4 1
    2 2
    
  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    2 4

    3 15

    4 10

    For this case, your code returns 15, but the right answer is 25.

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

In D, I first sorted the tasks in decreasing order of their rewards. If 2 tasks have the same rewards then the one with the higher 'A' attribute comes first. Then I followed a greedy approach. I iterated over the tasks and kept a count of how many days have elapsed so far which is 0 initially. If the current task can be done and its reward can be collected before m days, increment days and the ans. Else do nothing. Submission. Can someone tell me why is this approach wrong or tell a test where it fails

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

    Well, try this: 3 2 2 4 1 5 1 1

    the answer should be 9, i think yours is 6

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, I just realized what's wrong with my logic. Thanks anyway

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

    I did the same. This approach is wrong. Suppose a testcase 2 3 1 10 3 9 Your answer must be: 10 But the correct answer is:19 Explaination: Perform the job as late as possible so the job which have less profit but take more days can be accomodated. So the job with profit 10 can be performed on 2nd day instead of 1 and first job can be accomodated.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution is failing in one of the test sets in C. i sorted each string and then sorted the array , then found the equal ones and , did ((k-1)*k)/2 someone help me find the error given bellow is the submission link https://atcoder.jp/contests/abc137/submissions/6833935

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

I wrote a $$$O(p^2)$$$ solution for arbitrary $$$a_i$$$, based on elimination.

if we compute the $$$i$$$-th order differential of these equations, for all $$$j<i$$$, $$$b_jx^j$$$ term will not exist. So we can first compute the $$$(p-1)$$$-th order differential to only leave the $$$b_{p-1}x^{p-1}$$$ term, then we can get $$$b_{p-1}$$$. Then we subtract all $$$b_{p-1}x^{p-1}$$$ terms and compute the $$$(p-2)$$$-th order differential to get $$$b_{p-2}$$$, and so on.

We can compute the $$$i$$$-th order differential by $$$\sum_{j=0}^{i} (-1)^jC_i^jf_{t_j}(x)$$$ for any contiguous $$$i+1$$$ equations $$$f_{t_0}, f_{t_1}, \dots, f_{t_i}$$$. This differential should only contain the $$$b_ix^i$$$ term and the constant term, if we have already subtracted $$$b_jx^j$$$ for all $$$j>i$$$.

Actually we can prove $$$\sum_{j=0}^{i} (-1)^jC_i^j(i-j)^i=i!$$$. Since $$$(i!, p)=1$$$, we will always have exact 1 solution.

My submission

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

What's wrong about solving E using bellman-ford algorithm? with replacing edges weight with p-c, and detecting negative cycles that can reach the N-th node

Here is my submission: https://atcoder.jp/contests/abc137/submissions/6838302

Thanks in advance :)

Edit: RESOLVED

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can any one explain what the time complicity for D for the Backward solution, this my submission its AC using same approach i write it and wait to TLE but its AC.

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

I use a wrong algorithm to solve E and got accepted, but got TLE on some simple datas :(

3 3 0
1 2 1
2 2 1
1 3 1
»
5 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Thanks for your explanation about F, I learned a lot from your blog.

»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Terrible...

  • »
    »
    5 years ago, # ^ |
      Vote: I like it -25 Vote: I do not like it

    It's no use to solve problems on AtCoder. The quality of problems are so low. So AtCoder please go away.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In the Editorial in Japanese, I can read something in English on the first page : the Editorial in English will be available in several days. Is this true ? Still waiting.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

If anyone is interested here is a solution for task E, that works on after_contest tests. https://atcoder.jp/contests/abc137/submissions/6904276

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

    could you please explain your solution.. i will appreciate it :)

    • »
      »
      »
      5 years ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      I will try.
      If we can get from node 1 to negative cycle ans from this cycle to node n, the answer is -1.
      If we can't get from node 1 to node n the answer is -1.
      Else we should say max-dist from node 1 to node n.
      At first i change cost of my edges from cost to -cost; So, array d — array of shortest distances from node 1, but actually it is array of maximum distances.
      I calculate it with Bellman-Ford Algorithm first n steps of algorithm.
      This algorithm says that if after first n steps we keep algoritm going and some node v will get better d[v] value, then v — is node from negative cycle or reacheble from negative cycle.
      So i find all such nodes and just check if we can get from node v to n.
      To check this i just use Ford-Bellman algorithm with n(start node) and reversed edges(as we should check can we get from v to n)
      If i find such node ane we can get from it to n the answer is -1. Else as statement says if max-dist from 1 to n higher than 0 we should output it.Else we should output 0.

      Sorry if my explanation is not clear. I don't know english well.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Won't that already be considered when we run Bellman-Ford from node 1. If the distance of node n decreases even after n iterations over all edges, isn't that sufficient to say that a negative cycle is present on the path from 1 to n?

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

          Consider this graph
          n = 3
          1 3 1e9
          3 2 1e9
          2 2 -1
          2 1 1e9
          So, to get d[3] lower — we need at least 1e9 iterations of Ford-Bellman.
          But d[2] will get lower, so we can just check if we can get from node 2 to node 3.

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

            Awesome! Thanks.

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

            Excellent bro thank you, learnt a whole new important thing :)