Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people.
(Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.)
A — +-X
Just use your language's max function. As $$$A$$$ and $$$B$$$ are small, we don't need to worry about integer overflow.
Runtime: $$$O(1).$$$ Click here for my submission.
B — One Clue
Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set.
To find the minimum possible position of a black stone, we place $$$K$$$ black stones such that $$$X$$$ is at the maximum position. Then, the minimum position will thus be $$$X-K+1$$$, as we have $$$K-1$$$ black stones to the left of $$$X$$$. Likewise, if we place $$$K-1$$$ black stones to the right of $$$X$$$, our maximum position is thus $$$X+K-1$$$.
We should thus print all integers from $$$X-K+1$$$ to $$$X+K-1$$$.
Runtime: $$$O(K)$$$. Click here for my submission.
C — Green Bin
We take advantage of the small length of the strings. Represent the strings as character arrays. Then, note that two strings can be rearranged to become equal if and only if, after sorting their character arrays, the arrays are equal.
We read in the strings and sort their character arrays. We then build an array out of the character arrays and sort that array. From there, we know that all equal character arrays will form a consecutive subsegment of the new array.
Each set of $$$K$$$ equal strings adds $$$\binom{K}{2}$$$ to our answer. So, we now simply need to find the lengths of each of the subsegments containing identical arrays.
Counting sets of equal elements in an array is a relatively standard problem. We can use two pointers--maintain the starting position of our current segment and, when we find a position $$$i$$$ that has a different array from the starting position, we have a set of $$$i - start$$$ to add to the answer.
Runtime: $$$O(N |S| \log N)$$$, to account for the sorting (since comparing two of the character arrays takes $$$O(|S|)$$$ time). Click here for my submission.
D — Summer Vacation
Note that on day $$$i$$$, it's pointless to do any jobs that take more than $$$M-i$$$ days to pay out. We use this lemma to build a greedy strategy.
Let's pick our jobs for the days in reverse order. Sort the jobs in increasing order of payout time. We keep a priority queue containing the values of the jobs we can do. Then, iterate over the days $$$i$$$ from $$$M-1$$$ to $$$0$$$. Add the jobs that take $$$M-i$$$ days to the priority queue (by maintaining our position in the array, we can do this in $$$O(N)$$$ across all values of $$$i$$$), then pick the most valuable job in the priority queue (if the queue isn't empty, of course) and do it on day $$$i$$$. We're essentially picking the most valuable job we can do on day $$$i$$$ that we haven't already reserved for a future day.
The idea here is that on each of these days, there's no reason to wait to do the most valuable job we can--we're no better off doing a more valuable job on an earlier day rather than doing it on our current day, and in fact we may be worse off because some other jobs we want to do might become possible in that time.
Runtime: $$$O((N+M) \log N)$$$. The logarithm factor is due to our priority queue operations. Click here for my submission.
E — Coins Respawn
Note that when we travel along edge $$$i$$$, we gain $$$C_i$$$ coins, but eventually, $$$P$$$ coins will be subtracted from our final score. Therefore, we effectively have increased our score by $$$C_i - P$$$.
Afterwards, we have a weighted directed graph (possibly with both positive and negative weights), and we want to find the longest path on from vertex $$$1$$$ to vertex $$$N$$$ on this graph. If we multiply all of the edge weights by $$$-1$$$, this becomes a shortest path problem, and it can be solved in $$$O(NM)$$$ with the Bellman-Ford Algorithm.
The trick here is to handle the case in which the answer does not exist properly. Bellman-Ford is equipped to detect negative cycles (by determining whether processing the edges one more time would still make our path better, even if the algorithm already terminated), but the catch is that we can only use a negative cycle if it is on some path from $$$1$$$ to $$$N$$$. We therefore run a BFS (a DFS would work too) on the graph with all its edges reversed, starting with vertex $$$N$$$, to determine which vertices can reach $$$N$$$. Then, before confirming that an edge creates a negative cycle, we must check that it has been found both in our Bellman-Ford process (which means it can be reached from $$$1$$$) and in our BFS (which means it can reach $$$N$$$).
If this doesn't give us a usable negative cycle, we can simply print the given answer--that is, $$$-1$$$ times the shortest path--or zero, if it's greater.
Runtime: $$$O(NM).$$$ Click here for my submission.
F — Polynomial Construction
There are several solutions to this problem. The one presented here actually does not depend on the fact that all values of the polynomial are $$$0$$$ or $$$1$$$. However, I think it's still one of the simpler solutions, and it relies on a relatively accessible idea.
The basic idea is to employ finite differences. If you aren't familiar with this concept, I recommend this article to learn about the topic. While the article works with real-valued polynomials, the key theorems turn out to be true when applied over the integers modulo $$$P$$$.
We start by computing all finite differences of this polynomial in $$$O(P^2)$$$. Sequence zero is simply the input data; sequence one is the differences of consecutive values in the input array, and so on, until we have sequence P-1, which only has one element. Let $$$D_i$$$ be the first element in sequence $$$i$$$.
Our key lemma is that $$$f$$$ is equal to:
Of course, all arithmetic is modulo $$$P$$$. Division is represented by multiplication by a modular inverse.
This is a similar concept to the second theorem presented in the Proof of Theorem section in the linked article. The proof is fairly lengthy and is thus omitted here, but I encourage you to take a look at it if you're interested. It's a complex formula, but it's relatively easy to evaluate, and it should be fairly tractable with a solid understanding of finite differences.
The naive implementation of this algorithm could be $$$O(P^3)$$$ due to the need to evaluate $$$P$$$ different inner products. However, we take advantage of the fact that the products are relatively similar. We evaluate the sum starting at $$$n=P-1$$$ and moving downwards. At each step, we multiply the existing polynomial by $$$x-n$$$ (doable in $$$O(P)$$$ since this polynomial only has two terms) and then add $$$\frac{D_n}{n!}$$$ to the result. The result after dealing with $$$n=0$$$ is our answer.
Runtime: $$$O(P^2)$$$. Click here for my submission.
As usual, feel free to comment below if you have any questions.
what is the mistake in my code for problem D ..... i just sort the jobs and greedily taking the most valuable one if(day needed+ curent day <= M ) https://atcoder.jp/contests/abc137/submissions/6838897
You're essentially checking whether the $$$i$$$'th job in your sorted list can be done on day $$$M-i$$$. This causes some issues when $$$N \neq M$$$, and additionally, it may not be optimal (if we can't do a job now, we still might want to do it earlier if it's particularly valuable--also, if a valuable job can be done late in our schedule, we'd rather do it then so that we have more options for the early jobs).
Hi, in your submission to C, why do you choose to store strings as std::vector instead of simply std::string? Is there an advantage to vector representation?
Not particularly. In many languages, you would need to use an array because the sorting function could not be used on a string. I couldn't remember with certainty whether C++'s sort method works on strings, so to be safe and to save time within the contest I just used character vectors, which I knew would work.
sort(str.begin() , str.end());Yes, I checked afterwards and confirmed that a string works (hence why I wrote that there's no particular reason not to use a string).
Wrong link to problem E's solution.
Fixed, thanks for letting me know!
thanks for the amazing editorials I find it more helpful than atcoder editorials
Where can I find atcoder editorials for this round ?
Here's the link: https://img.atcoder.jp/abc137/editorial.pdf. Right now, it's only in Japanese--lately AtCoder has been adding English editorials several days after the fact.
Can u give brief idea about what other approaches can be used to solve problem F as u wrote there are many possible solutions.Thanks!!