We will hold Denso Create Programming Contest 2023 (AtCoder Beginner Contest 309).
- Contest URL: https://atcoder.jp/contests/abc309
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230708T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer: PCTprobability, m_99, evima
- Tester: yuto1115, kyopro_friends
- Rated range: ~ 1999
- The point values will be 100-200-350-400-425-525-575-650.
We are looking forward to your participation!
Yet another Well-known-in-China problem ... Well, perhaps not so well-known regarding the number of submissions, but the idea was probably pretty well-known.
I have no words to describe how bad the statement of problem C was. Is it so hard adding at least a small diagram which explains what is going on?
The statement was short and simple according to me. I didn't feel like anything else was needed.
I dont know maybe its just me but I found it quite confusing. What wasn't clear to me is that the whole lifecycle of a medicine starts always at day 1, I thought for 1 hour that it starts on day "i" so it didn't make any sense the output explanation. In my opinion this fact should have been stressed way better.
What is wrong in this submission of problem F?
Could someone help me in G ? I can't get the editorial's explanation
Here is my non inclusion-exclusion solution.
Suppose you have $$$N$$$ balls arranged in the top row and $$$N$$$ boxes arranged in the bottom row. Now you need to put $$$i$$$-th ball in $$$P_i$$$-th box such that $$$|P_i-i| \geq X$$$.
So you can have $$$dp$$$ such that $$$dp[i][l][r][mask_1][mask_2]$$$ denotes the number of ways to distribute the first $$$i$$$ balls into first $$$i$$$ boxes such that
Now for index $$$i+1$$$,
After each transition, you update $$$l$$$, $$$r$$$, $$$mask_1$$$ and $$$mask_2$$$
So finally your answer is $$$dp[n][0][0][0][0]$$$
Time complexity is $$$O(N^3 \cdot 4^X)$$$, with low constant factor.
You can also note that $$$|l - r| < X$$$ must be true, which helps you reduce the time complexity to $$$O(N^2 \cdot X \cdot 4^X)$$$.
Keeping $$$l$$$ in the state seems to be redundant, since the number of balls that haven't been placed is equal to the number of empty boxes.
Assuming a bit is set in $$$mask_1$$$ when the box is empty, and in $$$mask_2$$$ when the ball is yet to be placed:
$$$l = \text{popcount}(mask2) + r - \text{popcount}(mask1)$$$
This reduces the complexity to $$$O(N^2 \cdot 4^X)$$$. (Code)
In your Code why l is going till i-1 and not till i-x+1 as maximum number of empty boxes in range[1 , i-X+1] can be i-X+1.Can you please explain.
It seems, it is possible to solve $$$G$$$ using OEIS, and additionally write bruteforce to see, where to look on the site. For $$$X = 5$$$ an element of sequence depends on $$$43$$$ previous though.
Yes, I did think of this way during contest, but could not figure out how to determine the recurrences since bruteforcing 43! (I thought 20 would be sufficient since for X = 3 it depended on previous 5 terms) permutations wasn't feasible. How exactly are you determining the recurrences ?
https://oeis.org/A183244
Enjoyed solving G.
Could you share your approach? I am not getting the editorial's solution.
My approach is same as the editorial. We are calulating the unban permuatations such that atleast $$$y$$$ indexes satisfy the condition $$$abs(P_i - i) < X$$$ for which we can do simple $$$dp[currentIndex][indexesTaken][maskOfIndexesTakenIn$$$ $$$(i - x + 1,i + x - 1)]$$$. For the remaining indexes we can just multiply it by $$$fact[n - y]$$$. After calculating we can just do inclusion exclusion and add our $$$answer * (-1) ^ y$$$ to the $$$final answer$$$.
Code
Why this solution for F gives WA for 3 tests Link...
Implementing Problem D exactly as Editorial, still gives WA for 10 testcases. Any idea what is wrong with this?
`
Your solution fails when $$$n_1 = 1$$$ or $$$n_2 = 1$$$ or both. Your
max1
(ormax2
) variable will be equal toInteger.MIN_VALUE
sincemax
in your BFS will never get updated.What is the "method of mirror images" in the editorial of H? Why can't we use the initial dp[i][j](=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]) with some poly techniques instead of mirroring? Thanks.
That's because of dp[i][0] and dp[i][M+1], which should be $$$0$$$. If you naively use polynomials, for example dp[i][0] gets (kinda) dp[i-1][-1]+dp[i-1][0]+dp[i-1][1], which does not evaluates to $$$0$$$, eventually destroying the whole polyonimal.
Can someone please explain how to build segment tree in F??
I have thought till the part of sorting the tuples and all but being a beginner at segment tree, I am unable to understand the editorial
Maybe some example would help
Assume that the boxes are already sorted by $$$h$$$ :
Consider we are now evaluating box 4. Now we want to check whether there's a box can be fit inside box 4
By using the example above, we can see that box 3 can fits in the box 4
How to do that?
For each of the width, store the minimum depth of a box having that width. Let's store it in an array named $$$X$$$
So in the example above, this array $$$X$$$ will look like this :
We can now see thst when we evaluate box 4 (which has the width of 5), it's the same of finding minimum of $$$(X_1, X_2, X_3, X_4)$$$
Then we check whether the minimum values is less than box 4's depth. If it is, then we can conclude that there's a box can be fit inside box 4
And since we're gonna updating the $$$X$$$ values each time we evaluate new box and we can also need to find the minimum values of that array, then this task can be solved with segment tree
Yeahhh, I got you.
Thanks bro.
Oh I forgot to mention that :
Initially all $$$X$$$'s value should be an arbitrarily large value so it won't be considered as minimum (the
0
I write in the example above is just for the better visualization)Since the dimension of the box can reach $$$10^9$$$, make sure to have them compressed so it can be used as $$$X$$$'s indices
yeah I figured and was trying to write up the code
Can someone plz tell why the ratings are not updated yet??
++ I have checked several times for the same.
unrated beginner contest?
no, please no :(
Just updated now!
yepp!! Gained 110 :)
congrats bro!
Any Hints for F?
SegmentTree
I'm trying to solve F with a 2D fenwick tree.
First, rotate all the boxes to make $$$h_i\le w_i\le d_i$$$.
Then sort in ascending order of $$$h_i$$$. Do a compression on the second and third dimensions to make $$$1\le w_i, d_i\le N$$$.
For every $$$i$$$, first check the prefix sum of $$$(w_i-1, d_i-1)$$$. If the value is not zero, there must be at least one index $$$j<i$$$ such that $$$h_j<h_i$$$, $$$w_j<w_i$$$ and $$$d_j<d_i$$$ so we can print
Yes
(since we have sorted the boxes in ascending order of $$$h_i$$$, there is no need to check if $$$h_j<h_i$$$). Then update the fenwick tree to make $$$(w_i, d_i)=1$$$.A typical implementation requires $$$\mathcal O(N^2)$$$ memory, but most of the $$$N\times N$$$ tree is always $$$0$$$, so we can reduce it to $$$\mathcal O(N\log^2 N)$$$ with a hash table (
unordered_map
).The overall time complexity is $$$\mathcal O(N\log^2 N)$$$, which is expected to pass the task. But it got TLE on 11 of 64 cases. Why is that happening? my submission
I'm not sure if this is the reason, but
unordered_map
has a big constant factor which is slowing your code down quite a lot. $$$O(n \log^2 n)$$$ is already quite heavy and it's not that surprising that significantly increasing the constant factor TLE's.Use gp_hash_table or some custom made faster hashtable.
Submission after editing.
Thanks!
Also, I found that using gp_hash_table without a custom hash can do the trick: submission
Alternative solution for E: Do a DFS, and keep a tag on how many generations of the most "promising" (i.e. it has the most generations currently available) are left to be used. When traversed to a certain node, attempt to use that node's insurance plan as the most "promising" one. This works because we only care about whether someone is insured, not how many insurances that cover them. Code