When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

xiaowuc1's blog

By xiaowuc1, 4 years ago, In English

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.

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

| Write comment?
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When will the competition start exactly?

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

    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.

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

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

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

        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.

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

          If I recall correctly, it is UTC-12 as opposed to UTC.

»
4 years ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Looking forward to not being able to solve any problems!

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

Can somebody please say when will the contest exactly start.

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

    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.

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

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?

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

    You can't until the contest officially starts.

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

      Oh, alright, I thought it was starting at 0:00 UTC, not UTC-12

»
4 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

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

»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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

GLHF everyone!

»
4 years ago, # |
  Vote: I like it -136 Vote: I do not like it

Dang, a lot of partials...

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    Wait, are you allowed to say that?

    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -98 Vote: I do not like it

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

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

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

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

Will there be an editorial after the contest?

»
4 years ago, # |
  Vote: I like it +65 Vote: I do not like it

Nice, enjoyed it.

»
4 years ago, # |
  Vote: I like it +93 Vote: I do not like it

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

»
4 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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

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

    From the instructions page under General Technical Details:

    Your program must be less than 100,000 bytes in size and must compile in 30 seconds or less. Unless otherwise stated, your programs will be limited to about 256MB of total memory use.

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

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.

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

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.

»
4 years ago, # |
Rev. 2   Vote: I like it +79 Vote: I do not like it
Pieaters
Snowcow
Treedepth
Video of me typing and staring at a screen for hours
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My $$$\mathcal{O}(n^5)?$$$ pieaters solution passed...

    precomputing
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Well, the test data is essentially random.

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

        Are y'all going to add more test data like how you did for Cowland?

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    I hate to necropost but...

    In the third task when you say dp[n][k] -> dp[n + 1][k], dp[n + 1][k + 1], ..., dp[n + 1][k + 1], what goes in the ... section?

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

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

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

    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.

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

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

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

        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)$$$.

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

      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)

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

        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)$$$.

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

        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.

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

          Could you please share a pseudocode so I could visualize it better? I am having troubles with the time limit.

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

    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.

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

      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})$$$

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    (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.

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

      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.

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

    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)$$$.

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

    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.

»
4 years ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

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.

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

    The platinum problems were really good! Thanks for setting them.

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

    Does this mean you will be working closely with USACO staff from now on?

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

How to solve silver P2 ?

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

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

    I used sliding windows and few observations to solve the problem

    hint

    best silver problem I have ever solved. Thanks Benq

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

      I noticed this too

      My problem was calculating the time T

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

        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

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

    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]$$$.

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

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

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

    There's no guarantee about the cutoff, but seeing how it's generally around 750 and this silver contest was harder than usual, it should be enough

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

    Congrats, you made gold!!!

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

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

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

    I'm not aware of such a solution.

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

      It's just the NMK solution but with segment tree instead.

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

        Just be aware of memory, I guess it can get TLE because of memory access.

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

how to solve p3 on plat with G.F?

»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

When the results will be posted ?

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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?

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

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

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

When will the standings be posted ?

»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

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.

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

    They judge by last submission so did your last submissions fail?

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

      No, all my last submissions were like I said above :/

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

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