We will hold Tokio Marine & Nichido Fire Insurance Programming Contest 2020.
- Contest URL: https://atcoder.jp/contests/tokiomarine2020
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200613T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: yutaka1999
- Rated range: ~ 2799
The point values will be 100-200-500-700-800-1000.
We are looking forward to your participation!
How to Solve D?
Meet in the middle. Naive dp for the top 9 levels of the binary tree. If a query vertex has depth $$$\le 9$$$, we're done. Otherwise, brute force all $$$2^{9}$$$ subsets of the last $$$9$$$ ancestors and read the dp value from the suitable ancestor to get the answer for each query in $$$O(2^{9})$$$.
tl;dr. meet in the middle
Store all the queries in the respective nodes, to answer them offline.
Then run a single dfs on the tree.
While processing a node with height <= 9, compute a dp[height][w] — maximum sum of val with weight=w.
And while processing a node with height > 9, store all its ancestors(including itself) with height > 9, then iterate over all the stored ancestors and check for the maximum val for weight less than L.
My submission
Can someone give me hints for solving C? I came up with the bruteforce but that's obviously TLE
After around LogN operations, the array becomes : [N, N, N, .., N].
Now, it's easy. You could use fenwick tree/prefix sums to compute the array till then.
how do you prove that it won't take more than LogN operations?
I also stuck at that for 2 hours to prove that, it doesnt takes more operations but editorialist have described it nicely.
Intuitively think that's how it works and run the algorithm for maximum N and everything being 0 to confirm it experimentally.
In the editorial of problem E, the second solution mentions that number of ways to choose at least one number with 0 in that bit, or at least one number with 1 in that bit can be computed in $$$O(N + 2^{K}K)$$$ using inclusion-exclusion. How's that?
D knapsack tree, I do not get it.
"Thus, we can try all subsets of the items in the vertices at depth K or deeper in O(2^K) time."
How?
Are the test cases available?
In D, we can solve the problem when $$$L$$$ is large. To achieve that, for each query, we can take the list of all $$$O(2k)$$$ parents, and for each half build the list of all subsets sorted by weight in $$$O(2^k)$$$ (You can do it by merging in linear time sets $$$A$$$ and $$$A+x$$$ for each element $$$x$$$, to get $$$2^0+2^1+\ldots+2^k \to O(2^k)$$$). And then you can get the answer using two pointers.
In E, my sol was $$$O(3^L)$$$, I used the fact that $$$n \leq 50$$$ and inside the inclusion-exclusion maintained the set of all candidates in one long long.
How did you get all subsets sorted by weight in $$$O(2^k)$$$ ? I did exactly same thing, but I needed extra log for sorting subsets — it took me 1 hour to fit in time limit.
You don't need to sort all the subsets. That's what I wrote in my previous comment, let me elaborate it. Add elements $$$1,2, \ldots, i$$$, one by one, and maintain the set $$$A_i$$$ of all subsets sorted by weight. $$$A_{i+1} = (A_i \cup (A_i + x_i))$$$, so to get $$$A_{i+1}$$$ you can merge $$$A_i$$$ and $$$A_i + x_i$$$ in linear time, the total number of operations will be $$$1 + 2 + 4 + \ldots + 2^k \leq 2^{k+1}$$$.
Thanks for explanation, it makes sense!
I solved E in $$$O(3^L \cdot N/64 + NK)$$$. It's dumb inclusion-exclusion.
You don't need these hacks with memory, just calculate the same thing with brute instead of DP...
Check out my submission: link
If Anyone is stuck like me in C here is a detail explanation (maybe helpful to someone) In this link