Блог пользователя maroonrk

Автор maroonrk, история, 4 года назад, По-английски

We will hold ACL Contest 1.

The point values will be 300-600-600-800-900-1800.

As mentioned in this blog, you may use the library in the contest. However, it's not mandatory to install the library or learn C++; I've verified that all problems can be solved with python(pypy3).

I also tried hard to ensure the quality of the problems, and I believe that you can enjoy tasks as a usual AtCoder contest, rather than yet another practice contest. In addition to that, I would like to mention the last problem, which is unusually hard for ARC-rated contests, and we welcome >2800 coders to challenge it.

We are looking forward to your participation!

  • Проголосовать: нравится
  • +234
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hoping for an amazing round!!

»
4 года назад, # |
  Проголосовать: нравится +122 Проголосовать: не нравится

Our initial plan was to prepare tasks that require standard applications of the contents of the library, and make a practice contest for intermediate people while advertizing the library.

However, we changed the plan because we want to advertize it for strong people too, and improved the quality of the problems to make a contest that is worth participating for them too. maroonrk even refused to use some fine tasks that are acceptable for ARCs.

So, expect something between an AGC and an ARC!

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

    As a beginner-intermediate coder, i’m not sure the contest was beginner friendly, if it was intended to be fun for beginners.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Video on how to use Atcoder library. Looking forward for the contest!

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Please also kindly update kotlin version to 1.4.0. Thanks in advance

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Kinda unrelated but do you have any plan to change the rating system so that we don't get 0.00000000001 delta for accounts with lots of rated contest participation?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    Isn't atcoder's less shaky rating system better in some cases? For example, it prevents extreme positive delta from ABC. It also prevents extreme negative delta for one bad performance (can happen for network error, power loss etc.). As Atcoder has different time penalty from other OJs, contestants can easily submit at end of contest / when certain that their rating won't drop much. I think a less shaky rating system encourages participants to not worry about rating much.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes it's better in those very specific cases I suppose..

      I don't see any reason to make participants not worry about their rating. All that they have to do for that is make a throwaway account and participate with it.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +51 Проголосовать: не нравится

    Yeah, the codeforces system where your rating is determined by last 5 rounds is better :sarcasm:

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +40 Проголосовать: не нравится

      I don't think CF's system is better, but I think on AtCoder the effect is too strong. If I recall correctly, old contests from 2017 hold me back by about 100 points despite being mostly irrelevant.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think your current rating is supposed to represent how good you are now, not how good you were in the past (we have the rating graph for the latter). So I actually do think that determining your rating based on the last 5 rounds is better.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +34 Проголосовать: не нравится

        My rating was 3548 on 29.04.19, 3001 on 21.06.19 and 3494 on 23.09.19. What's more likely in your opinion: I went from one of the strongest CPers to almost-not-nutella and back in 5 month or CF rating is broken?

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +25 Проголосовать: не нравится

          I'd say it's more weird for you to not lose bunch of rating from 3.5K when you had few 3K performances in a row.

          Like suppose if an orange coder starts participating with your account. In my opinion, a "decent" rating system should be able to detect it from recent few performances that the guy is orange-level and adjust the rating of your account accordingly, not get stuck at high rating just because that account has huge number of past rated contest participation.

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится +29 Проголосовать: не нравится

            I don't agree. Rating is a measure of your strength. Obviously everyone has stronger and weaker sides, and it can happen that there are several rounds in a row where one has bad performance, and it shouldn’t disturb the rating a lot. Of course, it should gradually become lower, but overall the rating should be stable against several bad or good contests in a row.

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +15 Проголосовать: не нравится

              I'm not sure why do you think that one's rating should be stable. One's strength (in CP) can fluctuates depending on his condition at the time he's taking the contest.

              It could be because of unfavorable contest time, or maybe he ate some food gone bad, or he could have some bad performances on one of recent contests and can't think straight because of it.

              In this regard, I'd argue that any rating system which tries to adjust this fluctuation artificially, does not reflect one's strength at that time well.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится +15 Проголосовать: не нравится

                Ok, we have different views on rating. I don't understand yours to be honest, but that's fine with me, I don't care.

»
4 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

What is the full form of ACL? Like we have ABC (Atcoder Beginner Contest). What does ACL stand for?

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

editorial plzz

»
4 года назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Can I use DSU to solve A? Why it is wrong?

