Auto comment: topic has been updated by Polyn0mial (previous revision, new revision, compare).

Auto comment: topic has been updated by Polyn0mial (previous revision, new revision, compare).

It worked! Finally! Thank you for your help!

Not sure how. If we only do the middle ones, what will be the final answer? Some of the $$$\text{full_mask}$$$ could be starting from some nodes that isn't directly connected to node $$$1$$$.

Sorting is only $$$O(N \cdot 2^N)$$$ which is way smaller than $$$O(2^N \cdot N^2)$$$. Also, only do dp on the middle nodes like this $$$dp[\text{first_node}][\text{visited_nodes}][\text{ending_node}]$$$ ? However it requires $$$O(2^N \cdot N^2)$$$ memory which is too much.

Is it because bottom-up approach checked to many unimportant states?

Auto comment: topic has been updated by Polyn0mial (previous revision, new revision, compare).

Thank you! I somehow thought that I'm doing prefix sums on mobius and use int instead of long long since mobius only has -1, 0, 1 and won't overflow.

That make sense. Thanks for pointing that out!

Thanks! That's exactly what I'm missing.

In the editorial of problem G, "If Vertex 0 has other vertices, and if the next smallest vertex is Vertex $$$A_k$$$, then Vertices are descendants of $$$A_l$$$, in which there are $$$dp[l+1][k]$$$ ways to do so; on the other hand, there are $$$dp[k][r]$$$ possible trees as a result of removing Vertex $$$A_l$$$ and its descendants."

What does "next smallest vertex" means? Also I don't understand the part $$$dp[l + 1][k] * dp[k][r]$$$. Isn't it suppose to be $$$dp[l + 1][k] * dp[k][r]$$$?

I have hard time understanding the editorial for problem B. Can somebody explain?

It is strange that stress test didn't find this bug.

function run_stress_test() {
	# $1 : gen
	# $2 : brute
	# $3 : sol
	# $4 : starting test case id
	make $1
	make $2
	make $3
	for((i = $4; ; ++i)); do
		./$1 $i > debug_in
		./$3 < debug_in > my_out
		./$2 < debug_in > ans_out
		diff -Z my_out ans_out || break
		echo -e "\033[1;32mPassed test:" $i "\033[m"
	done
	echo -ne '\007'
	echo -e "\033[1;45mWA on the following test\033[m"
	echo -e "\033[0;46mInput\033[m"
	cat debug_in
	echo ""
	echo -e "\033[1;41mYour answer\033[m"
	cat my_out
	echo ""
	echo -e "\033[1;42mCorrect answer\033[m"
	cat ans_out
}

Thanks. That's a stupid mistake made by me. It worked.