Блог пользователя chokudai

Автор chokudai, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +92
  • Проголосовать: не нравится

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится -34 Проголосовать: не нравится

This comment has been deleted

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to Solve D??

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      I implemented the same using DSU,

      My Submission

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 9   Проголосовать: нравится +19 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can u suggest optimized solution for C?

»
5 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

How to solve E?

  • »
    »
    5 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

    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 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится +33 Проголосовать: не нравится

      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 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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 лет назад, # ^ |
            Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

            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 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Thank you for showing me what went wrong!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

After how much delay are ratings usually updated?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    2 4

    3 15

    4 10

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    the answer should be 9, i think yours is 6

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 3   Проголосовать: нравится +6 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

Terrible...

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -25 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится +14 Проголосовать: не нравится

          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.