This can be modelled as a graph problem. Create a graph node for each row and column where there’s a monster. Connect the nodes if a monster is on that row and that column. This is a bipartite graph, and you want to do minimum vertex cover. König’s theorem shows that for bipartite graphs the … Read more
Each time you fill a bucket of 10 liters, you will have 10 fewer liters in your source bucket. Each time you fill a bucket of 2 liters, you will have 2 fewer liters in your source bucket. Each time you fill a bucket of 50 liters, you will have 50 fewer liters in your … Read more
It is named Exchange sort and is sometimes confused with bubble sort. While Bubble sort compares adjacent elements, Exchange sort compares the first element with all the following elements and swaps if needed. Then it does the same for the second element and so on. 0 solved What is this inefficient sorting algorithm with two … Read more
I don’t know exactly what data structure you get the wall in, but assuming it is: std::vector<std::vector<char>> wall; To be able to perform melting using std::sort, it is best to have columns in the outer vector and rows in the inner vectors. // melting bricks for (int col = 0; col < wall.size(); ++col) //column … Read more
As I understand it the function (of two symmetric positive definite matrices) is JL(X,Y) = log( det( (X+Y)/2)) – log( det( X*Y))/2 = log( det( (X+Y)/2)) – (log(det(X)) + log(det(Y)))/2 I reckon the way to do this is to compute the cholesky factorisations of X, Y and (X+Y)/2, that is find lower triangular matrices L,M,N … Read more
You can use Array.reduce() to do it: Sort the array (safety) Iterate over the array with reduce to create an object containing the ranges and the start of the active range (rangeStart). On the first iteration, push the first element in the ranges and save this element as the rangeStart On the successive iterations, if … Read more
You can build a backtracking based solution to formulate all the possible sub-sequence for the given array. Sharing an ideone link for the same: https://ideone.com/V0gCDX all = [] def gen(A, idx = 0, cur = []): if idx >= len(A): if len(cur): all.append(cur) return gen(A, idx + 1, list(cur)) incl = list(cur) incl.append(A[idx]) gen(A, idx … Read more
base becoming multiplied by 5 got lost in the second version. public static int trailingZeroesV2(int n) { return trailingZeroesV2(n, 5); } private static int trailingZeroesRec(int n, int base) { return n == 0 ? 0 : n / base + trailingZeroesRec(n / 5, base * 5); } (Typically a recursive function uses an extra parameter,) … Read more
There is no built-in functionality to do that, since you throw away information (the length of each string). So that information have to be stored somewhere. You could use a TStringList descendant : Interface TMyStrings = class(TStringList) protected function GetTextStr: string; override; end; Implementation { TMyStrings } function TMyStrings.GetTextStr: string; var Element: String; begin Result … Read more
You can see this as a graph theory problem (http://en.wikipedia.org/wiki/Graph_theory). Each given state of your puzzle is a Vertice of the graph, and each light switching is an edge that takes the Graph to another state. Given a starting state, if you expand your graph breadth-first, your will find the sortest solution (http://en.wikipedia.org/wiki/Breadth-first_search). It is … Read more
So from the sound of your question you are attempting to get a binary search working for your example. First, it is useful to know that a binary search only works reliably on sorted data. This is quite different than a standard linear search that will always find the value, regardless of order. As you … Read more
The problem is that you haven’t coded DFS-VISIT step 4 correctly Step 4 says for each v ∈ G.Adj[u] but your code says for(int i=0; i<G; i++). Those aren’t the same thing at all. You should only visit the adjacent vertexes. In fact if you look at your code you never use adj at all. … Read more
The problem could be solved using recursion. For example, the code below prints exactly the required matrix for a given n. import java.util.Scanner; public class Main { public static void main(final String[] args) { final Scanner scanner = new Scanner(System.in); final int n = scanner.nextInt(); final int[][] matrix = create(1, (int) Math.pow(2, n)); print(matrix); } … Read more
Just a small improvement based on your code to find limit primes instead of limit numbers. limit = 1000 def is_prime(n): for i in range(2, n): if n%i == 0: return False return True sum = 0 num = 2 for i in xrange(limit): while not is_prime(num): num += 1 sum += num num += … Read more
You can create a regex to capture words and process using your function to parse individual words. For demonstration purpose, I have used the regex: /[a-z0-9]/gi (assuming you will have only alphanumeric characters in a word. Please update the regex if you can have other characters as well.) Following is a sample: function toCapitalize(s) { … Read more