PROBLEM LINK:Author: Evgenij Artemov DIFFICULTY:EASYMEDIUM 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. RELATED PROBLEMS:
This question is marked "community wiki".
asked 14 Nov '15, 19:25

An alternative solution would be to think of these offers as edges in a graph and perform a floodfill backwards from the max. possible type of all the stamps given in the input (which is <= 50000), keeping track of the max. day a stamp was visited in a hashmap. This way you only visit a stamp if you haven't already visited it at a later day (meaning that the current visit isn't useful). answered 16 Nov '15, 15:21

Getting tle with approach mentioned above someone please help... answered 16 Dec '15, 17:05

This can be done using disjoint union find data structure,
answered 16 Nov '15, 18:30

I solved it like adhoc problem.
My logic was: convert as many stamps into EMAX(50000) as possible then convert as many stamps into EMAX1 and so on. answered 17 Nov '15, 17:44

A slightly more difficult version of this problem is when the graph is directed. answered 16 Nov '15, 18:02

Can anyone help me out with this, I could not figure out why I was getting a SIGSEV in this c++ code for the larger test cases https://www.codechef.com/viewsolution/8764735 But it was working fine when I used arrays instead of maps in c++ and got 100pts ( https://www.codechef.com/viewsolution/8764794 ), Did anyone else face a similar issue or has any clue why larger cases might give a sigsev ? answered 17 Nov '15, 20:51
hey i also had the same implementation and idea. here is a link to my solution https://www.codechef.com/viewsolution/8798039
(19 Nov '15, 20:18)

can anyone please suggest,why its giving Runtime Error(NZEC) in codechef,though its working fine in my system,even just scanner.nextInt() is giving same error import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Queue; import java.util.Scanner; import java.util.Set; class Offer{ public int v; public int d; public Offer(int v,int d){ this.v=v; this.d=d; } } public class Main {
} class Node{
} answered 19 Dec '15, 15:39

I'm running into a problem with my Python solution. I'm getting an NZEC every time. At first, I thought it was a problem with the input size, but reading in all input at once and printing it out works fine. Then I thought it might be a problem with Python 3's input handling, so I switched to 2.7. No dice. The program works fine on the sample input, but fails on every subproblem. Is there some subtle difference in the input formats which I'm missing? answered 30 Jan '16, 02:07

answered 13 Jun '16, 17:04
