### PROBLEM LINK:

**Author:** Evgenij Artemov

**Tester:** Istvan Nagy

**Editorialist:** Xellos

### DIFFICULTY:

EASY-MEDIUM

### PREREQUISITES:

Graphs - connected components.

### PROBLEM:

You have N stamps of different types and M offers of the form (d,a,b) - on day d, you may exchange any number of stamps of type a or b for the same number of stamps of the other type, any number of times. Maximise the sum of types of your stamps.

### QUICK EXPLANATION:

Solve for each stamp independently. Process days in reverse order and remember the max. type into which you can eventually turn a stamp of each type; for each day, find connected components and update the max. types in them.

### EXPLANATION:

The first thing to realise is that we can split an exchange of multiple stamps of the same type into exchanges of one stamp for another. Therefore, we only need to find the maximum type into which a stamp of type t (for each t) can be exchanged - \texttt{maxtype}[t].

First of all, let’s solve this problem for only one day. The exchange offers can be viewed as edges of an undirected graph, whose vertices are stamp types. Since the offers can be used in any order and any number of times, we can turn any type into any other type in its connected component. Therefore, \texttt{maxtype}[t] *before* that day will be the maximum of \texttt{maxtype}[u] for all u in the conn. component of t *after* that day.

We may notice here in which order we can determine the values in \texttt{maxtype}[] - a latter day had to go first. Therefore, we should process the days in reverse chronological order (from the last day to the first one) and update \texttt{maxtype}[] for each of them.

This update is fairly simple - we just need to find the connected components (this can be done with BFS or DFS); for each component, we should find m=\text{max}(\texttt{maxtype}[t]) over all types t in it and set \texttt{maxtype}[t]=m for all those types.

There’s one thing to watch out for in the implementation: we can’t compute the connected components for all types and all days, but if we ignore all types which aren’t involved in any exchange offer, there are only about as many vertices to compute the conn. components for as there are edges (offers) for that day. The downside is that we can’t use regular arrays; in C++, they can be substituted with STL *map<>*s, which cost O(\log{T}) time per access / update (see my code for more details). Processing a day with e offers then takes O(e\log{T}) time.

The overall algorithm is as follows: throw all exchange offers in buckets for their respective days, process the days from last to first while updating the values in \texttt{maxtype}[] (initially, \texttt{maxtype}[t]=t); look at each of the N stamps, change them to the respective max. types and sum them up to get the answer.

Time complexity: O(N+T+M\log{T}), memory O(N+T+M).

### AUTHOR’S AND TESTER’S SOLUTIONS:

The author’s solution can be found here.

The tester’s solution can be found here.

The editorialist’s solution can be found here.