How did it go?

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?

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

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

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.

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

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

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

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.

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

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.

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

Like ten minutes or so. Its quick.

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

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 4

3 15

4 10

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

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

the answer should be 9, i think yours is 6

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.

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

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

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