This contest is CANCELLED. Please read updates for details
We will hold ACL Contest 2.
- Contest URL: https://atcoder.jp/contests/acl2
- Start Time: TBD
- Duration: 150 minutes
- Number of Tasks: 6
- Writer: maroonrk, yosupo
- Tester: maroonrk, yosupo, sigma425
- Rated range: 1200 — 2799
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.
Would this contest be "between ARC and AGC" like the last ACL contest, or at the same difficulty level of a normal ARC?
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.
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.
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.
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
If this round will be as hard as the previous ACL, I think this will be too hard for pupils
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).
maroonrk Any plans to change profile pic?
https://atcoder.jp/contests/abl
ACL Beginner Contest starting soon!
Now as the contest has finished could anyone please tell me how to solve D — Flat Subsequence
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
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
Like last week I implemented everything with segment tree ;) But was not able to solve F. However, here is what I found:
The 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
This 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)
We 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 and B where simple as usual. SubmissionA SubmissionB
Hello sir In problem D how are you merging two segments?
I use max of both values. Since the segment tree maintains the maximum length of sequences seen so far.
can D solved by DP ??
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.
Why you have taken aux+k+1 in your submission
Because that implementation of a segment tree I used there expects the right border to be exclusive, not inclusive.
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.
I added some comments to a submission: https://atcoder.jp/contests/abl/submissions/17053342
I try to explain what each parameter of the lazy segtree does. Hopefully it can be useful to understand the library better.
That's really useful. Thanks a lot
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 lol
Still, really nice practice and nice library, thanks for the contest.
I need tutorial for documentation lol. Freaking mathematical terms
What is the meaning/full form of ACL?
Atcoder Libray contest.
Anyone care to explain F?
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
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 link
EDIT: I have edited the multiplication factor, thanks Kush.code for pointing it out.
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
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), then
we 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.
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.
Is this first beginner contest with FFT problem?
Was problem F FFT ?
I like the idea of a contest with simple problems using complex concepts
Can anyone explain problem F please ?
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.
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
Oh wow... not sure how did I miss that.
thanks :)