maroonrk's blog

By maroonrk, history, 4 weeks 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
  • +202
  • Vote: I do not like it

»
4 weeks 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?

  • »
    »
    4 weeks 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.

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

      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, # |
  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.

  • »
    »
    4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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

»
4 weeks 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).

»
4 weeks 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).

»
4 weeks ago, # |
  Vote: I like it -43 Vote: I do not like it

maroonrk Any plans to change profile pic?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abl

ACL Beginner Contest starting soon!

»
4 weeks 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

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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

»
4 weeks 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
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 weeks 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.

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

    can D solved by DP ??

    • »
      »
      »
      4 weeks 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.

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

        can u explain how to use segment tree in this question

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

    I did the same. But got the wrong result. By the way, I felt relieved to know my approach was correct.

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

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D? Is there a way to do with dp I tried but got runtime error while using dp.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone give any hint or editorial for problem D.

»
4 weeks 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.

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

    I need tutorial for documentation lol. Freaking mathematical terms

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the meaning/full form of ACL?

»
4 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

Anyone care to explain F?

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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

        • »
          »
          »
          »
          »
          4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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} $$$
    • »
      »
      »
      4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Is this first beginner contest with FFT problem?

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain problem F please ?

»
4 weeks 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.

  • »
    »
    4 weeks 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