CHSTAMP - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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.

RELATED PROBLEMS:

1 Like
2

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).

3 Likes
3

A slightly more difficult version of this problem is when the graph is directed.

4

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.

Code : https://www.codechef.com/viewsolution/8776302

1 Like
5

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

1 Like
6

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 ?

7

Why can’t we apply the same logic in forward chronological order? Could you provide me a testcase where it will fail?

8

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? :smiley:

9

hey i also had the same implementation and idea. here is a link to my solution https://www.codechef.com/viewsolution/8798039

10

Getting tle with approach mentioned above someone please help…
Solution link : https://www.codechef.com/viewsolution/8965570

1 Like
11

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<Integer,List<Offer>> graph;

public Main(){
    graph=new HashMap<Integer, List<Offer>>();	
}
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<noOfTc;i++){
     
     int n=scanner.nextInt();
     int m=scanner.nextInt();
     
     int[] inputNodes=new int[n];
     for(int k=0;k<n;k++){
    	 int temp=scanner.nextInt();
    	 inputNodes[k]=temp;
     }
     scanner.nextLine();
     ticketExchange.initGraph(scanner,m);
     scanner.close();
     int sum=0;
     for(int j=0;j<n;j++){
    	 sum=sum+ticketExchange.doBfs(inputNodes[j]);
     }
        System.out.println(sum);
    }
}
private void addEdge(int a,int b,int d){
	List<Offer> currNodes=graph.get(a);
	if(currNodes==null){
		currNodes=new ArrayList<Offer>();
		graph.put(a, currNodes);
	}
	currNodes.add(new Offer(b,d));
}
private void initGraph(Scanner scanner, int noOfLines){
	
	for(int i=0;i<noOfLines;i++){
		String[] edge=scanner.nextLine().split(" ");
		int l=Integer.parseInt(edge[1]);
		int r=Integer.parseInt(edge[2]);
		int d=Integer.parseInt(edge[0]);
		
		addEdge(l,r,d);
		addEdge(r,l,d);
		
	}
}

public int doBfs(int source){
	Queue<Offer> queue=new LinkedList<Offer>();
	queue.add(new Offer(source,1));
	
	int maxVal=source;
	Set<Integer> visited=new HashSet<Integer>();
	
	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<currVal){
				   maxVal=currVal;
			    }
			     queue.add(new Offer(adjNode.v,adjNode.d));
			   }
		  }
		}
	}
	return maxVal;
}

}
class Node{

public Node(int v,int value){
	this.v=v;
	this.value=value;
}
public int v;
public int value;

}

12

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?

13

@xellos0, @admin can you explain me “first two paragraphs of EXPLANATION” with an example ?