Can anyone explain the Tata CLiQ Backend Hiring Challenge
2nd problem Cost of tree? I am able to complete it. Sample test case is working but solution I am not able to submit successfully. Can someone suggest the approach or solution.
Note : My approach using DFS and sum the total cost with the help of visited array.
Challenge Link
Hi did you get the solution
Hi, I did djikstra and stored previous elements. then went through all the paths and counted edge weights encountered. and removed most weight C edges. but i faced TLE for few test cases. I wasnt able to figure out a better way to calculate edge_weight * num_of_times_encoured for each edge. my approach was o(n^2) worst case
I solved using below code. Since some of the test cases are not working. I did using DFS. Attached problem statement.
/*******************************************************************
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
public class TestClass {
//Given code in system. we have to complete **solve function**.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
PrintWriter wr = new PrintWriter(System.out);
int T = Integer.parseInt(br.readLine().trim());
for (int t_i = 0; t_i < T; t_i++) {
String[] line = br.readLine().split(" ");
int N = Integer.parseInt(line[0]);
int C = Integer.parseInt(line[1]);
int u = Integer.parseInt(line[2]);
int[][] edge = new int[N - 1][3];
for (int i_edge = 0; i_edge < N - 1; i_edge++) {
String[] arr_edge = br.readLine().split(" ");
for (int j_edge = 0; j_edge < arr_edge.length; j_edge++) {
edge[i_edge][j_edge] = Integer.parseInt(arr_edge[j_edge]);
}
}
//sample Inputs
/*
* 1
5 1 3
1 2 2
2 3 3
3 4 4
4 5 5
5 2 6
*/
/*
* 1
10 3 2
1 2 6
2 3 7
3 4 10
4 6 12
5 2 8
7 5 13
8 1 5
9 4 11
10 3 9
*/
long out_ = solve(N, C, u, edge);
System.out.println(out_);
}
wr.close();
br.close();
}
static long solve(int N, int C, int u, int[][] edge) {
// Type your code here
Map<Integer, List<Integer>> hello = new HashMap<>();
Map<String, Integer> costMap = new HashMap<>();
//creating TREE or ACYCLIC graph
for (int i = 0; i < N - 1; i++) {
if (!hello.containsKey(edge[i][0])) {
List<Integer> path = new ArrayList<>();
path.add(edge[i][1]);
hello.put(edge[i][0], path);
} else {
hello.get(edge[i][0]).add(edge[i][1]);
}
if (!hello.containsKey(edge[i][1])) {
List<Integer> path2 = new ArrayList<>();
path2.add(edge[i][0]);
hello.put(edge[i][1], path2);
} else {
hello.get(edge[i][1]).add(edge[i][0]);
}
costMap.put(edge[i][1] + " " + edge[i][0], edge[i][2]);
costMap.put(edge[i][0] + " " + edge[i][1], edge[i][2]);
}
long minimum = 0;
Set<Integer> considered = new HashSet<>();
for (int i = 1; i <= C; i++) {
int max_cost = 0;
int next_adj = 0;
List<Integer> temp = hello.get(u);
if (temp.size() > 0) {
for (int x : temp) {
if (max_cost < costMap.get(u + " " + x) && !considered.contains(x)) {
max_cost = costMap.get(u + " " + x);
next_adj = x;
}
}
costMap.put(u + " " + next_adj, 0);
considered.add(next_adj);
}
//take a edge of u.
long cost = 0;
for (int j = 0; j <= N - 1; j++) {
//System.out.println(j);
if ((j + 1) == u) {
cost += 0;
} else if ((j + 1) == next_adj) {
cost += 0;
} else {
Set<Integer> visited = new HashSet<>();
cost = cost + findSubCost(u, j + 1, 0, hello, costMap, visited);
}
}
if (minimum == 0 || minimum > cost) {
minimum = cost;
}
costMap.put(u + " " + next_adj, max_cost);
}
return minimum;
}
static long findSubCost(int u, int vertex, int parent, Map<Integer, List<Integer>> hello, Map<String, Integer> costMap, Set<Integer> visited) {
long cost = 0;
long minCost = 0;
if (visited.contains(vertex)) {
return Long.valueOf(Integer.MAX_VALUE).longValue();
}
if (costMap.containsKey(u + " " + vertex)) {
visited.add(vertex);
return costMap.get(u + " " + vertex);//21->2...
}//1->1,2... 2->1,3.... 3->2,4
if (!visited.contains(Integer.valueOf(u))) {
List<Integer> vert = hello.get(u);
visited.add(u);//3...2...1
for (Integer t : vert) {
if (t == parent)
continue;
cost = costMap.get(u + " " + t);
cost = cost + findSubCost(t, vertex, u, hello, costMap, visited);
if (minCost == 0 || minCost > cost) {
if(visited.contains(vertex))
minCost = cost;
}
}
}
return minCost;
}
}This can be solved using DFS. The idea is to find the contribution of each edge in the final answer, and then change the weights of min(C, N - 1) edges with higher contributions. This can be done by sorting the edge contributions and removing the last min(C, N - 1) elements.
To find contribution of each edge: During DFS (with u as root), store the subtree size of each node. Then the contribution for edge X->Y is weight(edgeXY) * subtreeSize(Y), as there are subtreeSize(Y) paths which pass through this edge.
Now sort all the edge contributions and remove last min(N - 1, C) elements. The answer is the sum of remaining elements.
2 Likes
What is the approach for King’s Pawn problem? I was not able to do it.