New answers tagged

2

This problem is equivalent to the bipartite b-matching problem on complete bipartite graphs, where you get a complete bipartite graph $G = (V, E)$ as input and an integral function $b : V \rightarrow \mathbb{N}$ that assigns an integer to each vertex. The goal is to find a subset of the edges $S \subseteq E$ such that $S \cap \delta(v) = b(v)$ for all $v\in ...


3

This problem is not easy. The popular website GeeksforGeeks gives an answer that returns the wrong answer, "YES" when row sums are $ [3, 3, 3, 1]$ and column sums are $[4, 4, 1, 1]$. How can we find a set of necessary and sufficient conditions that is easy to compute? How can we produce a wanted matrix if the conditions are satisfied? One easy ...


1

To answer your question: I am not really sure what is the goal behind the question? If I were to give this assignment to my students, I would expect An algorithm in pseudo code Running time analysis Proof of correctness You have given neither. It is always risky to handwave an algorithm, because you always cherry-pick data structures and details when you ...


0

This follows almost immediately from the definition of expectation, when we sample the actions with the distribution that $\pi_t$ (the bandit) defines, and the inherent randomness of the model. First, let us make sure we use the same terminology: $\pi_t(x)$ is the probability that the bandit chose action $x\in\text{Actions}$ $R(x,r)$ will be the probability ...


1

Your solution is not optimal. Take for example, the following list of weights: $[1,4,3,2]$. In this example, your algorithm will place only $1$ in the bins, whilst a different solution could place $4,3$ and $2$ instead (which is obviously a better solution). However, you can create a dynamic programming solution for this problem: Consider the graph $G$, with ...


Top 50 recent answers are included