Given a tree in which each vertex represents an interval [x_i, y_i], you can merge adjacent vertices iff they intersect. The merged vertex has a new interval corresponding to the intersection of the previous two intervals, and its neighbors are the union of the neighbors of the merged vertices. How can you minimize the number of vertices after the process terminates?

I tried rooting the tree and attempting dynamic programming, but I’m not sure how to approach this. Any ideas?

You are given a matrix of characters and a starting point inside of the matrix. Every entry in the matrix except for one has the letter U, D, L, or R in it. When you are at an index that has an U, you most go up in the matrix. The same applies for the other characters (you must go down, left, or right, respectively).

We can represent this problem as a directed graph in which the entry (i, j) has an edge to one of its four neighbors if the entry at (i, j) tells us to move to that neighbor.

One entry in the matrix is marked “x”. In a single turn, you are allowed to choose an entry (i, j) and change its value to any one of U, D, L, or R. What is the minimum number of operations that you need to perform in order to ensure that one can reach the entry marked “x” from the given starting point? In other words, we can change the direction of any edge at a cost of one.

My initial thought is one can do a DFS from the starting point. If we can already reach x, the answer is zero. However, the problem is more complicated when we need to change edges. I feel that we can just reach any vertex that leads into x, so it’s not enough to just run a BFS from x either. Any help is appreciated.

Given $$$N \leq 10^{9}$$$, I want to place a vertical bar between any two consecutive digits to form two new integers. Let's call them $$$X$$$ and $$$Y$$$. How can we minimize $$$|X - Y|$$$?

Clearly, $$$N$$$ is so large, so we must get some non-linear solution. I thought about implementing something in which we first and second part, and we manually remove and add one digit at a time. However, this seems to be a little bit difficult when there are zeros.

For example, consider $$$30001$$$. We can split at the first zero to get $$$3$$$ and $$$0001$$$, so the answer is $$$|3 - 1| = 2$$$.

I also thought about using DP, but I think even a linear solution would get TLE. Any ideas are greatly appreciated.

This is part of a larger project that I am working on. It is not a contest problem.

Consider a complete graph $$$G = (V, E)$$$, where $$$V = {0, 1, 2, \ldots, n}$$$. The graph $$$G$$$ is a complete graph, so we can go from Vertex $$$i$$$ to Vertex $$$j$$$ for all $$$i, j \in V$$$. At each vertex $$$v \in V$$$, there is a task that we must complete. The task at vertex $$$v$$$ takes exactly $$$q_v > 0$$$ minutes, and we must complete all tasks. We start at Vertex $$$0$$$ and we have $$$q_0 = 0$$$.

Of course, it will take us exactly $$$\sum_{i = 1}^{n} q_i$$$ total time for us to complete all of the tasks on our own (it takes $$$0$$$ time to traverse edges). But now let's suppose that we have one helper. We can "dispatch" this helper at any one node (say $$$v$$$), and we can leave the node, go work on other tasks, and pick up the helper after $$$q_v$$$ minutes to drop it off at another node. The helper cannot move on its own; it must be picked up and dropped off by you. Essentially, we can "parallelize" this process to some extent.

Is there some sort of algorithm that allows one to find the best strategy that arises when we are allowed one helper?

I've already thought about greedy strategies (i.e, always drop the helper at the vertex that has the largest $$$q_i$$$, and go work on the quickest tasks available before coming back to pick up the helper), but there's no reason to believe that this is optimal. I thought that a DP on trees approach may help here, but I wanted to know what others thought.

Thank you.

Hi all,

While learning about minimum spanning trees a while back, I encountered the following problem:

Given a connected undirected graph $$$G = (V, E)$$$ and a subset of vertices $$$S = {v_1, v_2, \ldots, v_n}$$$, find a forest in which each vertex $$$v \in V \setminus S$$$ is connected to exactly one vertex of $$$S$$$ such that this forest has minimum total length (sum of edge weights).

I vaguely remember that the solution to this problem involved reducing the problem to a minimum spanning tree problem. In particular, a graph $$$G'$$$ was constructed in which one could run the minimum spanning tree on $$$G'$$$ in order to retrieve the final answer. However, I've forgotten the solution, and I'm wondering if someone can explain the solution to me.

I think that one can just keep edges of the form $$$(u, v)$$$ where $$$u$$$ is in $$$S$$$ and $$$v$$$ isn't. From here, I think we can just run an MST algorithm on the graph $$$G'$$$, but I'm not entirely sure if this is correct.

Thanks

