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.
Why after LogN? while working on it, i did realize that we will reach a point after which the array will be [N,N,N,N....], but why is it LogN?
Edit: The editorial is out. Thanks for replying.
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?
Is there any Youtube channel for video editorials of Atcoder contests?
Yes, there is but editorials only in Japanese.Atcoder
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
can someone help me solve problem b with help of binary search here is problem link: https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b
If Anyone is stuck like me in C here is a detail explanation (maybe helpful to someone) In this link