### maroonrk's blog

By maroonrk, history, 4 weeks ago,

We will hold ACL Contest 2.

The point values will be 300-600-700-900-1300-1900.

The concept of this contest is the same as ACL1, so you may refer to the announcement of ACL1 for more details.

We are looking forward to your participation!

UPD:

We decided to postpone the contest. The new date is not confirmed, but it is likely to be 3rd October.

The reason for this sudden decision is the collision of the problem with today's Japanese contest (problem). This task is almost the same as our E. We thought if we were to hold the contest with current problems, it would favor Japanese competitors too much.

Sorry for the inconvenience; we appreciate your understanding.

UPD2

We regret to inform you that we discussed the issue and concluded that it is hard to hold ACL2. If we replace E with another problem, you can easily deduce from the point values that these 300,500,700,900,1900 pointers do not need FFT, and the other one is likely to require it. We thought this would spoil the contest, and we tried to find a way to avoid this situation. However, we concluded that it's hard to keep going with this problem set. Therefore, we decided to use the tasks in future contests (of course, we will not use them all together).

rng_58 is now preparing a makeshift contest named Junior ACL (or something), which also uses AtCoder library but is much easier than the original ACL contest. This contest is more like yet another ABC and rated for <2000. The contest will be educational for beginners, but please don't expect ad-hoc, original problems (so it won't be interesting for D1 people; however, it may be useful if you want to test the usage of the ACL library). He said he would finish the preparation quickly and hold the contest tomorrow (or today in the Asian timezone), that is, the same time and date as the original ACL2! Watch out for the announcement from him.

Again, we are very sorry about this. We hope to see you in our next 2800 rated round, which will happen next week.

• +202

 » 4 weeks ago, # |   +12 Would this contest be "between ARC and AGC" like the last ACL contest, or at the same difficulty level of a normal ARC?
•  » » 4 weeks ago, # ^ |   +34 The difficulty level is "between ARC and AGC". As you can judge from the point values, we have an unusually hard problem for ARC-rated like ACL1.
•  » » » 4 weeks ago, # ^ |   0 Can u just tell that whether there is any difference b/w ABC or ACL contest other than in difficulty level ? Means whether we have to add some at coder library or what .?Sorry My question can be stupid
 » 4 weeks ago, # |   +32 Why not just hold this as AGC and remove rating upper bound? If the problem point values are consistent across contests, it is not so different from AGC values.
•  » » 4 weeks ago, # ^ |   +59 Well, yes they are difficult problems, but we still feel they're not suitable for AGC. Some may say we can just declare the contest rated if it's difficult enough, but we think there are more aspects to consider.I'm sorry we have too few rated contests for you. I'm planning to hold at least two more AGC this year. I appreciate your patience.
 » 4 weeks ago, # |   0 I think it's a bit odd to ask. What is the difficulty level of the problems ? Can newbies or pupils can solve problems here?I never did an ACL before
•  » » 4 weeks ago, # ^ |   0 If this round will be as hard as the previous ACL, I think this will be too hard for pupils
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 4 weeks ago, # |   0 Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
 » 4 weeks ago, # |   -43 maroonrk Any plans to change profile pic?
 » 4 weeks ago, # |   0 https://atcoder.jp/contests/ablACL Beginner Contest starting soon!
 » 4 weeks ago, # |   0 Now as the contest has finished could anyone please tell me how to solve D — Flat Subsequence
•  » » 4 weeks ago, # ^ |   +1 You will need a data structure to calculate the max of a subsection of the array.This can be done with a segment tree.I referred to this problem and its solution closely https://atcoder.jp/contests/practice2/tasks/practice2_j
•  » » 4 weeks ago, # ^ |   +3 dp with segment tree. Make a segment tree in range 0 to 300000 where in a node i, you would store the position where i appeared last. Now, lets say you are at index i, then you are looking for p = maximum in range(v[i], v[i] + k) and q = maximum in range(v[i — k], v[i]). then, dp[i] = max(dp[p], dp[q]) + 1. Update for v[i] with i after calculating the dp[i]. Ans is maximum of dp[i] over 1 to n. Its easy to realise why it works, its upto you
 » 4 weeks ago, # |   +6 Like last week I implemented everything with segment tree ;) But was not able to solve F. However, here is what I found: EThe decimal value of the whole number is the sum of the single digits, where the single digits are multiplied by $10^{position}$ It is a lazy segment tree range update, where we set the values. The tricky part is, that we need to set a nodes value to its decimal representation, which is calculated as the sum of above furmular. So we need to include that calculation into the push function of the segment tree. Submission DThis can be implemented using a simple segment tree of size 3e5. In the tree we maintain the max length of a subsequence seen so far ending in an element with value of that position.Then we go from left to right throug the list, and foreach element query the tree for the max value in interval $(a[i]-k, a[i]+k)$. And update the position a[i] with that $value+1$. Submission Final answer is max of interval (0,n) CWe can utilize Dsu here. After union of all connected vertices we count the connected components, ans=cnt-1 since we need to connect all those components. Submission A+BA and B where simple as usual. SubmissionA SubmissionB
•  » » 4 weeks ago, # ^ |   0 Hello sir In problem D how are you merging two segments?
•  » » » 4 weeks ago, # ^ |   0 I use max of both values. Since the segment tree maintains the maximum length of sequences seen so far.
•  » » 4 weeks ago, # ^ |   0 can D solved by DP ??
•  » » » 4 weeks ago, # ^ |   0 I did not found a way to solve it with "normal" dp. However, if using a segment tree it is like a dp, only that we maintain the dp-array as a segment tree.
•  » » » » 4 weeks ago, # ^ |   0 can u explain how to use segment tree in this question
•  » » 4 weeks ago, # ^ |   0 I did the same. But got the wrong result. By the way, I felt relieved to know my approach was correct.
•  » » 4 weeks ago, # ^ |   0 Why you have taken aux+k+1 in your submission
•  » » » 4 weeks ago, # ^ |   0 Because that implementation of a segment tree I used there expects the right border to be exclusive, not inclusive.
 » 4 weeks ago, # |   +5 Oh man, come on. What mess you made in lazy segment tree documentation. I need tutorial for the terms in lazy segment tree documentation bro.
