Recently, I learned about Tarjan and Kosaraju's algorithms to find articulation points.

However, I was wondering whether there are algorithms to find vertices whose removal disconnects the graph into three or more components (as opposed to two). I've searched online, and I cannot find anything (perhaps I'm using the wrong search terms?).

I have a guess, but I'm not sure if this is correct. I think that we can take the DFS tree, and conclude that a vertex satisfies my condition if one of the following is true:

1) It's the parent of the DFS tree with three or more children.

2) It's not the parent of the DFS tree with two children.

This seems too easy to me, so I'm pretty sure it's wrong.

Can someone please help me with this problem?

This is a problem on an algorithms final that I'm studying for.

You are tryng to get from City A to City for the cheapest cost. Your company will pay for exactly one flight between two cities (from a list of flights), but aside from that, you need to drive from the rest of the trip. Given a matrix $$$C[x, y]$$$ that represents the money needed to drive from city $$$x$$$ to city $$$y$$$, and a Boolean matrix $$$F[x, y]$$$, which is TRUE if there's a flight from $$$x$$$ to $$$y$$$ and FALSE otherwise, find an algorithm that finds the minimum amount of money you have to pay to get form $$$A$$$ to $$$B$$$.

This is a problem from a previous final that I am studying with. Apparently the full credit solution was something that runs in $$$\mathcal{O}(V^2)$$$ time, but the only solution that I can think of is to run Dijkstra's $$$n^2$$$ times (bruteforce). Can someone please help me study? We haven't covered anything super advanced (this is an intro algorithms class).

As a part of a project, I am troubled with the following problem:

Given an l x w rectangle, where 1 <= l, w <= n as well as n polygon-shaped dominoes d1, d2, d3, ..., dn (each domino does not necessarily have just a length and width -- it is a polygon), I want to cover as much of the l x w rectangle as possible using the given dominoes.

The dominoes that are placed into the rectangle don't necessarily need to be small enough to fit inside of the rectangle, so we need to be able to recognize this and not use those dominoes in invalid places.

Now suppose I hypothetically have an O(n^k) algorithm that solves the following problem:

"Given the list of dominoes, the rectangle dimensions (l and w) and some value x, this algorithm returns true if there exists some way to cover at least x squares with the dominoes and the algorithm returns false otherwise."

Now using this algorithm, is it possible to find a tiling of the l x w rectangle that covers as many squares as possible (i.e. a maximal orientation) in polynomial time? I want to figure out if it is possible and how fast it would be.

You can find the maximal value of x in polynomial time. But then finding which dominoes to use and their orientation is difficult.

Some ideas (but I might be completely wrong):

• Represent the squares as nodes in a graph?

• Maybe something clever with DP?

Given N points representing the coordinates of heroes on the coordinate plane and another N points representing the coordinates of enemies on the coordinate plane, each hero plans to battle a single enemy (the number of enemies equals the number of heroes, so nobody is ever left out).

Each hero prioritizes the enemy that is closest to them, where distance is defined as taxicab (orthogonal) distance as opposed to Euclidean distance. For example, if we have two points p, q, then the distance is NOT sqrt((p.x — q.x)^2 * (p.y — q.y)^2) but instead |p.x — q.x| + |p.y + q.y|. No two pairs of heroes and enemies will have the same distance.

What's an efficient way to make the matching? I thought about lots of graph algorithms but cannot come up with much. Maybe something with a priority queue/heap?

Thank you

Given a list of N integers, what's the minimum number of operations you need to perform to make them all equal? An "operation" consists of subtracting one number by one, and adding another number by two. Or, when is it not possible?

I think this was a problem in a codeforces or topcoder, but I cannot remember where. For example, if N = 5 and we have Array = [6, 1, 1, 1, 1], you can make them all equal to 2 in just four operations.

Clearly, they all need to become equal to Sum/N, but the hard part is determining whether it is possible or not. I was trying to do this with a while loop but it is getting really slow when I try for large numbers.

