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

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

Hi all,

The first contest of the 2019-2020 USACO season will be running from December 13th to December 16th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

Edit 2: Even though it is impossible to start the contest after 23:59 UTC-12, contestants who start right at that point in time still get a full four hours to do the contest. Therefore, please do not discuss the contest until 4:00 UTC-12 on December 17.

Edit 3: Results can be found here.

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

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

When will the competition start exactly?

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

    You can choose to start any time in the interval provided, but once you start you have 4 hours and you cannot pause midway through.

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

      Well, I mean which hour exactly will we be able to participate? Since December 13th seems vague for me.

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

        I believe you can start right at 0:00 UTC of Dec 13th and ends at 23:59 UTC Dec 16th, so begins and ends right at start and end of dates given in universal time.

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

Looking forward to not being able to solve any problems!

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

Can somebody please say when will the contest exactly start.

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

    Read the comments above. Beginning at 0:00 UTC of Dec 13th and ending at 23:59 UTC Dec 16th, you can choose when to start the contest.

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

Uhm, how do you participate in the contest? I have an account, and I see the contest dates on the right sidebar, but where can you start the contest for yourself?

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

The contest starts at 13 December 2019, 0:00, UTC-12

https://www.timeanddate.com/worldclock/timezone/utc-12

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

Contest has begun, you can sign up for any 4 hour period to take the contest until 23:59 UTC Dec 16th.

GLHF everyone!

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

Dang, a lot of partials...

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

    Wait, are you allowed to say that?

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

      ...what I mean is that the problems just give a lot of partials ie. 1-3 test correct for some time complexity or 1-5 test cases correct for some time complexity, I'm not giving anything away.

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

        I would still refrain from discussing anything even minimally related to the contest.

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

Will there be an editorial after the contest?

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

Nice, enjoyed it.

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

I did screencast for Platinum contest and will post it here after the end of the contest.

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

Maybe a stupid question, but I couldn't find the memory limits anywhere?

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

The contest has ended more than four hours ago. Pinging this to discuss solutions.

Hints for platinum three? I have no idea how to deal with the condition on the number of inversions.

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

Did the contest end earlier than expected?

I was still in my window but I was kicked out when submitting problems. I think the contest should not end so early.

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится +79 Проголосовать: не нравится
Pieaters
Snowcow
Treedepth
Video of me typing and staring at a screen for hours
»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

