here is hackerrank couting on a tree solution

Hi there!

Don't use stupid main function provided by Hackerrank for Java.

It is extremly slow! Just load of test case exceed time limit on test case 4+.

Beware! Rewrite it:

    public static void main(String[] args) throws IOException {
        final Scanner scanner = new Scanner(System.in);
        final BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int n = scanner.nextInt();
        int q = scanner.nextInt();
        int[] values = new int[n];
        for (int i = 0; i < n; ++i) {
            values[i] = scanner.nextInt();
        }
        int[][] tree = new int[n - 1][2];
        for (int i = 0; i < n - 1; ++i) {
            tree[i][0] = scanner.nextInt();
            tree[i][1] = scanner.nextInt();
        }
        int[][] queries = new int[q][4];
        for (int i = 0; i < q; ++i) {
            queries[i][0] = scanner.nextInt();
            queries[i][1] = scanner.nextInt();
            queries[i][2] = scanner.nextInt();
            queries[i][3] = scanner.nextInt();
        }

        int[] result = solve(values, tree, queries);

        for (int i : result) {
            bufferedWriter.write(String.valueOf(i));
            bufferedWriter.newLine();
        }
        bufferedWriter.close();
        scanner.close();
    }

Tough one. DFS for depth building, LCA for path finding (using depth), trying to put node with most connections at the root of the tree, simple math for sums (will fit in normal int), optimized visited nodes storage. Tried caching paths (no improvement). Still getting 8 timeouts (TCs: 5,6,8,9,11,14,15,17) :(

Undoubtedly there's another algo or structure I need to use.

include

include

include

include

include

include

using namespace std;

typedef struct _node { _node * prev; int value; int index; _node() { prev = NULL; value = 0; index = 0; } } NODE;

int GetPathFromRoot(int b, NODE *pNode, vector& nodes) { unsigned int i = 0; NODE *curNode = &pNode[b]; do { nodes.push_back(curNode); curNode = curNode->prev; } while (curNode != NULL); return 0; } int num = 0; int GetPath(int a, int b, NODE *pNode, vector& nodes) { //Get root to a vector rootA; vector rootB;

int *flag = new int[num];
memset(flag, 0, sizeof(int)*num);
GetPathFromRoot(a, pNode, rootA);    
GetPathFromRoot(b, pNode, rootB);


//merge rootA and rootB
int nA = 0;
int nB = 0;
int found = 0;
for (unsigned int i = 0; i < rootA.size(); i++)
{        
    flag[rootA[i]->index-1] = 1;
}
for (unsigned int i = 0; i < rootB.size(); i++)
{
    if (flag[rootB[i]->index-1] == 1)
    {
        nB = i;
        nA = rootB[i]->index;
        break;
    }
}

for (unsigned int i = 0; i < rootA.size(); i++)
{
    if (rootA[i]->index == nA)
        break;
    nodes.push_back(rootA[i]);
}
for (int i = nB; i >= 0; i--)
{
    nodes.push_back(rootB[i]);
}
delete [] flag;
return 0;

}

int FindSame(int w, int x, int y, int z, NODE *pNode) { int nMatch = 0; vector wxNode; vector yzNode; GetPath(w, x, pNode, wxNode); GetPath(y, z, pNode, yzNode);
for (unsigned int i = 0; i < wxNode.size(); i++) { for (unsigned int u = 0; u < yzNode.size(); u++) { if (wxNode[i]->value == yzNode[u]->value && (wxNode[i] != yzNode[u])) { nMatch++; } } } cout << nMatch << endl; return nMatch; }

int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */
int nodeNum = 0; int queryNum = 0; int i = 0; cin >> nodeNum; num = nodeNum; cin >> queryNum; NODE *pNode = new NODE[nodeNum];

for (i = 0; i < nodeNum; i++)
{
    cin >> pNode[i].value;
    pNode[i].index = i+1;       
}
int node1 = 0;
int node2 = 0;
bool fwd = true;
cin >> node1;
cin >> node2;
if (node1 == 1)
{
    fwd = true;
    pNode[node2-1].prev = &pNode[node1-1];   
}
else
{
    fwd = false;
    pNode[node1-1].prev = &pNode[node2-1];   
}


for (i = 1; i < nodeNum-1; i++)
{

    cin >> node1;
    cin >> node2;
    if (fwd)
        pNode[node2-1].prev = &pNode[node1-1];        
    else
        pNode[node1-1].prev = &pNode[node2-1]; 

}

//Tree is built

for (i = 0; i < queryNum; i++)
{
   int w = 0, x = 0, y = 0, z = 0;
    cin >> w;
    cin >> x;
    cin >> y;;
    cin >> z;
    FindSame(w-1, x-1, y-1, z-1, pNode);        
}
delete [] pNode;
return 0;

}

workts but timeout

Can this be passed with Python? I implemented a min-heap, and used it for dijkstra pathfinding, and I still timeout on all tests but the first.