•  » » 4 weeks ago, # ^ | ← Rev. 4 →   +5 I added some comments to a submission: https://atcoder.jp/contests/abl/submissions/17053342I try to explain what each parameter of the lazy segtree does. Hopefully it can be useful to understand the library better.
•  » » » 4 weeks ago, # ^ |   0 That's really useful. Thanks a lot
 » 4 weeks ago, # |   0 How to solve D? Is there a way to do with dp I tried but got runtime error while using dp.
 » 4 weeks ago, # |   0 Can someone give any hint or editorial for problem D.
 » 4 weeks ago, # | ← Rev. 4 →   +9 I guess I had a good chance of solving E had I tried reading the docs before the contest... Glad I was not the only one who got stuck on lazysegtree documentation lolStill, really nice practice and nice library, thanks for the contest.
•  » » 4 weeks ago, # ^ |   0 I need tutorial for documentation lol. Freaking mathematical terms
 » 4 weeks ago, # | ← Rev. 2 →   0 What is the meaning/full form of ACL?
•  » » 4 weeks ago, # ^ |   0 Atcoder Libray contest.
•  » » » 4 weeks ago, # ^ |   0 Thank you so much.
 » 4 weeks ago, # |   +17 Anyone care to explain F?
•  » » 4 weeks ago, # ^ |   +46 Let bad pairs be defined as pairs with two equal heights. The idea is you first want to count the number of ways to choose $i$ pairs of people such that they are all bad pairs. If we consider the set of people with the same heights, we can easily compute these number of ways to choose $i$ bad pairs within these groups by counting using the choose function. Then treat the number of ways as stored in a polynomial, where the coefficient of $x^i$ is the number of ways to choose exactly $i$ bad pairs from a group of people in the same height. We multiply all these polynomials, and we get the overall ways to choose $i$ bad pairs for each $i$. We can then use PIE to finish off and compute the final answer. However, this will TLE because we are multiplying a bunch of polynomials in a naive order. To get around this, store a multiset of the polynomials, and multiply the smallest polynomials in degree each time. It can be shown that this will run in $\mathcal O( n \log n)$.Submission link
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 Just adding to above explanation. After finding ways to pick exactly $i$ pairs of same heights, we also need to consider making pairs of remaining $(N-2*i)$ elements irrespective of heights. So we'd need to multiply the coefficient of $x^i$ by $f(2*(N-i), (N-i))$ where $f(N, i) = \frac{N!}{(N-2*i)! * i! * 2^i}$ which'll give us the number of ways to pair all elements such that there are at least $i$ pairs with same height. Then we apply PIE.Submission linkEDIT: I have edited the multiplication factor, thanks Kush.code for pointing it out.
•  » » » » 4 weeks ago, # ^ |   +8 Taran_1407 I don't understand your logic of (N!)/((N-2*i)!*i!*2^i)If we have made i equal pairs then we are left with (N-2*i) heights. Now if we divide these heights into pairs then the number of ways would be (N-2*i)!/(2^((N-2*i)/2)*((N-2*i)/2)!) but then there are equal elements among N-2*i so mine would overcount. could you plz explain
•  » » » » » 4 weeks ago, # ^ |   0 Here's an example.assume i=3, we have (1, 1) (1, 1) (1, 1), 3 pairs of the same height.if we label it as (1, 2) (3, 4) (5, 6), thenwe have 3! = 6 permutations of "outer permutation"(1, 2) (3, 4) (5, 6)(1, 2) (5, 6) (3, 4)(3, 4) (1, 2) (5, 6)(3, 4) (5, 6) (1, 2)(5, 6) (1, 2) (3, 4)(5, 6) (3, 4) (1, 2)After that, for each "outer permutation", we have 2^i "inner permutation"for example (1, 2) (3, 4) (5, 6)[(1, 2) or (2 1)] * [(3, 4) or (4, 3)] * [(5, 6) or (6, 5)]so that's where i! * 2^i come from.
•  » » » » » 4 weeks ago, # ^ |   0 $\frac{{n \choose 2} {n - 2 \choose 2} \cdots {n - 2 * i + 2 \choose 2}}{i !} = \frac{n!}{(n - 2i)! \cdot i! \cdot 2^i}$
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 multiply the polynomials with same degree using fast power (otherwise I got a TLE due to my slower nft template) and multiply the smallest polynomials in degree each time.
 » 4 weeks ago, # |   +21 Is this first beginner contest with FFT problem?
•  » » 4 weeks ago, # ^ |   0 Was problem F FFT ?
 » 4 weeks ago, # |   +6 I like the idea of a contest with simple problems using complex concepts
 » 4 weeks ago, # |   0 Can anyone explain problem F please ?
 » 4 weeks ago, # |   0 Are we forced to use ACL NTT for F?I'm having a really hard time making my F code pass with the NTT template I've been using before.It runs for about 1.88s locally for max case, so I don't think I've made mistake in small to large.
•  » » 4 weeks ago, # ^ |   +6 When you do small to large, you want(int)poly[i].size(), not (int)poly.size() on line 311. As is, the initial polynomial sizes are all the same, so it didn't even pass when I switched to AtCoder library since it doesn't do small to large. Now it passes in only 106 ms.Submission link
•  » » » 4 weeks ago, # ^ |   0 Oh wow... not sure how did I miss that.thanks :)