dyzmax
BAN USERTime O(n), memory O(n).
It works by sorting the heap in a quick way by using heap properties. The mechanism is similar to the one used in Dijkstra algorithm for shortest paths:
1. I start from the root node (heap max), adding it to the list of “edge nodes” - the nodes that I am choosing the current max from. This max is the next element in the ordered heap.
2. in an infinite loop I remove the max element from the edge nodes list, know that this is the next element in the order, then I take its children and add them to the “edge nodes” list. I sort the edge nodes list by merging in O(number of edge nodes), to be able to get the max in the next iteration in O(n), and repeat.
3. I finish when I return the k-th edge nodes value maximum, which is k-th element in the order
Memory complexity is O(n/2) == O(n) (in the worst case I have all heap leafs in the edge nodes list)
Time complexity is O(2n) == O(n) (for every processed edge node while adding its children I need to merge 2 elements child list with list of existing edge nodes that has between 1 and log n elements. This would make nlogn but if you look more carefully you will see that the ratio of those bad logns and good 1s is such it totals to 2n. This is similar situation like when at the first glance heap construction is O(nlogn), but if you look more carefully it can be in fact done in O(2n). Thank you Skiena, the best spent $80 in my computer programmer life :)
class EdgeNode {
int idx, value;
public EdgeNode(int idx, int value) {
this.idx = idx;
this.value = value;
}
}
// k == 0, 1, 2 …
public int getHeapKthElement(int a[], int k) {
if (a == null) { throw new IllegalArgumentException();}
if (a.length < k) { throw new NoSuchElementException();}
LinkedList<EdgeNode> edgeNodes = new LinkedList<NextNode>();
edgeNodes.add(new EdgeNode(0, a[0]);
int count = -1;
for (;;) {
EdgeNode maxNode = edgeNodes.removeFirst();
if (++count == k) {
return maxNode.value;
}
LinkedList<EdgeNode> childNodes = getChildNodesSorted(a, maxNode.idx);
edgeNodes = merge(edgeNodes, childNodes);
}
throw new RuntimeException(“we should never be here …”);
}
private LinkedList<EdgeNode> getChildNodesSorted(int a[], int i) {
LinkedList<EdgeNode> childNodes = LinkedList<EdgeNode>();
Integer child1 = i * 2 + 1 < a.length ? a[i * 2 + 1] : null;
Integer child2 = i * 2 + 2 < a.length ? a[i * 2 + 2] : null;
// two element sort, if needed
if (child1 != null && child2 != null && child2 > child1) {
Integer tmp;
tmp = child2;
child2 = child1;
child1 = tmp;
}
if (child1 != null) {
childNodes(child1);
}
if (child2 != null) {
childNodes(child2);
}
return newNodes;
}
private LinkedList<EdgeNode> merge(LinkedList<EdgeNode> edgeNodes, LinkedList<EdgeNode> childNodes) {
LinkedList<EdgeNode> merged = new LinkedList<EdgeNode>();
Iterator<EdgeNode> edgeNodeIt = edgeNodes.iterator();
Iterator<EdgeNode> childNodeIt = childNodes.iterator;
EdgeNode edgeNode, childNode;
if (edgeNodeIt.hasNext()) {
edgeNode = edgeNode.next();
}
if (childNodeIt.hasNext()) {
childNode = childNode.next();
}
for (;;) {
if (edgeNode == null) {
if (childNode != null) {
merged.add(childNode);
}
while(childNodeIt.hasNext()) {
merged.add(childNodeIt.next());
}
return merged;
}
if (childNode == null) {
if (edgeNode != null) {
merged.add(edgeNode);
}
while(edgeNodeIt.hasNext()) {
merged.add(edgeNodeIt.next());
}
return merged;
}
if (edgeNode.value < childNode.value) {
merged.add(childNode);
if (childNodeIt.hasNext()) {
childNode = childNodeIt.next();
}
} else {
merged.add(edgeNode);
if (edgeNodeIt.hasNext()) {
edgeNode = edgeNodeIt.next();
}
}
}
return merged;
}
1. construct graph of dependencies.
- dyzmax June 19, 20152. for every edge, if one of the nodes is “both” set weight to 0, if both nodes have the same semester assign 0, if they have different semesters assign 1
3. for every starting node (no dependency node) that starts in spring, add a non dependency artificial node that that has an edge to the starting node, with weight 1 (this is to ensure that we always start counting in fall)
4. you may have now multiple “starting” (without dependencies nodes). if this is the case add a single artificial node (let’s call it a “graph source”) that has 0 weight edges to all no dependency nodes. this will make your graph having only one no dependency node
5. do dijkstra algorithm starting from source (after the action from 4 you have only a single source node). after you are done you will get the lengths of the paths between the source node and all the nodes. max of those path lengths would be your answer if there are no semester limits.
6. let’s make your solution obey the limits. first let’s notice that after dijkstra run you have your courses sliced (grouped) in layers - all the nodes that have the same distance from the source are in the same layer, they are happening in a single semester. you iterate through layers starting from semester 0, and do the following:
a) if the number of nodes is <= the limit, you are fine. you go to the next layer (semester). in the limit check you do not consider artificial nodes you added in points 3 and 4
b) if the number of nodes is > the limit, then you need to push some nodes forward to obey the limit. if your limit is “l”, and number of nodes in the semester is “k” (k > l), then you need to choose all possible layer subsets that have l - k elements (the number of nodes that you have over limit). For every such subset you do the following:
i) you push them forward by modifying the graph. If the season assigned to your layer (spring or fall) is different than the season of the over the limit node or the over the limit node is “both”, you add 1 to the weight of all the edges incoming to this node. Otherwise (If the seasons are the same and over the limit node’s season is not both), you add 2.
ii) now you have a new graph, that fixed the limit in the layer you were in. you are doing dijsktra starting from this layer ( before you remove all the min path information for the nodes in the layers later than the one you removed over the limit nodes from). after dijkstra either you have a new result within limits, or one of the layers is again over the limits. You do the recursive call of the same limits fixing procedure - you push over the limit nodes forwrad etc etc. By doing that at some point you will fix all the layers.
7. when pushing forward all over the limit subsets and repeating that for all the over the limit layers, you will get a recursion tree which at leafs has one possible arrangement of courses that is within the limits and dependencies. Such tree has a max path. the min of max paths over all such trees is your solution.