Probably means extra, you dumbass.

A friend (jokingly) told me it probably stood for, "Extra Garbage Data Structure"

Extra
Example
Exercise
External
Extended
Excellent
Exhausting
Extraordinary

Solve offline. Apply normal MST algo for graph with all m normal edges and q query edges combined. The difference is to not actually add the edge if its a query edge. Solution

Store the edges given, in set with ind=-1
Store the edges of queries, in set with index of query.
Now apply Kruskal or Prim's and whenever you encounter a query edge check if this edge would have been added or not and store the answer for that index by using vector of strings.
Finally print that vector.
Submission

Think of kruskal algorithm used to compute the MST of a graph:

You sort edges by increasing order of weights and you use an edge if and only if it unites two nodes that are not already connected. So you can put all the edges in the same vector, sort them and keep uniting like if you were computing the MST of the graph.

At any time when the current edge is a "query edge" you just check if it unites two nodes that are not already connected or not.

See my code for more details: https://atcoder.jp/contests/abc235/submissions/28547346

My solution:

Build the MST of the original graph, then the answer for a query $$$(u, v, w)$$$ is Yes if and only if the maximum weight of an edge in the path from $$$u$$$ to $$$v$$$ on this MST is greater than $$$w$$$. So, now our problem has changed to: Given a tree and multiple queries $$$(u_i, v_i)$$$, report for each of them the maximum weight of an edge in the path from $$$u _i$$$ to $$$v_i$$$, which is easily solvable by Binary Lifting.

I did some pretty similar DP.

The states are: number of the digit, bitmask (to know which of the required digits have already been used) and a bool to know if my number if currently less or equal than n.

Don't allow any leading zeroes (so in your base case don't use digit 0) and at any digit just add a new transition which is "creating" a newer digit already smaller than n:

See my code for more details: https://atcoder.jp/contests/abc235/submissions/28560145

Don't mind to tell me if anything is unclear :p

My solution (although I couldn't submit it due to some bugs in my code) is the following:

Let's say $$$sum(A)$$$ is the sum of all the elements in the set $$$A$$$. Let's also define $$$S_d$$$ as the set of numbers that don't have the digit $$$d$$$ on their decimal representation. Then, we're asked for $$$sum\left([1, n]- \displaystyle\bigcup_d{S_d}\right) = \frac{n(n+1)}{2} - sum\left(\displaystyle\bigcup_d{S_d}\right)$$$. The sum of that $$$union$$$ can be computed by inclusion-exclusion principle: We iterate through all the non-empty subsets of the given digits and for each of them, we can use digit-dp for computing the required sum.

+1

D can be solved with something not that far from DP. Imagine a graph where each node is a number and you add an edge X->Y if you can reach number Y from number X. You start from number 1 and want the shortest path to get to node N. You have O(n) nodes and O(n) edges.

Let me know if anything is not clear :)

Here is my code: https://atcoder.jp/contests/abc235/submissions/28543245

Yes, my very messy solution just uses recursive DP. With a little tweak to avoid infinite circular rotation (if we reach the same state, then bail out and return "infinity"): https://atcoder.jp/contests/abc235/submissions/28563863

I initially tried to do rotations via integer arithmetic operations, but wasted a lot of time debugging it. Only at the last moment replaced this stuff with string manipulations and got an AC verdict. Premature optimization is the root of all evil...

Edit: Now hacked by the "99_after_contest_00.txt" testcase :-)

We could implement logic like "find max weight edge on path from u to v", and if that weight is bigger current query edge weight, then the query edge weight would have been used.

But to find max weight edge on path from u to v in the MST, we need more that only compare the weight to the parent edge. It can be done in example with binary lifting.

Maybe it is actually a memory error, caused by using several gig for all the dsu.

ABC is educational it is normal to have classic problems.

3 621

Your solution gives 9. My solution gives 6.

Looks like our solutions were hacked after the contest and mine fails it too (are problem setters reading comments here?). Now it would be indeed interesting to have a look at this 99_after_contest_00.txt testcase. I tried stress testing, but haven't found anything yet.

Now I have some testcases: "2 11327" (expected 40, but got 41) and "2 62153" (expected 17, but got 18).

The bug is that the solution is effectively doing DFS to find a path from N to 1. But it isn't always the shortest path, so BFS is really needed instead. The original tests used during the contest were weak and didn't detect it. I wonder how many incorrect solutions got accepted?

And even now, having just a single testcase (testcase 99_after_contest_00.txt) in the set makes it possible for some heuristically tuned or even randomized DFS to be incorrectly accepted.