How to solve gold milkvisits ( the one about trees ).

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

    First, break the query into 2 queries (a, lca(a, b)), (b, lca(a, b)).

    So for every query (a, lca(a, b), MILK_TYPE), what is the lowest node u which is parent of node a such that milk type of cow in that node is equal to MILK_TYPE. For (b, lca(a, b), MILK_TYPE), let say that node is v. If the heights of u and v are smaller than lca(a, b), then the answer for (a, b, MILK_TYPE) is 0, otherwise is 1.

    Finding node u, v could be done with dfs and stack for each milk_type.

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

      "Finding node u, v could be done with dfs and stack for each milk_type." Could you elaborate ?

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

        You will store a list of queries to process offline for each node. For each milk type, maintain a stack of nodes that have it when you do DFS. When you visit $$$a$$$ or $$$b$$$, you just need to check if the last element you pushed to the required milk type stack is lower than $$$lca(a, b)$$$.

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

      how to solve the online version of Milk Visits(gold)

      in editorial it is written at the end to try and solve it in (M+N)log(N)

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

        I have an online $$$O(N*\sqrt{N})$$$ solution.

        For colors with less than $$$\sqrt{N}$$$ occurrences, just check all nodes of that color in $$$O(1)$$$.

        For colors with frequency $$$\geq \sqrt{N}$$$ , we do $$$O(N)$$$ preprocessing per color to find the closest ancestor of that color. Using this we can find the answer for these colors in $$$O(1)$$$.

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

        For each color, you can store a set of the vertices of that color, sorted by their index in the preorder traversal (like in snowcow). Then given a path $$$u-v$$$ and a color $$$c,$$$

        • Find the lowest node $$$x$$$ above $$$u$$$ of color $$$c$$$ in $$$O(\log N)$$$ using the set of color $$$c$$$.
        • Test whether $$$x$$$ lies on the $$$u-v$$$ path using LCA in $$$O(1)$$$ or $$$O(\log N)$$$.
        • Do the same for the lowest node above $$$v.$$$

        Alternatively, use sparse segment trees as mentioned below.

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

    This might be really unnecessary but explicitly finding out the answer seemed easier to me.

    Let $$$f(u, c)$$$ be the number of nodes of color $$$c$$$ from root to node $$$u$$$, and $$$l = lca(u, v)$$$
    Then our answer would be $$$f(u, c) + f(v, c) - 2f(l, c) + (color[l] == c)$$$

    Doing an euler tour will reduce adding information of node $$$x$$$ to a range update, and calculating $$$f(x, y)$$$ to a point query. These can be done easily by maintaining a sparse segment tree for each color.

    Requesting the solution of other two problems.

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

      Pump: just iterate through every possible minimum flow value and find the path with minimum cost.

      Cowmbat:

      • Let $$$f_i$$$ be answer for $$$[1, i]$$$ and $$$cost_{c, i}$$$ be the cost to change prefix $$$[1, i]$$$ into $$$c$$$.

      • We have: $$$f_i = min_{j \leq i - k} (f_j + min_{\forall c} (cost_{i, c} - cost_{j, c}))$$$ = $$$min_{\forall c} (min_{j \leq i - k} (f_j - cost_{j, c}) + cost_{i, c})$$$.

      • Let $$$g_{i, c} = min_{j \leq i} (f_j - cost_{j, c})$$$, we can calculate $$$g_{i, c}$$$ from $$$g_{i - 1, c}$$$ in $$$O(1)$$$.

      • Substitute it in: $$$f_i = min_{\forall c} (g_{i - k, c} + cost_{i, c})$$$

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

    (MilksVisits Silver). Here is how I solved it. First I make the tree weighted.

    #1 — Weight of edge == 0 if both nodes are the same ('H') or ('G') (depends on you)

    #2 — Weight of edge == 1 same as zeros .

    #3 — Weight of edge == 2 if types of nodes (U,V) are different.

    now we preprocess the date using binary lifting keeping track of the Max.

    Finally, to answer the queries I get the max (U,LCA(u,v)) (LCA(u,v),v).

    of course, there are 3 cases if max is (0 or 1) the answers depend on how you make the graph.

    if the max is 2 the answer always is 1.

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

      You can store the highest ancestor with the same type. The answer is no if types of u and v are bad and the highest ancestor is the same.

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

    I had a different approach, using divide and conquer (kinda overkill though). First, notice that the answer for a query $$$(u, v, w)$$$ is $$$1$$$ iff when every vertex with type equal to $$$w$$$ is removed from the graph, $$$u$$$ and $$$v$$$ are in different components. Suppose we've already processed all the queries, i.e the solution is offline.

    Let $$$solve(l, r)$$$ be a function that finds the answer for every query $$$(u, v, mid)$$$ where $$$mid = (l+r)/2$$$. Now, iterate through every value $$$t$$$ from $$$l$$$ until $$$r$$$ and insert every edge $$$(a, b)$$$ from the tree in a DSU if either $$$T(a)$$$ or $$$T(b)$$$ are equal to $$$t$$$ and both $$$T(a)$$$ and $$$T(b)$$$ are different from $$$mid$$$. After this, to answer all queries $$$(u, v, mid)$$$, just check if $$$u$$$ and $$$v$$$ are in different components. If so, the answer is $$$1$$$.

    After this, remove all edges added in the DSU in the step above using a stack. To recursively call $$$solve(l, mid-1)$$$, we now have to add every edge $$$(a, b)$$$ from the tree where both $$$T(a)$$$ and $$$T(b)$$$ are not in the range $$$[l, mid-1]$$$ and either $$$T(a)$$$ or $$$T(b)$$$ are in the range $$$[mid, r]$$$.

    Then, to recursively call $$$solve(mid+1, r)$$$, erase all edges added in the step above again, and insert in the DSU only edges $$$(a, b)$$$ where both $$$T(a)$$$ and $$$T(b)$$$ are not in the range $$$[mid+1, r]$$$ and either $$$T(a)$$$ or $$$T(b)$$$ are in the range $$$[l, mid]$$$.

    Finally, remove all edges added previously in the DSU once again. Since we use DSU with rollback, the complexity of this solution is $$$O(n \cdot log^2 n)$$$.

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

    Hi, during the competition, I found another solution to this exercise. My solution is more complex than the one presented in the correction, however, and is slower. x)

    My solution is to maintain for each node of the tree all "open" requests (that is to say, passing through this node). All the "open" requests constitute in the merger: - sets of "open" requests from children - requests whose node is one of the ends of the path.

    We can maintain this effectively and simply with a set. To merge two sets of queries, simply make a DSU with the optimization of the smallest in the largest.

    If we try to add an identical request to the set, it means that we have reached the LCA of the nodes, and consequently that the request is "finished" (the ancestors of the current node will not be affected by the request). As a result, we can fire the whole request.

    Once this process is completed, we search in the set all the requests whose MILK_VISIT is the color of the current node. We put that they are possible, and we fire them from the set of requests so as not to have to consider them several times (which would lead to a considerable increase in complexity!).

    Sorry in advance for my English mistakes.

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