Sorry if this is a really silly question but I would appreciate any assistance with this problem. This seems like a really simple problem, but I am struggling. Additionally, if anyone recognizes this problem please link me in the comments so I can try to submit.

Hey everyone, I'm pretty new to binary searching, and I would really appreciate some help with this problem. I initially started trying to solve this problem last week, and I still haven't solved it!

Here's the problem: "Given an array A of N (1 <= N <= 100,000) positive integers, is it's possible to remove exactly two elements in the array to form a partition of the array into three continuous sub-arrays with equal sums?"

For example, if A = [1, 3, 4, 2, 2, 2, 1, 1, 2], you can remove the "4" and the second-to-last "2" in order to get the following array: A = [1, 3, REMOVED, 2, 2, REMOVED, 1, 1, 2]. This works because 1 + 3 = 2 + 2 = 1 + 1 + 2 = 4. But in some cases it might not be possible. For instance, if A = [1, 1, 1, 1, 1, 1], it's impossible.

The solution (thanks to apostoldaniel854) is as follows:

Compute the prefix array of the array A so that we can do range-querying in O(1). Now let i, j be the indices of the elements that we're going to remove. If we fix i so that our first sub-array is A[0...i-1], we know that the other two subarrays need to have sum equal to prefix[i — 1]. In order to see if this is possible, we can search for the first position of j such that sum[1...i-1] <= sum[i+1...j-1] using binary search. If sum[1...i-1] != sum[i+1...j-1], then we can't get a partition of the original array with the selected value of i. Otherwise, we need to look at sum[j + 1...n] in order to see if it's equal to the other two sums. If it is, we've found a valid partition.

In theory this solution makes perfect sense to me. But, implementing it is a completely different story. I was wondering whether someone could please help me with this implementation -- I've been struggling with it for quite a long time now.

Here is what I have right now:

int main() {
	vector<int> A = {1, 3, 4, 2, 2, 2, 1, 1, 2};

	vector<int> prefix;
	prefix.push_back(A[0]);
        
	FOR(i, 1, A.size()) {
		prefix.push_back(prefix[i - 1] + A[i]);
	}

	/* Let i, j be the indexes of the element we are going to remove. */
	FOR(i, 1, A.size() - 3) {
		int sum_of_subarray_one = prefix[i - 1];

		/* Now we want to find the first position j so that
		 * sum[1...i-1] <= sum[i+1...j-1] with binary search. */
	}

	return 0;
}

I'm really just struggling with the part where we need to do a binary search. I can bruteforce the value of j with another for-loop, but that gives me an O(n^2) time complexity. With binary search, I would be able to get O(nlogn). I would greatly appreciate anyone's help in this problem. It seems like whenever I try one thing, another problem arises somewhere else :)

I was wondering if anyone knows how to solve the following question. I have tried on-and-off for about a week now, but I cannot figure it out:

Given an array A of N (1 <= N <= 100,000) positive integers, is it possible to remove exactly two elements in the array in order to form a partition of the array into three contiguous subarrays with equal sums?

For example, if A = [1, 3, 4, 2, 2, 2, 1, 1, 2], you can remove the "4" and the second-to-last "2" in order to get the following array: A = [1, 3, REMOVED, 2, 2, REMOVED, 1, 1, 2].

This works because 1 + 3 = 2 + 2 = 1 + 1 + 2 = 4.

But in some cases it might not be possible. For instance, if A = [1, 1, 1, 1, 1, 1], it's impossible,

Something important to keep note of is that don't need to determine which elements to remove but rather whether or not it is possible (so just yes/no is enough).

I have been struggling for a really long time with this problem. It is a variant of the "partition an array into 3 parts with equal sums" problem since you're forced to drop two elements in the array here.

I have tried thinking of DP solutions with no luck. Does anyone know how I can solve this? I think prefix sums might be useful here.