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

Автор lewin, история, 5 недель назад, По-английски,

NAIPC is coming up on April 15 (start time here). More information can be found on the site. The contest will be on Kattis on the 15th. About 15 hours later, it will be available as an open cup round as the Grand Prix of America. Please only participate in one of them, and don't discuss problems here until after the open cup round.

The deadline to register for the contest on Kattis is April 12th. You can register by following instructions on this site: http://naipc.uchicago.edu/2017/registration.html# You will need an ICPC account to register.

You can see previous NAIPC rounds here: 2015, 2016. 2016 is also available in the codeforces gym here: http://codeforces.com/gym/101002

UPD 1: The deadline to register is in a couple of days.

UPD 2: Both contests are now over

NAIPC standings: https://naipc17.kattis.com/standings

Open Cup standings: http://opentrains.snarknews.info/~ejudge/res/res10376

I'll update this one more time with solutions once they are up.

UPD 3: Test data is available here (solutions may show up later, but I'm not sure when): http://serjudging.vanb.org/?p=1050

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

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

so,it's unrated?

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

How is it related to ICPC? Will North American teams be selected based on this contest?

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

    This started as a contest for North American ICPC teams. It used to have some big prizes but since we don't have many sponsors currently, it is mostly just for fun now. It's meant as some more practice before WF, and is not used for any kind of selection.

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

    No teams are selected from this contest this year.

    North America is trying to form a super regional for WF selection sometime in the future (something like NEERC). This contest is a stepping stone to that end.

    Right now the contest is a WF preparation contest. The target is an ICPC WF level set to prepare teams for the difficulty and pressure of ICPC WF. (Or that's what I've been told anyways.) It used to be an onsite invitational contest (at UChicago) for teams going to ICPC World Finals but due to lack of sponsorship in recent years is an online only contest.

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

I think the 6th pretest for the second question is wrong .

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

Will there be a gym mirror?

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

Contest is over and results are here.

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

How do you estimate how fast flow works?

I believe G is a flow problem. There are various ways to construct a graph, and also there are various flow algorithms. What is a good way to choose them? (Big-O analysis is not very useful here)

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

    Distance from source to sink is rather small here, so I believe Dinic will be the best one. Network usually should be chosen such that number of edges is as small as possible. In this problem we used network with about 106 edges.

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

      Can you describe more about your network?

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

        Make nodes for every horizontal segment, it could be done straightforward using nm3 / 6 edges or in segment tree-like technic using edges.

        Then we made something like sparse table over each group on n segments having the same left and right ends. It cost us edges. Then each customer has 2 edges.

        P.S. Now I realized that first part could be done like sparse table too. In that case it will consist of nm2 edges

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

          Just sparse table (2dimensional) is enough to get 0.5 running time

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

            I tried to create such solution, but it has more edges and its implementation looked for me more tricky.

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

            Sadly, the data for G was extremely weak to the point that very naive greedy solutions passed the data. This caused the Dinic to find a solution on its first iteration and simply break out very early. I have been working on generating some stronger data and have got something that takes >10 seconds. This is more than double the timelimit allotted for this problem.

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

              Here comes the question to the authors: how did they decide to make such constraints? Why weren't there strong tests on the contest? Haven't they had a doubt when preparing the problem, that on some tests this solution might be working too long?

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

                Initially the bounds were set at k = 1,000. However the data was weak and naive flow solutions that should TLE passed in time. Thus they raised the bounds. However, they failed to consider that the data was just weak and not that this flow graph just runs fast. (It doesn't if you make good cases)

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

    G is a flow problem with V = nmlgnlgm + k, E = 4k + 2nmlgnlgm. Also, someone I know wrote E = O(klgnlgm) (approx 15M edges) and passed. In this problem, I think author needed big constraint to force his solution (although, surprisingly, this failed.)

    I was also curious about the time complexity of flow algorithm. This is the "fact" I know about time complexity of flow algorithm :

    • Ford fulkerson is O(NM^2), Dinic is O(N^2M). (You can solve a problem about making Dinic TLE with O(N^2M) operation, on here)

    • Both are O(fE) of course

    • If it have unit edge capacity, Dinic runs in O(M^1.5). This was proposed in some CF round in last year.

    This was what people usually say about time complexity of flow algorithm :

    • Ford fulkerson is fast, and Dinic is super fast

    • You need a lot of experience

    • If you can't solve with Dinic, that is not a flow problem

    I'm not sure it is a good practice. If you are sure that is not a good practice, please update this article.

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

      In case of unit capacity Dinic works in

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

        I'm aware of proof for O(EV2 / 3) but I never heard of faster one. Can I ask about some resources for it?

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

        That runtime needs the additional requirement of in degree 1 or out degree 1 for each node. The bipartite matching case meets this requirement.

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

          At first, I accidently gave one downvote to this reply. Does that explains it's -15 downvote?

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

      Here 3053014 is the push preflow algorithm implementation that is faster than Dinic (for the given problem), so Dinic not always the fastest flow algorithm.

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

        I was (and probably, they were) aware of push flow algo for maxflow. I just wanted to stress out that the problemsetter don't usually force it, even though there might be a case that I want to force my non-model flow sln to pass.

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

How to solve E?

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

    Add X to the cost of each edge that connects a special vertex and a non-special vertex, and find an MST in this graph.

    If you are lucky and this MST contains exactly k edges between special vertices and non-special vertices, this is the answer.

    Otherwise you should change the value of X to be "lucky" — do binary search on X.

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

      Why does there exist such X that the MST contains exactly k edges? We had this solution accepted, though we had to consider carefully the cases where we can add either special or non-special edge to the MST.

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

      That is a truly amazing solution. Is there any other solution that ordinary people can think?

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

      Take complete graph, all edges have weight 1, k is somewhere in the middle.

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

        More precisely, for a fixed X, I computed LX and RX — the minimum/maximum possible number of special edges in an MST. Then LX + 1 = RX.

        • »
          »
          »
          »
          »
          9 дней назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится
          1. I believe if x is double

          2. Still not obvious how to restore the answer

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

            Probably one can think in this way. Let the answer tree be T and its cost to be C. Suppose when you add weight x to each special edge, you can construct an MST T' with k special edges, and the cost of T' is C'.

            (1) If we subtract weight x for each special edge of T', we still get a spanning tree with cost C'- k*x.By the property of our answer tree, C <= C'- k*x.

            (2) If we add x for each special edge of T, we get a spanning tree with cost C + k*x. Then by the property of T', we have C' <= C + k*x.

            (3) By (1) and (2), C = C'-k*x.

            So if we can find such an x to we can construct an MST with k special edges, we can simply output C'-k*x, and no solution otherwise? (not sure)

          • »
            »
            »
            »
            »
            »
            7 дней назад, # ^ |
            Rev. 3   Проголосовать: нравится +25 Проголосовать: не нравится
            1. It sufficient to consider only integer x because sorting of edges by weight changes only in integer points. To get Lx in case of equal weights we prefer usual edges, opposite for Rx. If x is increased by 1, then all special edges jump to next weight and order of edges in Rx and Lx + 1 will be the same.

            2. To get spanning tree with Lx ≤ k ≤ Rx edges, we can consider intervals of edges with equal weights independently (because for prefix of edges we will always get the same set of components regardless of their order in Kruskal's algorithm). To get spanning tree with any possible number of special edges one can build components using only usual edges, then add all necessary special edges (there are Lx of them), then add any subset of spanning tree on remaining special edges.

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

      black magic

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

      I have been solving that problem maybe 4 years ago and already forgotten about it :(

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

How to solve D?

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

    DP on subtrees with merging sets. First, make all numbers different. Let d(x) be the answer at some subtree if all taken vertices have value  ≤ x. We store in a set all such x that d(x) ≠ d(x - 1) (note that in this case d(x) = d(x - 1) + 1).

    Now if you look at the transition formulas (or stare at the values of these sets on some examples) you will see that the recalculation is similar to finding the LIS. First, we merge the sets of the children. Second, we replace the value set.upper_bound(wv) with the value wv or add it to the set if upper bound does not exist. The answer is the size of the set in the root.

    Honestly, I don't know how to come up with this solution without staring at the examples.

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

      For motivation, you can notice is if the tree is a line graph, then this is exactly computing LIS on the sequence. Anyways, here's a short implementation of the above approach:

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

How to solve A?

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

    Sort all bracket sequences according to some weird combination of minimum depth and sum , then do DP.

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

      We got this by just trying several sort functions. Is there intuition for why this one is correct?

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

      You can mention some combination?

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

      You can mention any?

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

        pre = minimum prefix sum
        len = length of bracket
        sum = sum ( = +1 and ) = -1

        Note that i am not sure why it worked , i tried several combinations until i got ac.

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

          I tried to find a specific combination for around 2 hours in the contest, got super frustrated, wrote several comparators and ran the DP against them all, and printed the maximum answer (AC). Wasted almost entire contest on A :/

        • »
          »
          »
          »
          »
          8 дней назад, # ^ |
            Проголосовать: нравится +1 Проголосовать: не нравится
          my team solve the problem in the contest with similar idea
          this is a more deep analysis
          
          The main idea is that if some comparator can be defined so that,
          if the pieces are previously sorted, always exist some optimal solution 
          that can be formed following this order, 
          then doing basic dp we arrive at the solution
          
          The same notation:
          pre = minimum prefix sum
          len = length of bracken
          sum = sum ( = +1 and ) = -1
          
          Note that we can ignore the couples of open-closed parentheses(without change the len property) for one more clear view, this do not change any thing, then exist three types of pieces
           
          1 - Open Type
              (())(( --------> is ((
              ((()( ---------> is (((
              pre >= 0
          
          2 - Closed-Open Type
              ()))()( -------> is ))(
              ))))(())())(()(---> is )))))((
              pre < 0 && pre != sum
          
          3 - Closed Type
              )))())---------> is )))))
              ()()()())))----> is )))
              pre < 0 && pre == sum
          
          The Closed-Open Type has two subtypes:
          
          2.1 - Incremental Closed-Open ( more open parentheses that closed parentheses )
                ))()())(((( -----> is )))((((
                )()(((((((( -----> is )((((((((
                pre < 0 && pre != sum && sum >= 0
          
          2.2 - Decremental Closed-Open ( more closed parentheses that open parentheses )
                ))()())(( -----> is )))((
                ))()( -----> is ))(
                pre < 0 && pre != sum && sum < 0
          
          Any correct sequence of pieces can be reorder in this way: 
          first --------> open pieces ( in any order )
          next  --------> incremental-closed-open pieces ( in decreasing order of pre ) 
          next  --------> decremental-closed-open pieces ( NOT exist any correct comparator ) 
          and finally --> closed pieces ( in any order )  
          and the sequence remains correct
          
          But the issue is that NOT exist any correct comparator for decremental-closed-open pieces, many teams, my team included, accepted this problem with wrong criteries for compare decremental-closed-open pieces,
          for example:
          - decreasing order of pre (My solution)
          - decreasing order of par(pre - sum , sum)
          Both criteries has WRONG SOLUTION to this case:
          4
          (((((
          ))))(
          )))))((((
          )
          
          The correct idea is that if we have a good way of compare open and incremental-closed-open pieces, then we can divide the problem in two parts: 
          1 - for each possible value v, what is the maximum lentgh of any sequence formed using only open and incremental-closed-open pieces, with exactly v open parentheses without couple, this problem can be solved sorting open and incremental-closed-open pieces and doing dp
          
          2 - for each possible value v, what is the maximum lentgh of any sequence formed using only decremental-closed-open and closed pieces, with exactly v closed parentheses without couple, this problem is similar to 1 if the pieces are reverted and the parentheses are changed '('-->')' and ')'-->'('.
          
          Now the solution for original problem would be
          Max( dp[v] + dp2[v] ) for all possible value v
          
»
9 дней назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

How to solve B?

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

    Once you know the plane where one of the bases is, you can project all the points on it, and the result will be the maximum distance to that plane (height of the cylinder) * area of minimum circle that covers the projected points (a 2D problem for which there is a randomized algorithm with expected runtime O(N) ).

    The problem is finding those planes, since it takes too long to check all the candidates, even with the information that there are at least 3 points on one of the bases. I've tried all sorts of tricks and randomized checkers and failed during the contest, and the only way I could get accepted afterwards was with 3d Convex Hull (the planes we are looking for will be the planes of the hull faces which I'm pretty sure are at most O(N)).

    I'm really curious if others got it without Convex Hull.

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

    You need to do 3d convex hull, then apply steps above. The 3d convex hull is made slightly easier by the fact that you can do it in O(n^2).

    For instance, here's my code for 3d convex hull using gift wrapping (~10-15 lines).

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

How to solve C?

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

    It could be solved using dynamic programming.

    Firstly, "There is exactly one path, going from streamer to streamer, between any two students in the circle." means that the resulting graph is a tree with n students as vertices and n-1 streamer as edges.

    Secondly, "No streamers may cross." indicates that if there's a streamer connecting student i and student j, then after erasing this streamer, we are left with one tree of all student in range (i, j) and another tree of all students in range (j, i). Note that the interval here is cyclic. For example, n = 10, (8, 4) represents {9, 10, 1, 2, 3}, and (4, 8) represents {5, 6, 7}.

    This gives us a way to define DP states. Let dp(int i, int j, bool connected) be the number of ways to construct a tree for students in range [i, j], and there's a direct streamer between i and j if connected is true while there's no direct streamer between i and j if connected is false.

    The final answer is (dp(1, n, true) + dp(1, n, false)) % 1000000007.

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

Any hint on problem H?

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

    It's hard to give a small hint, but you can look at the first sample a bit more closely

    I added a big hint below:

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