maroonrk's blog

ACL Contest 2 Announcement
By maroonrk, history, 4 years ago, In English

This contest is CANCELLED. Please read updates for details

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.

  • Vote: I like it
  • +192
  • Vote: I do not like it

Comments Comments (41)
| Write comment?
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Would this contest be "between ARC and AGC" like the last ACL contest, or at the same difficulty level of a normal ARC?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it +32 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

    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.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If this round will be as hard as the previous ACL, I think this will be too hard for pupils

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by maroonrk (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it -43 Vote: I do not like it

maroonrk Any plans to change profile pic?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abl

ACL Beginner Contest starting soon!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Now as the contest has finished could anyone please tell me how to solve D — Flat Subsequence

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Like last week I implemented everything with segment tree ;) But was not able to solve F. However, here is what I found:

E
D
C
A+B
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello sir In problem D how are you merging two segments?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I use max of both values. Since the segment tree maintains the maximum length of sequences seen so far.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can D solved by DP ??

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why you have taken aux+k+1 in your submission

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because that implementation of a segment tree I used there expects the right border to be exclusive, not inclusive.

      → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +9 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I need tutorial for documentation lol. Freaking mathematical terms

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the meaning/full form of ACL?

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Anyone care to explain F?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +8 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it
          $$$ \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} $$$
          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Is this first beginner contest with FFT problem?

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I like the idea of a contest with simple problems using complex concepts

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem F please ?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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

    → Reply