Activity 2, A KATTIS Problem

Short Description:

Please work through the following activity.

Goals

When you finish this homework, you should have:

Formal Description

This is an individual/group activity. You may do it yourself or as part of a group. If you work as part of a group, please include all names in the final report. Each person should submit a copy of the final report.

In this activity you will construct a document that explains how you solved a complex Kattis problem.

Programming contest problems range from easy to hard. The easy problems are usually straight forward and can be solved with a simple algorithm or a brute force approach. Other problems require knowledge of an algorithm. Problems are made more difficult by forcing you to modify an algorithm that you know.

In this activity, we will explore the third case above.

Please start a word document and record the following, one per group

  1. Record the names of all members of the group.
    • Record if you employed any outside sources to solve this problem, including all AI use.
    • It is probably best if you program on prog1 and only submit your solution after you have a working solution.
  2. Create or log into your Kattis account.
    • The page is at open.kattis.com
    • If you have an account, there is nothing else to do in this step.
    • If you don't have an account
      • Create one
      • Solve the first problem.
  3. Find the problem Horror List.
    • You should find the problem Horror List
    • If the link is broken, search for the problem "horror" in the search bar under the Kattis logo (a cat in a judge robe with a judges gavel).
  4. Read the problem. Read it twice.
    • Ok read it again
    • Note any questions you might have in your document.
    • The following do not need to be correct at this point, this is a moment for reflection.
      • Note what algorithm(s) you think you would employ in your document.
      • Note what data structures you think you would employ to solve your problem in your document.
  5. Visualize the graphs in the given test cases.
    • These are at the end of the description.
    • On paper or something more fancy like graphviz online.
    • Contest problems are notoriously tricky with test cases. They are sometime minimalistic and misleading. Here is another to consider:
    • 9 2 9
      0 8
      0 1
      1 2
      2 3
      2 4
      3 5
      4 6
      5 7
      6 8
      7 8
    • Draw the graph for this case.
    • Take a picture/screen shot of these graphs and include them in your document.
  6. If you wish, proceed to solve the problem without my help.
    • If you choose this option and are successful please do so. But please, in your document
      • Give your modified algorithm.
      • Give the performance of this algorithm.
      • Argue that this algorithm is correct.
      • Provide a screen shot of the "success" of your program in Kattis
      • Submit a tar file file with your program and your document.
    • Otherwise, continue, you have different submission criteria.
  7. My plan for a solution
    • I plan to use a map to hold the graph.
    • I plan to use a vector to hold the horrorList
    • I plan to run a modified BFS to compute the HI for each move
      • Set all costs to the number of movies+1
      • Eliminate color of each node.
      • Set the costs of each of the movies on the horror list to be 0
      • Enqueue all of the movies on the horror list
      • Run the BFS algorithm, but only enqueue a vertex if the cost is less than the parent node's cost + 1
        MULTI-SOURCE-BFS(G, S)
            Is the graph
            S is a list of sources
        
        1. for each vertex v ∈ G.V
        2. v.cost = ∞
        3. Create an empty queue Q
        4. for each vertex v ∈ S
        5. v.cost = 0
        6. Q.enqueue(v);
        7. While not Q.IsEmpty
        8. u = Q.Dequeue
        9. for each v ∈ G.Adj(u)
        10. if v.cost > u.cost+1
        11. v.cost = u.cost + 1
        12. Q.enqueue(v)
    • In your document:
      • Trace this algorithm on at least the graph I gave you, but perhaps all three.
      • What is the performance of MULTI-SOURCE-BFS?
  8. I have a working copy of the program if you encounter any problems.
    • Up to you, write it yourself, follow the steps below, use mine, or some combination.
  9. Begin implementation
    • Note in your document any code you do not understand.
    • Start a c++ program.
    • Include
      • iostream
      • map
      • vector
      • algorithm
      • queue
    • Declare a NodeT that can hold
      • An adjacency list (vector of ints)
      • An integer cost
      • struct NodeT {
            vector adj;
            int cost{0};
        };
    • We will be using a map of these
      • This is sort of a complex name, so set up an alias
        using GraphT = map<int,NodeT>;
    • Declare your main routine
    • Declare
      vector<int> horrorList;
    • Declare a graph
      GraphT graph;
  10. Read in the data
    • All Kattis programs read from standard in and write to standard out.
    • Read in the movies
      • // read in the vertex count and initialize the graph
            vector horrorList;
            GraphT graph;
        
            int movies;
            cin >> movies;
        
            for(int i = 0; i < movies; ++i){
               graph[i].cost = movies + 1;
            } 
      • I initially had a bug in that some vertexes might have any edges, and I didn't initialize the graph properly.
      • The loop should probably be done in the MultiDFS routine, but I wanted to save time and not loop through any more than I had to, so it is here.
      • Kattis problems have a fairly tight time limit! Sometimes you make less than completely clean code to save time.
    • Read in the next two constants
      • int horrorListSize;
        cin >> horrorListSize;
        
        int edges;
        cin >> edges;
    • Read in the horror list
      • for(int i = 0; i < horrorListSize; ++i) {
                int tmp;
                cin >> tmp;
                horrorList.push_back(tmp);
        }
    • Read in the edges
      • for(int i = 0; i < edges; ++i) {
           int src, dest;
           cin >> src >> dest;
           graph[src].adj.push_back(dest);
           graph[dest].adj.push_back(src);
        }
  11. Implement MultiDFS
    • You may do this on your own, or use my code.
    • Function Prototype
      • void MultiDFS(GraphT & G, vector sources);
    • Function Implementation
      • void MultiDFS(GraphT & G, vector sources) {
        
            // the max cost has already been set up for each node in the graph.
            queue Q;
        
            for(auto x: sources) {
               G[x].cost = 0;
               Q.push(x);
            }
        
            while (Q.size() > 0) {
               int u = Q.front();
               Q.pop();
        
               for(auto v: G[u].adj) {
                  if (G[v].cost > G[u].cost + 1) {
                     G[v].cost = G[u].cost + 1;
                     Q.push(v);
                  }
               }
            }
        }
    • Call this function after your input section in main.
      • MultiDFS(graph, horrorList);
  12. Finish by computing the answer and print the result.
    • Back in main, under the MultDFS call
    • int maxCost{graph[0].cost};
          int maxID{0};
      
          // find the answer
          for(auto & x: graph) {
             if (maxCost < x.second.cost) {
                 maxCost = x.second.cost;
                 maxID = x.first;
             }
          }
      
          cout << maxID << endl;
          return 0;
      }
  13. Compile, debug and test your code.
    • Compile it.
    • create three files a.dat, b.dat and c.dat that contain the test cases.
    • Run the program on all three test cases.
    • ./horror < a.dat
      ./horror < b.dat
      ./horror < c.dat
    • The answers should be 1, 3, 3
  14. Submit your problem to Kattis
    • Include a screen shot of the accepted solution, or of it passing at least the first 2 test cases.
  15. In my first implementation, I ran a BFS for each movie in the horror list, with maintenance to keep track of the "lowest" horror rating at each node. This sovled the problem but took too much time.
    • What is the worst case performance for this implementation?
  16. Write a reflection on this lab discussing, what, if anything you learned.

Required Files

A file to d2l containing your answers.

Submission

Submit the assignment to the D2L folder Activity 2 by the due date.