chokudai's blog

By chokudai, history, 2 months 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

»
2 months ago, # |
Rev. 2   Vote: I like it -34 Vote: I do not like it

This comment has been deleted

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The time link of English page is still broken T_T

»
2 months 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.

»
2 months 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!

  • »
    »
    2 months 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.

  • »
    »
    2 months 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?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I can help you

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Please explain.

        • »
          »
          »
          »
          »
          2 months 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)

          • »
            »
            »
            »
            »
            »
            2 months 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.

            • »
              »
              »
              »
              »
              »
              »
              2 months 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

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  2 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am aware of that. But the thing is I didn't understand the questions itself.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to Solve D??

  • »
    »
    2 months 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

  • »
    »
    2 months 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

  • »
    »
    2 months 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...

  • »
    »
    2 months 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

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

      I implemented the same using DSU,

      My Submission

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How do you approach that . i try to upsolve this problem but i'm asking how you can use dsu i learnt it and i can solve some problems using it but not all how can i merge greedy solution with dsu cause dsu seems to be remarkable data structure . sorry for my poor English. thanks in advance

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

        solution this is my solution it is wa i know why but i can't know how to choose to make them max as possible and the variable cnt i feel it makes my mind goes far from the problem my mind is stuck with only cnt shan61916 thank you in advance.

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

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

            is this similar problem i understands the greedy approach but with DSU i can't understand it. and do you understand what i'm saying in this comment i feel very sad that i can't find such a solution and my mind sometimes confuse me. makes my go far from the problem and stuck in upsolving and finally can't solve after all that.

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

            shan61916 after your approach i used this first but gives me wrong and also time but i know why from the time but why wrong. this is my submmition.

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

    Convert this problem to job scheduling problem by subtracting the reward day from M. eliminate all the negative values (M — day < 0).

    input (A, B)=> [(4, 3), (4, 1), (2, 2)]

    day, reward = map(int, input().split())

    if m- day + 1 > 0:
    
        jobs.append((m - day + 1, reward))
    

    jobs = [(1, 3), (1, 1), (3, 2)] #(A days, B reward) sort the jobs by reward point and day in descending order.

    this is now a job sequencing problem. I have solved it using DisJoint Set Union.

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

»
2 months 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.

  • »
    »
    2 months 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

  • »
    »
    2 months 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.

    • »
      »
      »
      2 months 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?

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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 :)

    • »
      »
      »
      2 months 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?

      • »
        »
        »
        »
        2 months 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$$$.

  • »
    »
    2 months 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)}$$$

  • »
    »
    2 months 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))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can u suggest optimized solution for C?

»
2 months ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve E?

  • »
    »
    2 months ago, # ^ |
    Rev. 3   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 a necessary, this is not sufficient. 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 Bugman.

    • »
      »
      »
      2 months 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.

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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

      • »
        »
        »
        »
        2 months 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.

        • »
          »
          »
          »
          »
          2 months 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

          • »
            »
            »
            »
            »
            »
            2 months 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.

            • »
              »
              »
              »
              »
              »
              »
              2 months 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??

              • »
                »
                »
                »
                »
                »
                »
                »
                2 months 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.

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you for showing me what went wrong!

    • »
      »
      »
      2 months 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.

»
2 months 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.

  • »
    »
    2 months 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

»
2 months 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:)

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

After how much delay are ratings usually updated?

  • »
    »
    2 months 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 :)

»
2 months 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?

  • »
    »
    2 months 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
    
  • »
    »
    2 months 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.

»
2 months 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

  • »
    »
    2 months 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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months 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.

»
2 months 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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide the proof of D's solution.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I recommend they increase the difficulty of A, B and C. They are really easy.

»
2 months 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

»
2 months 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

»
2 months 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.

»
2 months 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
»
2 months 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.

»
2 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Terrible...

  • »
    »
    2 months 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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution to D : https://atcoder.jp/contests/abc137/submissions/6829804 Why is it wrong ?

»
2 months 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.

»
2 months 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

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

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

    • »
      »
      »
      2 months 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.

      • »
        »
        »
        »
        2 months 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?

        • »
          »
          »
          »
          »
          2 months 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.

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

            Awesome! Thanks.

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

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why in D restrictions is too big? If i want to store the graph in djacency matrix it would take too much memory (?)