jaehyunp / stanfordacm Goto Github PK

This repo is really helpful to learn to implement clean algorithms.

It seems like that KMP.cc doesn't handle the case when pattern's length < 2. It is better to fix this problem.

Hi
I tried the code with the following edge costs:

int cost3[][] = { { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 2, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 2, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 2, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0, 0}, { 0, 0, 0, 0, 0, 0, 0, 0, 1}, { 0, 0, 0, 0, 0, 0, 0, 0, 0} };
and the following edge capacities:
`int cap3[][] = { { 0, 1, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, INF, 0, 0, INF, 0 },
{ 0, 0, 0, 0, 0, INF, 0, INF, 0 },
{ 0, 0, 0, 0, 0, 0, INF, INF, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, INF },
{ 0, 0, 0, 0, 0, 0, 0, 0, INF },
{ 0, 0, 0, 0, 0, 0, 0, 0, INF },
{ 0, 0, 0, 0, 0, 0, 0, 0, 2 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }

    };`

Your code gave the result 1 2, whereas, I think the result should be 2 2.
I am trying to represent a directed graph here. It is best visualized as an n-partite graph. In the first column, you have node 0, in the second column you have nodes 1, 2 and 3. In the third column, you have nodes 4, 5, 6 and 7. In the last column you have node 8.
Node 0 has edges to nodes 1, 2 and 3 with 0 edge cost and infinite edge capacity. Node 1 has edges to nodes 4 and 7. The edge from 1 to 4 has edge cost 2 and infinite capacity, whereas the edge from 1 to 7 has edge cost 0 and infinite capacity. Node 2 has similar edges to nodes 5 and 7. Node 3 has similar edges to nodes 6 and 7. Nodes 4, 5 and 6 have edges to node 8 with cost 0 and infinite capacity. Node 7 has an edge to node 8 with cost 1 and capacity 2.

The following code prints 5 3 4.

int main() {
  auto res = LongestIncreasingSubsequence(vector<int>({5,6,2,3,4}));
  for (auto i : res)
      cout << i << " ";
  cout << endl;
}

Although the Dinic implementation does give the correct result, the time complexity is not right. Issue tracked in TODO as well.