### chokudai's blog

By chokudai, history, 3 months ago,

We will hold AtCoder Beginner Contest 245.

We are looking forward to your participation!

• +40

 » 3 months ago, # |   0 Who didn't copy-paste D?
•  » » 3 months ago, # ^ |   0 from where?
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -6 I didnt solve it and I assumed ppl copy-pasted it because it felt impl-heavy
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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]; Spoilerint main() { fast; cin >> n >> m; vi A(n+1); FOR(n+1) cin >> A[i]; reverse(all(A)); vi C(n+m+1); FOR(n+m+1) cin >> C[i]; reverse(all(C)); vi B(m+1); FOR(m+1) { int times = C[i] / A[0]; B[i] = times; FOR(j, n+1) C[i+j] -= A[j] * times; debug() << im(C); } reverse(all(B)); EACH(x, B) cout << x << " "; } 
•  » » » » » 3 months ago, # ^ |   0 Nice solution, i was stupid lol
 » 3 months ago, # | ← Rev. 3 →   -7 I spent only 6 mins on F, but struggled to solve problem D, like when you get WA on pretest 2 on div2A. Spoiler
 » 3 months ago, # |   +29 anybody else did dp on reversed compressed scc graph in F?
•  » » 3 months ago, # ^ |   0 I did lol.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 3 months ago, # ^ |   +13 I did remove leafs until there are not more leafs. All remaining vertex lead into circles.
•  » » 3 months ago, # ^ |   0 Me too
 » 3 months ago, # |   0 how to solve c ?
•  » » 3 months ago, # ^ |   0 I used multi-source BFS. It could have been done by DP as well.
•  » » 3 months ago, # ^ |   0 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.
•  » » » 3 months ago, # ^ |   0 thanks
 » 3 months ago, # |   0 How to solve H?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 even tourist couldn't solve it on time..
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 My solution to D with NTT: Link
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 You can make from each element a pair, then sort this. First element in this list is min value, and has its index next to it.
•  » » » 3 months ago, # ^ |   0 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.
•  » » » » 3 months ago, # ^ |   +4 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)
•  » » » » » 3 months ago, # ^ |   0 I use Python so I guess multiset wasn't an option for me. I'll have to learn C++ too it seems.Thanks anyway.
•  » » 3 months ago, # ^ | ← Rev. 3 →   +8 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.
•  » » » 3 months ago, # ^ |   0 Thank you.
•  » » » 3 months ago, # ^ |   0 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 ?
 » 3 months ago, # |   0 can any body tell my mistake in problem D? Only 1 testcase failed while all other worked submission
•  » » 3 months ago, # ^ |   0 Input3 0 4 4 1 3 3 3  Expected OutputYes  Your OutputNo  CommentYou can choose $X = B$
•  » » » 3 months ago, # ^ |   0 Thanks a lot sir
 » 3 months ago, # | ← Rev. 3 →   +8 Nvm
 » 3 months ago, # |   0 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.
•  » » 3 months ago, # ^ |   0 If A0=0 you divide by 0 I think.
•  » » » 3 months ago, # ^ |   +3 In the question it is given that A0 is not zero.Check the question .
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 That's An not A0. A0 is the constant term.
•  » » » » » 3 months ago, # ^ |   +3 " 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.
•  » » » » » » 3 months ago, # ^ |   0 Leading coefficients just mean An and Bm not every coefficient.
•  » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » » » 3 months ago, # ^ |   0
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 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 .
 » 3 months ago, # | ← Rev. 2 →   +15 Can check out my video editorials of D,E and F if you have any doubt
•  » » 3 months ago, # ^ |   0 plz also upload of D
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 Yes I will upload Edit: D uploaded
 » 3 months ago, # |   +14 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.
•  » » 3 months ago, # ^ |   +3 I completely agree. Combined with the short statements, i always learn something new from ABC, especially D/E/F
 » 3 months ago, # | ← Rev. 2 →   0 my code for E is failing 7 test cases , could anyone give me a test case where it is failing or point out what's wrong with my code code linkedit : please don't mind this comment i found my mistake
 » 3 months ago, # |   0 How to solve Problem G?
 » 3 months ago, # |   0 I want to ask after_contest_001.txt on C.I use DisjointSet to detect the connection about whether is there a path from left to right ?here is my submission
•  » » 3 months ago, # ^ |   0 4 1 100 99 96 95 1 97 98 2I made a mistake on connection and DP, directed graphthe pic
 » 7 weeks ago, # |   0 For H, why the answer for M equal to the product of F(pi, qi, K, N)?