We will hold AtCoder Beginner Contest 245.
- Contest URL: https://atcoder.jp/contests/abc245
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20220326T2100&p1=248
- Duration: 100 minutes
- Number of Tasks: 8
- Writer:leaf1415,PCTprobability, YoshikaMiyafuji,m_99,penguinman
- Tester:Nyaan, kyopro_friends
- Rated range: ~ 1999
- The point values will be 100-200-300-400-500-500-600-600.
We are looking forward to your participation!
Who didn't copy-paste D?
from where?
I didnt solve it and I assumed ppl copy-pasted it because it felt impl-heavy
I didn't think it was impl-heavy. Notice you can determine the coefficient of $$$B_i, 0 \leq i \leq m$$$ from
C[i] / A[0];Nice solution, i was stupid lol
I spent only 6 mins on F, but struggled to solve problem D, like when you get WA on pretest 2 on div2A.
anybody else did dp on reversed compressed scc graph in F?
I did lol.
I did node coloring. (white unprocessed, grey in-process, black processed)
A cycle is detected if a grey node is visited before being colored black.
I did remove leafs until there are not more leafs. All remaining vertex lead into circles.
Me too
how to solve c ?
I used multi-source BFS. It could have been done by DP as well.
Maintain the max two numbers the previous position x[] can have. First element can be a[0] or b[0] Then iterate x[], and foreach position check if you can use a[i] or b[i], taking into account which values on the previous position where possible.
You end up with 0, 1 or 2 possible values for the last position. If 0, then ans=No.
How to solve H?
I tried FFT on D but failed. Is it precision error? Submission Anyway I got AC with a naive approach. There's no way a problem D in ABC would need FFT.
My solution to D with NTT: Link
Is there a way to extract the index of the min value of an array in a range in O(log(n)) rather that just the value? (with segment tree or otherwise — I am not very comfortable with seg tree yet)
I needed that to solve E.
You can make from each element a pair<value,index>, then sort this. First element in this list is min value, and has its index next to it.
No I mean dynamically. I have to change the value of elems to 'delete' them by assigning to a large val then keep querying for the min in a range.
Not sure how exactly that works.
In E, I maintained a multiset of witdhts of chocklates that fit into some with of a box.
Then iterated the boxes sorted by length, and putting all chocklates that fit into the box by length into above multiset.
Then take one choclate out of the multiset, and put it into the current box. For this, we choose the choclate from the multiset with the biggest with. (which is first if putting negative with into the multiset)
I use Python so I guess multiset wasn't an option for me. I'll have to learn C++ too it seems.
Thanks anyway.
Note that if we sorted boxes and chocolates in ascending order of their widths then their lengths, and started processing boxes one by one in ascending order, we can find that among the first chocolates that have widths $$$\le$$$ the current box it is best to assign the chocolate having the maximum length that can fit into the current box (if exists).
The reason is that all those chocolates will fit into the next boxes in terms of width, so the idea is to choose the one that will increase our chance of succeeding later in terms of length by getting rid of the maximum we can choose.
A multiset with upper/lower bound operations is sufficient here, where we can maintain a pointer for chocolates and when we move to the next box keep incrementing the chocolates pointer while adding the respective chocolate lengths to the multiset until we either reach a length greater than the current box or exceed the $$$n$$$ boundary.
Thank you.
the editorial sorts the overall list of boxes and chocolates in descending order of (width, length) but the argument looked similar .
Is there any name for such greedy proof's ?
Nvm
Can anyone help me with the question polynomial division for this contest ? The question was fairly easy don't know why I am getting RE as a verdict although there doesn't seem to be any .Here's my code CODE LINK . Thanks in advance.
If A0=0 you divide by 0 I think.
In the question it is given that A0 is not zero.Check the question .
That's An not A0. A0 is the constant term.
" Here, each coefficient of A(x) and B(x) is an integer whose absolute value is at most 100, and the leading coefficients are not 0. " It's stated the coefficients are not 0 , sorry I didn't get it.
Leading coefficients just mean An and Bm not every coefficient.
okay, thanks for the clarification, language for the problem should have been better, although it did strike to me that it was written "leading coefficients" instead of "coefficients" anyway thanks for your help.
Yes , I had seen that , it's just that I thought every coefficient is greater than 0 so I wrote the code with A[0] because you see it was written leading coefficients which misled me . Thanks anyway .
Can check out my video editorials of D,E and F if you have any doubt
plz also upload of D
Yes I will upload Edit: D uploaded
I think Problem E is a very nice practice for greedy algorithm, where you should choose different strategies of sorting at different stages.
At first sight of problem F, I realized that the well known algorithm of finding out all strongly connected components should work, but made some small mistakes during the implementation, and finally got accepted within the last 5 minutes.
In my opinion, problem E and F are really great for my level. I have a big chance to solve them, but still not that easy. Thanks again to the problem writers.
I completely agree. Combined with the short statements, i always learn something new from ABC, especially D/E/F
How to solve Problem G?
For H, why the answer for M equal to the product of F(pi, qi, K, N)?