You are not logged in. Please login at www.codechef.com to post your questions!

×

CHSTAMP - Editorial

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:

This question is marked "community wiki".

asked 14 Nov '15, 19:25

xellos0's gravatar image

7★xellos0
5.9k54292
accept rate: 10%

edited 08 Jan '16, 17:27

admin's gravatar image

0★admin ♦♦
19.7k350498541


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

link

answered 16 Nov '15, 15:21

Amlesh's gravatar image

4★Amlesh
2393
accept rate: 0%

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

link

answered 16 Dec '15, 17:05

saar2119's gravatar image

5★saar2119
1213
accept rate: 0%

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

link

answered 16 Nov '15, 18:30

geek_geek's gravatar image

4★geek_geek
43914
accept rate: 16%

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

link

answered 17 Nov '15, 17:44

nilesh3105's gravatar image

5★nilesh3105
716210
accept rate: 31%

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

link

answered 16 Nov '15, 18:02

khalid545's gravatar image

4★khalid545
1163
accept rate: 12%

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 ?

link

answered 17 Nov '15, 20:51

s4shyam95's gravatar image

5★s4shyam95
2086
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★

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

link

answered 19 Nov '15, 19:26

ananth360's gravatar image

3★ananth360
11
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★

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;

}

link

answered 19 Dec '15, 15:39

nishat_2015's gravatar image

0★nishat_2015
1
accept rate: 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?

link

answered 30 Jan '16, 02:07

jaccarmac's gravatar image

0★jaccarmac
1
accept rate: 0%

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

link

answered 13 Jun '16, 17:04

dhavalmehta's gravatar image

2★dhavalmehta
563
accept rate: 30%

edited 13 Jun '16, 17:23

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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