Given M one-by-one tiles and N two-by-two tiles, what's the largest side-length of a square that you can make if the square must be completely filled in the middle?

I was recently asked this problem in an interview, and I came up with an incorrect dynamic programming approach. I did some sort of three-state DP with (m, n, k), where k is the current square side-length. From (m, n, k), we can transition to a state with k' = k + 1 by using some number of one-by-one tiles (around the border of the current square with side-length k), and we can transition to a state with k' = k + 2 by using some number of two-by-two tiles.

However, this is clearly not exhaustive: It doesn't take into account when we can use a combination of both tiles.

I think this might be purely a combinatorial problem. Could someone please help me with the right approach? Even after thinking for a few more days, I can't come up with a solution.

Given a circular array of N integers (i.e. A[0] and A[N — 1] are adjacent to each other), what's the maximum number of adjacent pairs that you can form whose sum are even? Note that each element can belong to at most one pair.

This is a recent problem that I encountered, but my approach is wrong. I know that the sum of two numbers of the same parity produce an even sum (so odd and odd, or even and even), but the whole "wrap-around" part is what's getting me. In particular, I can't figure out whether or not it's optimal to pair a value with its left neighbor or its right neighbor. The current algorithm I'm thinking of is as follows:

• For each index 0 <= i <= n — 1, try to pair A[i] with A[i + 1] by checking their parity.

• If both A[0] and A[n — 1] are unpaired at the end, pair them if they have the same parity.

This is a wrong algorithm since it fails for [1, 1, 1, 0, 1] in which case it's optimal to pair A[0] with A[n — 1] and A[1] with A[2]. Does anyone have any suggestions?

Thanks.

Hi everyone,

I am pretty new to dynamic programming, and I have been struggling with the following problem:

Given an array of integers, how can I find the longest contiguous arithmetic subsequence? For instance, if our entries are 10, 3, 5, 7, 9, 11, 5, 8, 7, 13, 14, then I would have to return "5" since 3, 5, 7, 9, 11 forms the longest contiguous arithmetic subsequence.

I thought about defining dp[i][j] to be the longest contiguous arithmetic subsequence ending at index i with common difference equal to j, but I can't really come up with the transitions properly.

I would really appreciate it if someone could please help me with this problem.

I'm pretty new to graph theory; I'm learning about BFS and DFS, and I came across the following problem:

Given an undirected graph $$$G = (V, E)$$$, how can I compute for each vertex $$$u$$$ the number of vertices $$$v$$$ such that $$$d(u, v) = 2?$$$

Of course, one could just perform a BFS from each vertex and count the number of vertices for which the distance is equal to $$$2$$$, but I was wondering whether there is any better solution to this problem. Does anyone have any ideas?

Hi everyone,

I've been learning a lot of graph theory lately, and I've come across the following question, which I am having trouble with:

Suppose you are given a directed acyclic graph $$$G = (V, E)$$$ in which each vertex is colored one of two colors. You are also given two vertices $$$u$$$ and $$$v$$$ in the graph. How can I determine whether there is a path from $$$u$$$ to $$$v$$$ consisting of only one color (each intermediate vertex other than $$$u$$$ and $$$v$$$ are required to have the same color, the colors of $$$u$$$ and $$$v$$$) don't matter.

I thought about applying topological sort since it's a DAG, but then I don't really know how to proceed. Can someone please help me?

Hey everyone,

I recently learned about basic graph theory (BFS/DFS), and I would like to know approaches to the following two problems. I will discuss my thoughts after I present the problems.

1) Given an undirected graph $$$G = (V, E)$$$ whose $$$V$$$ vertices are colored with at most $$$V$$$ distinct colors, how can I determine whether there exist two vertices $$$u$$$ and $$$v$$$ with $$$d(u, v) \leq 2$$$ such that the color of $$$u$$$ is equal to the color of $$$v$$$?

This problem seems really similar to the bipartite coloring problem, but the key differences are that we're allowed to use up to $$$n$$$ colors, and we need to make sure that no two vertices have the same color within a distance of two. I thought about this problem for a while, and I couldn't come up with too much. I thought about somehow "augmenting" each node with the colors of its adjacent vertices, but I couldn't really get much from there. I'm not sure if this is the right direction or not.

2) Given a DAG $$$G = (V, E)$$$ with each vertex colored with colors $$$1$$$, $$$2$$$, or $$$3$$$, how can I find the set of all vertices colored $$$1$$$ that are reachable from both a vertex with color $$$2$$$ AND a vertex with color $$$3$$$?