I selected the problems for platinum. Hope it was interesting (but not too interesting for those of you at the top, that would mean that it's too hard :P).

EDIT: Solutions are here.

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

How to solve silver P2 ?

I was trying to do binary search on the time spent but I wasn't quite getting it.

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

    I used sliding windows and few observations to solve the problem

    hint

    best silver problem I have ever solved. Thanks Benq

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

      I noticed this too

      My problem was calculating the time T

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

        if a particle is going leftwards add location and its weight to a array a. else add l-location and its weight to the array a

        now sort the array by distance(first value) and then keep iterating until the weight is atleast half of total weight.the time is the distance of the last index iterated

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

    Ignore weight's and collisions first. Calculate times then cows are at locations 0 and L. Notice that the order of increasing x is the same as increasing time in location 0 (contrary at position L). From this, we can find out T. To calculate collisions we can once again ignore weights and collisions. For every cow going to the right calculate the number of cows moving to the left in an interval $$$[x, x + 2T]$$$.

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

Does anyone think 795/1000 enough to pass silver? I was hoping to qualify in-contest but couldn't fully solve P2

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

For gold P3, was NMlogN not meant to pass? Thanks

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

how to solve p3 on plat with G.F?

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

When the results will be posted ?

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

In Bronze P3:
Generating all permutations + sorting got AC, but I was wondering if there is a more efficient solution, for example is it possible to construct the result directly from the conditions?

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

    As $$$n$$$ is very small ,your algorithm must get AC. You can also build a graph according to the relatives.

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

When will the standings be posted ?

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

Results and editorials are out at http://usaco.org/index.php?page=dec19results!

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

Anyone else that cant see how many points they had on the contest? I got full AC on P1 and P2, and on P3 I had first 8 test cases correct (first 2 subtasks) and rest was WA, that should put me at 833 points right? Enough to be promoted to Platinum division but I checked on my account profile and I'm still Gold and nowhere I can see how many points I had.

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

Could someone help me find a bug in my solution to Snowcow (Plat 2)?

I am getting WA on test cases 9 and 10 (I can't test it in my IDE because there is StackOverflowError).

https://github.com/tommattgeorge/CompetitiveProgramming/blob/master/snowcow.java