code
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    I solved it via monotonic sets, I didn't try for any other approach though

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

    If you think of it as a permutation, reverse it, now each connected component is an interval of both indices and values so a component ends every time the maximum of the first $$$i$$$ elements is equal to $$$i$$$.

    Code
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes! Thank you very much! My solution is realy close to the yours.But I don't know why I didn't realize this mistake during the contest!

      Problem A took me 2 hours:(,And after I solved B ,there is no time left!!

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Instead of inserting the current secondary (which is not used in sorting) co-ordinate we have to insert the minimum secondary co-ordinate of the set in which the current index belongs. My Submission

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    A has the same idea and solution basically as Moo Particle, a problem from a recent USACO contest here: link

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank You for the super fast editorial!

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is "doubling" from problem D's editorial?

»
4 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

This is the tutorial for A

Unfortunatly I do only understand the $$$O(N^2a(n))$$$ solution. Can somebody explain the $$$O(Na(n))$$$? That loop looks like $$$N^2$$$ to me, I get something wrong.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -6 Проголосовать: не нравится

    I think there's something wrong with the Editorial, you can check my solution of dsu.

    code
    • »
      »
      »
      4 года назад, # ^ |
      Rev. 7   Проголосовать: нравится 0 Проголосовать: не нравится

      My algorithm for A (TLEs) is similar to the dsu editorial, and Id say use the same complexity.

      Here is my submission https://atcoder.jp/contests/acl1/submissions/16918995

      BTW for B we can do better than sqrt with bitmasks

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      I think the $$$ O(N\alpha(N))$$$ solution in the editorial indeed should be more clear.

      Suppose I have $$$(1,N),(2,N-1),\cdots,(N,1)$$$, the algorithm must traverse every pair of points, which is $$$O(N^2)$$$ and would TLE.

      I actually feel bad because I found the $$$x_i=i$$$ idea but couldn't finish :(

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    What do they even mean by a(n) ? Is that some fancy way to denote logarithm and slower functions?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    you can refer my code link- https://ide.geeksforgeeks.org/ZV03mZTlG2

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

can someone please explain me the solution of problem B

  • »
    »
    4 года назад, # ^ |
    Rev. 6   Проголосовать: нравится +7 Проголосовать: не нравится

    (If you have any suggestions or corrections feel free to comment below, I'll fix)

    Notation: $$$A\backslash B=$$$ the set of elements contained in A that are NOT in B.

    I actually found the official solution quite unintuitive, so here is my (slightly faster) approach.

    Factorize $$$2N=\prod_{i=1}^n p_i^{e_i}$$$, where $$$p_1,\cdots,p_n$$$ are distinct prime factors of $$$2N$$$. For convenience, let $$$q_i=p_i^{e_i}$$$ for $$$1\le i\le n$$$.

    Let $$$[n]$$$ be the set of positive integers from $$$1$$$ to $$$n$$$

    We need $$$\prod_{i=1}^n q_i \mid k(k+1)$$$. Since $$$\gcd(k,k+1)=1$$$, suppose $$$S\in [n]$$$, $$$q_i\mid k$$$ if and only if $$$i\in S$$$, then since $$$\prod_{i\in [n]\backslash S} q_i\mid k(k+1), \gcd(\prod_{i\in [n]\backslash S} q_i,k)=1, \prod_{i\in [n]\backslash S} q_i \mid k+1$$$.

    Let $$$Q_S=\frac{2N}{P_S}$$$.

    We can now easily compute $$$k+1$$$ with modular inverses; let $$$P_S=\prod_{i\in [n]\backslash S} q_i$$$, then $$$\gcd(P_S, Q_S)=1$$$, suppose $$$x\equiv Q_S^{-1} (\bmod\; P_S)$$$, then $$$k+1=xQ_S$$$ works because $$$\frac{2N}{P_S}\mid k+1$$$ and $$$xQ_S\equiv 1(\bmod\; P_S)$$$ by the definition of modular inverse.

    There are less than fifteen distinct primes that can divide an integer $$$\le 2\cdot 10^{15}$$$, so this can be done in approximately $$$\omega(2N) \cdot 2^{\omega(2N)}\le 15\cdot 2^{15}$$$ operations, which is fast enough.

    Code
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      You said

      We can now easily compute ... $$$k+1 = x \cdot \frac{2N}{P_s}$$$ works

      Why? How did you reach that conclusion? Also, what do you mean by the notation $$$i \in [n]$$$ \ $$$S$$$? All the elements in $$$[n]$$$ but not in $$$S$$$?

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Could someone kindly explain approach with $$$O(KNM log(NM))$$$ complexity mentioned in official tutorial? Thanks in advance!

btw, I built graph with $$$O(K+NM)$$$ vertices and $$$O(KNM)$$$ edges and run mincost-maxflow on it during contest, but it turns out to be TLE. :(

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    same graph — 50ms (used atcoder implementation)

  • »
    »
    4 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

    From the source, add edges to pieces with capacity 1 and cost 0. From all the feasible final positions to destination, add edges with capacity 1 and cost 0. From a feasible position to another feasible position to the down or right, add an edge with capacity infinity and cost -1. (Feasible position is any a[i][j] != #).

    Find the minimum cost flow in this graph. I am unsure how to implement this with atcoder's min cost flow (I spent 15 mins thinking about why it isn't working, and the answer is because they require cost >= 0).

    Anywya, here's my in contest implementation: https://atcoder.jp/contests/acl1/submissions/16916600

    I would be grateful if someone would explain how to do this using atcoder's template.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Just add edge with cost T+cost, and after all mincost is mincost-T*maxflow

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        But then the minimum cost would be when the pieces don't move from their initial position at all. It wouldn't flow through the edges as it doesn't reduce the cost

        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          i guess missunderstanding, I mean cost = -distance

          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

            Is it possible for you to do a submit and send it here? Sorry, but I don't fully get your point, and the code is really short after using atcoder library.

            Unsure if you are referring to this idea: https://atcoder.jp/contests/acl1/submissions/16752194 which is a bit different, I guess

            Edit: rereading your comment, I guess you do mean the submission I referted above. Never mind then, that doesn't fully resolve my initial question :(

            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
                Проголосовать: нравится +8 Проголосовать: не нравится

              yes, different. for each o I calculate distance from o to cell that can be reached and add edge with flow=1 and cost=-distance

              flow graph is S -> L -> R -> T

              where L is start positions of 'o'

              R is possible finishes

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Screencast of barely missing out on 69th place :(

(also video solutions for A-D)

»
4 года назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

So, you made a maxflow problem for 600 points. Why?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    why not?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If 600 point problem is supposed to 1900-2100 rated problem then why there should be maxflow? I was recommended to learn maxflow after reaching master

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        Because you don't need to know how max flow works, only what it does(in this case finding max weight bipartite matching); the implementation is in the atcoder library.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +24 Проголосовать: не нравится

        Well this contest is specifically named "ACL" which means anything in the atcoder library can appear.

        Also, I think the advices like "do not learn ~~ until you reach master" should be interpreted as "it's better to focus on 'thinking' side of problem solving rather than knowledge side to reach master", which is true. Do not interpret it as "learning is bad till master" because that's not true. I bet majority of the people who learns flow in this planet don't even have a cf account.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Also, after you do the practice contest max flow problem, this one has almost the same idea anyway.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I feel like B is the easiest and the most straightforward, but A quite challenging.

BTW, can anyone hack the following "greedy" algorithm for C? It WAs but I can't find a counterexample.

The algorithm: scan points by rows from bottom to top, on a row I scan from right to left. Suppose I encounter a piece. I place it in the furthest place from it such that below and to the right are either an obstacle or a piece.

If this is not specific enough, see my code: https://atcoder.jp/contests/acl1/submissions/16920848

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    As with most incorrect greedy solutions, some decisions you make greedily will lead to a greater loss in the future.

    Test:

    4 3
    ..o
    ..o
    o..
    .##
    
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can somebody explain the O(N *a(n)) solution for problem A? I didn't understand the editorial.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have problems solving C with min cost flow? I used the code in the Atcoder Library and it gives wrong answer for even a simple test case like this:

1 3

o..

The answer should be 2 while the code gives me 1

I used the same logic but change the code to cp-algorithms.com and it gives the correct answer.

The code used Atcoder Library: https://atcoder.jp/contests/acl1/submissions/16973939

The code used another source and give correct answer: https://atcoder.jp/contests/acl1/submissions/16973807

Both of them use the same logic.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I just explained above in this thread in detail the same issue.

    TL; DR: You can't add negative cost edges in atcoder library.

»
4 года назад, # |
  Проголосовать: нравится -28 Проголосовать: не нравится

I think the ACL Round is useless.

You cannot use the ACL in big contests like IOI or some other websides like codeforces. If you use the ACL for a long time, you will forget the algorithms quickly.

So I think you shouldn't learn to use the ACL.