Example 0: {1, 3, 2, 6, 4, 5 }: |
0: { 1, 3, 2, 6, 4, 5 }. Answer = 4.
The subsequences are: { 1, 3, 6 }
{ 1, 2, 6 }
{ 1, 3, 4, 5 }
{ 1, 2, 4, 5 }
1: {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}. Answer = 10.
Each subsequence of size 1 is a maximum increasing subsequence. There are no others.
2: {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}. Answer = 1.
The whole thing is an increasing sequence, so any subsequence will be increasing, but
not maximal.
3: {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}. Answer = 41.
Now, what's the rule for that? There should be an edge from a[i] to a[j] if a[j] is greater than a[i] and there is no number between the two -- in other words there is no k such that i < k < j and a[i] < a[k] < a[j]. Here are graphs for each of their examples:
|
Example 0: {1, 3, 2, 6, 4, 5 }: |
Example 1: {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}:
 |
Example 2: {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}
 |
Example 3: {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}
 |
Now that you have this graph, what is a maximum subsequence? It's a path from a node with no incoming edges to a node with no outgoing edges. Given that, our job is to determine how many such paths there are. It should be easy to see that the number of paths is 4 in example zero, 10 in example 1, and 1 in example 2. What about example 3? That's a mess!
So, we can be quantitative. There is one path to any node with no incoming edges. Otherwise, the number of paths to a node is the sum of the number of paths to nodes incident to it. In example 1, there is one path to nodes one, three and two. There are two paths to node six and two paths to node four. And thus two paths to node five. So, the sum of paths to nodes with no outgoing edges is four.
How do we calculate this? Using topological sort! We start with nodes with no incoming edges. They have one path. Then we do a topological sort -- every time we process a node, we go through each of its edges, and add its number of paths to the nodes to which it is connected. Then we remove the edges. When we're done, we sum up the number of paths to nodes with no outgoing edges.
I'll put this calculation in all the examples below. I've colored nodes with no outgoing edges magenta. The sum of the values in these nodes is our answer:
Example 0: {1, 3, 2, 6, 4, 5 }: |
Example 1: {1000000000,100000000,10000000,1000000,100000,10000,1000,100,10,1}:
 |
Example 2: {1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000}
 |
Example 3: {564,234,34,4365,424,2234,306,21,934,592,195,2395,2396,29345,13295423,23945,2}
 |
Before looking at all of my code, I want to highlight the code that creates each node's adjacency list, since this can confuse students. Remember when there is an edge from node i to node j: It's when i's value is less than j's value, and there is no node between i and j whose value is between node i's value and node j's value. To implement this, I have made the realization that these j nodes will have decreasing values. So, I keep track of the maximum value of the last j node. If the new j node's value is between this value and i's value, then we can create the edge.
Here's the code for that part. All of the nodes are in the vector N and they are pointers to Node classes. They store their values in Value. The adjacency list for a node is in its member value Adj, which is a vector of pointers to nodes:
/* Create the adjacency list for each node */
for (i = 0; i < N.size(); i++) {
bigval = 1000000001;
n = N[i];
for (j = i+1; j < N.size(); j++) {
to = N[j];
if (to->Value > n->Value && to->Value < bigval) {
n->Adj.push_back(to);
bigval = to->Value;
to->NumIncident++;
}
}
}
|
#include <string>
#include <vector>
#include <deque>
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
/* This is not how I solved the problem when I did it in topcoder.
When I did it in class, the students wanted me to use a class
for graphs and a class for nodes. I like that, because my
node list and adjacency lists hold pointers to nodes, which
gives you practice with pointers. */
class Graph {
public:
vector <class Node *> N; // The nodes in the graph
deque <class Node *> L; // This is the list of nodes with no incoming edges.
vector <int> A; // The original input.
void Make_Graph(); // Method to create the graph from the input.
long long TS(); // Method to perform the topological sort
};
class Node {
public:
int ID; // The node's id (its index in Graph::N)
int Value; // The node's value (A[ID])
vector <Node *> Adj; // Adjacency list
int NumIncident; // Number of edges incident to the node.
long long Paths; // Number of paths to N
};
/* Make Graph creates the graph from the input vector. */
void Graph::Make_Graph()
{
int i, j;
Node *n, *to;
int bigval; // Bigval is a sentinel that we use to create the
// adjacency lists.
/* First create all of the nodes. Initialize the values stored in each node. */
N.resize(A.size(), NULL);
for (i = 0; i < A.size(); i++) {
n = new Node;
n->ID = i;
n->Value = A[i];
n->Paths = 0;
n->NumIncident = 0;
N[i] = n;
}
/* Create the adjacency list for each node */
for (i = 0; i < N.size(); i++) {
bigval = 1000000001;
n = N[i];
for (j = i+1; j < N.size(); j++) {
to = N[j];
if (to->Value > n->Value && to->Value < bigval) {
n->Adj.push_back(to);
bigval = to->Value;
to->NumIncident++;
}
}
}
/* For each node that has no incident edges, push the node onto the list L */
for (i = 0; i < N.size(); i++) {
if (N[i]->NumIncident == 0) {
L.push_back(N[i]);
N[i]->Paths = 1;
}
}
/* This loop prints out the graph for debugging. */
for (i = 0; i < N.size(); i++) {
n = N[i];
printf("Node %d: NumIncident: %d. Adj:", i, n->NumIncident);
for (j = 0; j < n->Adj.size(); j++) {
printf(" %d", n->Adj[j]->ID);
}
printf("\n");
}
}
/* TS performs the topological sort to count the paths from
nodes with no incoming edges to nodes with no outgoing edges. */
long long Graph::TS()
{
long long RV;
Node *n, *t;
int i;
RV = 0;
while (!L.empty()) {
/* Process the first node on L, and then delete it. We use a deque for
this, because it implements push_back() and pop_front() in constant time */
n = L[0];
L.pop_front();
/* If the node is terminal (has no outgoing edges), then add its
number of paths to the overall return value. */
if (n->Adj.size() == 0) RV += n->Paths;
/* Process the adjacency list, adding my paths to each node on my adjacency
list, and then "erasing" the edge by decrementing NumIncident on the
node that the edge is going to. If that number is zero, then push the node
onto L. */
for (i = 0; i < n->Adj.size(); i++) {
t = n->Adj[i];
t->Paths += n->Paths;
t->NumIncident--;
if (t->NumIncident == 0) L.push_back(t);
}
}
return RV;
}
class IncreasingSubsequences {
public:
long long count(vector <int> a);
};
/* The main method to solve the topcoder problem simply creates the graph,
then returns the return value of TS. */
long long IncreasingSubsequences::count(vector <int> a)
{
Graph G;
G.A = a;
G.Make_Graph();
return G.TS();
}
|