×

# CHSTAMP - Editorial

Author: Evgenij Artemov
Tester: Istvan Nagy
Editorialist: Xellos

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.

# RELATED PROBLEMS:

This question is marked "community wiki".

7★xellos0
5.9k54292
accept rate: 10%

19.7k350498541

 3 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 4★Amlesh 239●3 accept rate: 0%
 1 This can be done using disjoint union find data structure, Go from Nth day to first day, each day union the two values which can be exchanged and replace every value in the connected component set by its maximum in the set, at the end of the day remove all the unions by setting the parent[i]=i for all the values and keep going till day 1, then you have maximum values for all stamps. answered 16 Nov '15, 18:30 439●14 accept rate: 16%
 1 I solved it like ad-hoc problem. My logic was: convert as many stamps into EMAX(50000) as possible then convert as many stamps into EMAX-1 and so on. I implemented it using a recursive function. link to my solution : https://www.codechef.com/viewsolution/8787938 answered 17 Nov '15, 17:44 716●2●10 accept rate: 31%
 0 A slightly more difficult version of this problem is when the graph is directed. answered 16 Nov '15, 18:02 116●3 accept rate: 12%
 0 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 208●6 accept rate: 20% 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) likecs6★
 0 Why can't we apply the same logic in forward chronological order? Could you provide me a testcase where it will fail? answered 19 Nov '15, 19:26 1●1 accept rate: 0% How would you apply the same logic in forward chronological order? What would you update, the max. stamp you can get at the first day? :D (19 Nov '15, 19:37) xellos07★
 0 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 { Map> graph; public Main(){ graph=new HashMap>(); } public static void main(String[] args){ Main ticketExchange=new Main(); Scanner scanner=new Scanner(System.in); int noOfTc=scanner.nextInt(); for(int i=0;i currNodes=graph.get(a); if(currNodes==null){ currNodes=new ArrayList(); graph.put(a, currNodes); } currNodes.add(new Offer(b,d)); } private void initGraph(Scanner scanner, int noOfLines){ for(int i=0;i queue=new LinkedList(); queue.add(new Offer(source,1)); int maxVal=source; Set visited=new HashSet(); while(!queue.isEmpty()){ Offer current=queue.poll(); if(!visited.contains(current.v)){ visited.add(current.v); for(Offer adjNode : graph.get(current.v)){ int currVal=adjNode.v; if(adjNode.d>current.d){ if(maxVal
 0 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 1 accept rate: 0%
 0 @xellos0, @admin can you explain me "first two paragraphs of EXPLANATION" with an example ? answered 13 Jun '16, 17:04 56●3 accept rate: 30%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,494
×1,648
×1,197
×120
×27

question asked: 14 Nov '15, 19:25

question was seen: 5,729 times

last updated: 13 Jun '16, 17:23