So when I see DAG, I usually think of topological sort. But I really can't get anywhere with this problem. I thought about reversing the edges and performing a depth-first search from each of the vertices colored $$$1$$$, but this would be $$$O(V(V + E))$$$ in the worst case, and I'm pretty sure we can do better.

Could someone please help me with these graph theory problems? Thank you

Hi,

Today, I worked on the following problem: https://onlinejudge.org/external/113/11396.pdf (UVa 11396)

While I recognized that the problem involved bipartite graphs, I could not figure out how to solve the problem, so I looked at the answer. Accordingly, I found out that a graph $$$G$$$ can be decomposed into $$$K_{1, 3}$$$ graphs if $$$G$$$ is bipartite. While this solves the problem, I'm not so sure why this is true.

I understand that each of the $$$K_{1, 3}$$$ graphs can have their center vertex colored black leaving the remaining three vertices to be colored white; however, I can't really figure out where the "each vertex has degree $$$3$$$," and "decomposition" (the graph can have many $$$K_{1, 3}$$$'s in them) parts come into play.

I've tried drawing pictures, but I can't seem to get the intuition that a bipartite graph check is enough. It's also pretty hard for me to come up with examples in which the criteria are satisfied and a decomposition is possible. I'm not so sure if my examples are valid either (the term "graph decomposition" is new to me). Here's an example that I came up with that I believe is valid (it can be decomposed into three $$$K_{1, 3}$$$'s; the three centers are $$$0$$$, $$$4$$$, and $$$5$$$). I am familiar with basic bipartite graph theorems (e.g. bipartite if and only if no odd cycle), but those don't seem to help me here either.

Can someone please help convince me that a bipartite graph check is enough? I don't understand the intuition behind this solution, and I cannot find much reasoning online. There are hints/solutions provided here, but they do not help me very much. I would really appreciate any help.

Does anyone know how I can solve this problem? Unfortunately, I can't find any editorials/solutions online, and I've been stuck on this problem for some time now :).

I've tried using BigInteger, etc in Java, with no luck. So I would love to see how someone else has done it.

Here's the problem: https://www.spoj.com/problems/PIB/

This was a question I was asked in a programming contest at a local college, which I was not able to solve. I was wondering whether anyone knows the way to solve it:

Given a string S consisting only of binary digits (e.g. we can have S = "10101"), what's the minimum number of operations you need to perform to get from S to 0? There are two valid operations that can be performed:

1) Divide by 2 2) Subtract by 1.

For example, if the string S is "011100," which has decimal representation 28, then you can go 28->14->7->6->3->2->1->0, which requires 7 operations. Since this is optimal, the answer is 7.

I tried implementing the greedy solution, which does not work. A very similar problem is here: https://stackoverflow.com/questions/39588554/minimum-number-of-steps-to-reduce-number-to-1

The number that S was representing would be at most 1,000,000, which means that S has around 20 digits max. Maybe there's an even quicker way to do it, without converting it to an integer first?

However, I was only given the binary representation of the number as a string, and I wasn't given the number itself. So I don't quite think that the technique described in the post is enough.

Also, I have to reduce to 0, whereas the post wanted to reduce to 1. I would greatly appreciate some help. As of now, I think the problem might require dynamic programming, which I am not so great with.

I thought of this problem after encountering a similar problem in TopCoder (many months ago — I can't find the problem anymore; if someone happens to find the problem, please let me know!), and I was wondering whether anyone has an efficient solution to it:

Given an integer N, find two positive integers A and B such that 1) A + B = N

2) Neither A nor B contain a "0" in them.

For example, if N = 12, you could return (7, 5) or (6, 6) or (4, 8), etc. But you wouldn't be able to return (10, 2).

At first thought, I was trying to just set A := N — 1 and B = 1, and decrement/increment A and B until neither had a "0" in them. But for really large cases, something like N = 1099999999999, this can take a really really large time. So then I tried checking each digit and adding 10^(k). But it gets really messy. I was wondering whether there is a nice and efficient solution to this problem, or if the best way is the way I described.

Given an array A = [a1, a2, ..., an] and another array B, where B is some permutation of the numbers 1, 2, ... n, how can I order the elements of A according to the permutation B in-place (so you cannot make an extra array)?

For example, if A = [27, 15, 11, 19] and B = [3, 2, 4, 1], then we would have to modify A to get [19, 15, 27, 1].

This problem seems really easy at first, but I thought it was quite difficult with the memory constraint. I wasn't able to solve this problem, but I was wondering whether someone else would be able to show me how to solve it.

