Hey, I'm given a set $$$S = {a_1, a_2, \dots, a_n}$$$ of integers $$$a_i \leq 10^{5}$$$. I'm also given an integer $$$10^9 \leq W \leq 10^15$$$. I need to tell whether there is an unbounded subset with sum $$$W$$$ (by unbounded I mean that we can use e.g. $$$a_1$$$ few times). The best algorithm I know works in $$$O(nW)$$$ which is obviously too slow. Do you happen to know any algorithm which can solve this problem (maybe randomized one or sth?). Thanks in advance!

Hey! Recently, I have tried 1500B - Two chandeliers and after few hours I gave up and opened the editorial. The problem is, I don't quite understand author's solution. I have 3 questions about it.

• Why in the second congruence, there is $$$y$$$ instead of $$$x$$$?

• What is the point of finding the number of solutions to that pair of congruences? How does it correlate with number of $$$a_i \neq b_i$$$ in prefix of size $$$x$$$?

• The problem states that all $$$a_i$$$ are different (same goes for all $$$b_i$$$). Why does it matter?

Thanks in advance!

Hey, I have a problem and I cannot think of any faster soltuion than $$$O(nm)$$$.

I'm given a tree with $$$n$$$ vertices and $$$n-1$$$ undirected edges. I'm also given $$$m$$$ queries ($$$m \le 10^5$$$) and each of them is an integer $$$x$$$ ($$$1 \le \lvert x \rvert \le n$$$). If $$$x > 0$$$ then we need to remove vertex $$$x$$$ from a tree and print number of connected components in that tree, otherwise if $$$x < 0$$$ then we need to add vertex $$$x$$$ to that tree (and also print number of connected components). Input data is correct i.e. no vertex will be added before it was removed.

What I thought of, was storing degree of each vertex. Then, if vertex $$$v$$$ was removed then number of connected components increases by $$$deg(v)-1$$$, but this way we also need to decrement by one degrees of vertices with edge with $$$v$$$ which can take $$$O(n)$$$ and that leads to $$$O(nm)$$$. Another idea, was to try to solve the problem using dynamic connectivity, but I'm not sure how to connect that problem to mine.

Thanks in advance!