Dec0Dedd's blog

By Dec0Dedd, history, 2 years ago,

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!

• 0

By Dec0Dedd, history, 3 years ago,

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?

• 0

By Dec0Dedd, history, 3 years ago,

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.