Given a set of nodes numbered 1, 2, .. N, and a list of edges, we define an "operation" as removing an existing edge between two vertices and placing it between two other vertices. What is the minimum number of operations needed to connect the graph?

We are given the number of vertices and edges as input, and then we are given the list of edges.

For instance, if there are 2 vertices and 1 edge, and the one edge is (1, 2), then you don't need any operations since you're already done.

On the other hand, if there are 4 vertices and the edges are (1, 2), (1, 3), and (2, 3), then 4 isn't connected, but you can remove any edge and connect it to get 4 with just one operation. So the output is 1.

How can I solve this problem?

I am thinking about finding the number of connected components, and going from there, but I have not been able to make any progress. I am really bad at graph implementations though, and I would really appreciate some sort of help.

Suppose you want to construct sequences from the restricted alphabet {1, 2, 3, 4, 5, 6}. However, you cannot place the number i (i = 1, 2, 3, ... 6) more than A[i] times consecutively, where A is a given array. Given the sequence length 1 <= N <= 10^5 and the array A with 1 <= A[i] <= 50, how many possible sequences are possible?

For example, suppose A = {1, 2, 1, 2, 1, 2} and N = 2. In this case, there can only be one consecutive 1, two consecutive 2's, one consecutive 3, etc. So in this example, something like "11" would be invalid, but something like "12" or "22" would be valid. It turns out that there are actually 33 possible sequences in this case (namely, two-digit sequence except for "11", "33", and "55").

I was wondering how I can solve this problem? Initially, I tried to use a DP approach, but I have been thinking there might be a clever combinatoric strategy. Like, in the example I showed above, it's pretty quick to just do complementary counting. It gets really messy when I try to work it out for larger cases though. I've also tried to use inclusion-exclusion and got nowhere.

Another thing I noted is that A[i] is pretty small, but I wasn't able to get anywhere with that observation.

I would greatly appreciate some help in solving this problem. It might just be a really easy combinatorics problem. I am really bad at that topic, so I wouldn't be surprised if is just something I am not seeing.

Thanks.

Given an integer 1 <= N <= 100, and 1 <= MIN, MAX <= 10^5, how can I compute the number of ordered pairs (a_1, a_2, ..., a_N) such that MIN <= a_i <= MAX for any i, and gcd(a_1, a_i) = 1 for any i not equal to 1?

For example, when N = 3, MIN = 2, and MAX = 4, the valid configurations are (2,3,3), (3, 2, 2), (3, 4, 2), (3, 4, 4), (4, 3, 3), and (3, 2, 4), so the output should be "6".

I am pretty sure (not 100%) this is a DP problem, but I can't manage to come up with the solution. Also, obviously, every configuration with the first number prime is valid, but this doesn't have to be the case. Does anyone have any ideas? I have been stuck on this problem for a few days now. Maybe I'm going about it wrong, and there is a really simple solution? Print the answer modulo 10^9 + 7.

Side-note: Is it possible to get TeX to work in these blogs?

I am using one-based indexing when I discuss this problem, not zero-based indexing.

Suppose you are given two arrays, A and LOC, both of length n.

The array A contains elements in an order that is not necessarily sorted. For instance, we can have A = {40, 80, 30, 60, 10, 70, 20, 50}.

On the other hand, LOC[i] represents the index of the ith smallest element of A. In this case, we'd have LOC = {5, 7, 3, 1, 8, 4, 6, 2}. For instance, LOC[1] = 5. This means that 5 is the index of the 1st smallest element (which is true because A[5] = 10, and 10 is the smallest element).

PROBLEM: Given the array A and LOC, construct a new array ANS such that ANS[i] is the rank of the ith element in A. You may not modify the original array ANS, and you can only use an extra n bits along with a constant amount of memory (that is, you can only use n + O(log n) extra bits of memory). The answer you return must be LOC modified. So you cannot create a new array ANS to return the value. It needs to be in-place.

For our example, we are given A = {40, 80, 30, 60, 10, 70, 20, 50} and LOC = {5, 7, 3, 1, 8, 4, 6, 2}. The expected output would be ANS = {4, 8, 3, 6, 1, 7, 2, 5}. For example, ANS[2] is the rank of the 2nd element in ANS. The 2nd element in ANS is 80 (which is the max value), so it has rank 8.

This problem can supposedly be solved in linear time, but I can only come up with the bruteforce n^2 algorithm. What am I missing? How can this be done?

Thanks