We will hold AtCoder Beginner Contest 137.

- Contest URL: https://atcoder.jp/contests/abc137
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190810T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- writer：potetisensei IH19980412 drafear yokozuna57 DEGwer gazelle
- Rated range: ~ 1999

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

We are looking forward to your participation!

This comment has been deletedThe time link of English page is still broken T_T

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

How did it go?

1 and 2 were freebies. Solved 3rd using sorting. 4th hit me hard.

Next time you hit first :)

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!

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.

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

I can help you

Please explain.

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)

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

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

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

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

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.

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

How to Solve D??

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

I tried with forward failed then tried with backward passed, Why the forward approach fails ?

Failed -> https://atcoder.jp/contests/abc137/submissions/6831836 Passed -> https://atcoder.jp/contests/abc137/submissions/6826566

Edit: I figured it out :)

Thank you for the explanation, but what about the time complexity, N can go up to 1e5 and the same goes for M, with this solution we can easily reach 1e10 operations. Am I wrong ?

Time complexity is O(M + NlogN) because operation for insert, erase, and get value from multiset will happen at most N times, with LogN complexity for each of 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

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

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

I implemented the same using DSU,

My Submission

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

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.

shan61916

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

heador theparentof 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.

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.

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.

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

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

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

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.

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

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.

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?

1 sec :D

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.

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

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

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

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

Orz Your idea is quite awesome!

I have found an interesting solution by int_cl.

I think that it works because

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

Oh so amazing.

Can u suggest optimized solution for C?

Sort all strings and hash them. Iterate over the hash map suppose count =p add p*(p-1)/2 to the answer.

thank you very much sir.....helped alot

Do you mind posting your code? I still didn't understand

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

Great use of Stl thanks :)

get a string. sort the string. make the string into map<string,int> You can see my code: https://atcoder.jp/contests/abc137/submissions/6811374

It is possible to use array instead of map since the number of possible sorted strings is $$$C^{35}_{10} = 183579396$$$ while $$$1024 \text{ MB}$$$ can hold $$$~256000000$$$

`int`

s.submission

How to solve E?

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

anegative 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 anecessary, this is notsufficient. 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

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

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.

This solution is not correct. Try the following case:

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.

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

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.

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

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.

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??

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.

yes got it

Thank you for showing me what went wrong！

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.

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.

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

Nice, thanks

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

After how much delay are ratings usually updated?

Like ten minutes or so. Its quick.

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

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?

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

2 4

3 15

4 10

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

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

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

the answer should be 9, i think yours is 6

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

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.

Can you help me with the code for this question

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

line 28: count+=((k-1)*1LL*(k))/2;

thank you!

Can anyone provide the proof of D's solution.

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

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

https://atcoder.jp/contests/abc137/submissions/6821014 https://atcoder.jp/contests/abc137/submissions/6820913 https://atcoder.jp/contests/abc137/submissions/6821035

all three submissions are totally same! Should Atcoder Check this?

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

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.

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

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

Terrible...

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

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

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.

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

could you please explain your solution.. i will appreciate 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.

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?

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.

Awesome! Thanks.

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

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

oh, this blog for 137, i'm talking about 138D sorry.