### chokudai's blog

By chokudai, history, 5 years ago,

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

| Write comment?
 » 5 years ago, # | ← Rev. 2 →   -34 This comment has been deleted
 » 5 years ago, # |   -19 This will be my first contest at AtCoder. Lets see how it goes.
•  » » 5 years ago, # ^ |   0 How did it go?
•  » » » 5 years ago, # ^ |   0 1 and 2 were freebies. Solved 3rd using sorting. 4th hit me hard.
 » 5 years ago, # |   +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 years ago, # ^ |   0 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, # ^ |   0 Can you explain problem B and C? Or give a link which can explain them?
•  » » » 5 years ago, # ^ |   0 I can help you
•  » » » » 5 years ago, # ^ |   0 Please explain.
•  » » » » » 5 years ago, # ^ |   0 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, # ^ |   0 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, # ^ |   0 just the "string[n]" so every string[i] can also be a string
•  » » » » » » » » 5 years ago, # ^ |   0 Oh ! I missed that :( Thanks. i will try my best.
•  » » » » » » » » » 5 years ago, # ^ |   0 I didn't solve C because I missed that too:-(
•  » » » 5 years ago, # ^ |   0 You know you can see all submission after a contest, iE https://atcoder.jp/contests/abc137/submissionsMost users use the same account name on both sites.
 » 5 years ago, # |   0 How to Solve D??
•  » » 5 years ago, # ^ |   +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 years ago, # ^ | ← Rev. 3 →   +1 I tried with forward failed then tried with backward passed, Why the forward approach fails ?Edit: I figured it out :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 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 ?
•  » » » » 5 years ago, # ^ |   0 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.
•  » » 5 years ago, # ^ |   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 years ago, # ^ |   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 years ago, # ^ |   +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 years ago, # ^ |   +3 I implemented the same using DSU, My Submission
•  » » » » 5 years ago, # ^ |   0
•  » » » » » 5 years ago, # ^ |   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.Problemthe editorial of this problem is very well explained, and you will definitely get the gist of this idea.
 » 5 years ago, # |   +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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   0 1 sec :D
•  » » » 5 years ago, # ^ |   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 years ago, # ^ | ← Rev. 2 →   +3 Using FFT to multiply two polynomials in $O(p\log{p})$ is the speed-up :)
•  » » » 5 years ago, # ^ |   +16 Why are you multiplying by (G(x) +1)?? How would the answer differ without it?
•  » » » » 5 years ago, # ^ |   0 ... You are actually correct. I have no idea why I multiplied by $G(x) + 1$.
•  » » 5 years ago, # ^ |   +16 https://atcoder.jp/contests/abc137/submissions/6823284This 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, # ^ |   +6 Orz Your idea is quite awesome!
•  » » 5 years ago, # ^ |   +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 years ago, # ^ |   +3 Oh so amazing.
 » 5 years ago, # |   0 Can u suggest optimized solution for C?
•  » » 5 years ago, # ^ |   0 Sort all strings and hash them. Iterate over the hash map suppose count =p add p*(p-1)/2 to the answer.
•  » » » 5 years ago, # ^ |   0 thank you very much sir.....helped alot
•  » » » 5 years ago, # ^ |   0 Do you mind posting your code? I still didn't understand
•  » » » » 5 years ago, # ^ |   0
•  » » » » » 5 years ago, # ^ |   0 Great use of Stl thanks :)
•  » » 5 years ago, # ^ |   0 Sort all strings, then use a map to find equal ones. For any group of strings with count>1 calculate the number of pairs. The number is calculated as (i-1)+(i-2)+...+1. Sum up the number of pairs. 
•  » » 5 years ago, # ^ |   0 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$ ints.submission
 » 5 years ago, # |   +4 How to solve E?
•  » » 5 years ago, # ^ | ← 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 years ago, # ^ | ← 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 years ago, # ^ |   +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 years ago, # ^ | ← 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] = -infthen run n-1 of FB again, properly processing cases with inf
•  » » » » 5 years ago, # ^ |   +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 years ago, # ^ |   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 years ago, # ^ | ← 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 years ago, # ^ |   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 years ago, # ^ |   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 years ago, # ^ |   0 yes got it
•  » » » » 5 years ago, # ^ |   0 Thank you for showing me what went wrong！
•  » » » 5 years ago, # ^ |   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.
•  » » » 4 years ago, # ^ |   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 
•  » » » » 4 years ago, # ^ |   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.
•  » » » » » 4 years ago, # ^ |   0 Thnx, got it.
 » 5 years ago, # | ← 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 years ago, # ^ |   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 years ago, # ^ |   +3 Nice, thanks
 » 5 years ago, # |   +8 I've been solving D for 1 hour and 10 minutes but didn't manage to solve it at last:)
 » 5 years ago, # |   +11 After how much delay are ratings usually updated?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +6 Like ten minutes or so. Its quick.Edit: Still no update after 25 minutes... ;) Edit2: Now it's done :)
 » 5 years ago, # |   0 Hi guys! I dont understand why my solution for D doesnt work. https://atcoder.jp/contests/abc137/submissions/6812607Can you give sample, which can destroy my solution?
•  » » 5 years ago, # ^ | ← 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 years ago, # ^ | ← Rev. 2 →   +2 2 43 154 10For this case, your code returns 15, but the right answer is 25.
 » 5 years ago, # |   +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 years ago, # ^ |   +1 Well, try this: 3 2 2 4 1 5 1 1the answer should be 9, i think yours is 6
•  » » » 5 years ago, # ^ |   0 Yeah, I just realized what's wrong with my logic. Thanks anyway
•  » » 5 years ago, # ^ |   +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 years ago, # ^ |   0 Can you help me with the code for this question
 » 5 years ago, # |   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 years ago, # ^ | ← Rev. 2 →   +6 line 28: count+=((k-1)*1LL*(k))/2;
 » 5 years ago, # | ← 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 $ji$.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, # |   +10 all three submissions are totally same! Should Atcoder Check this?
 » 5 years ago, # | ← 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 nodeHere is my submission: https://atcoder.jp/contests/abc137/submissions/6838302Thanks in advance :)Edit: RESOLVED
 » 5 years ago, # |   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 years ago, # | ← 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 years ago, # | ← Rev. 3 →   0 Thanks for your explanation about F, I learned a lot from your blog.
 » 5 years ago, # |   -16 Terrible...
•  » » 5 years ago, # ^ |   -25 It's no use to solve problems on AtCoder. The quality of problems are so low. So AtCoder please go away.
 » 5 years ago, # |   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 years ago, # |   +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 years ago, # ^ |   +5 could you please explain your solution.. i will appreciate it :)
•  » » » 5 years ago, # ^ | ← 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 years ago, # ^ |   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 years ago, # ^ |   +14 Consider this graphn = 31 3 1e93 2 1e92 2 -12 1 1e9So, 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, # ^ |   +5 Awesome! Thanks.
•  » » » » » » 5 years ago, # ^ |   +5 Excellent bro thank you, learnt a whole new important thing :)