xiaowuc1's blog

By xiaowuc1, 7 weeks 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

»
7 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

When will the competition start exactly?

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

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

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

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

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

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

Looking forward to not being able to solve any problems!

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

Can somebody please say when will the contest exactly start.

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

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

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

    You can't until the contest officially starts.

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

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

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

»
7 weeks ago, # |
  Vote: I like it -136 Vote: I do not like it

Dang, a lot of partials...

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

    Wait, are you allowed to say that?

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

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

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 4   Vote: I like it -26 Vote: I do not like it

        Guys, good luck!! :)

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      btw nice spelling

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

Will there be an editorial after the contest?

»
6 weeks ago, # |
  Vote: I like it +65 Vote: I do not like it

Nice, enjoyed it.

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

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

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

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

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

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

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

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

      Well, the test data is essentially random.

      • »
        »
        »
        »
        6 weeks 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?

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

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

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

    • »
      »
      »
      6 weeks 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 ?

      • »
        »
        »
        »
        6 weeks 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)$$$.

    • »
      »
      »
      6 weeks 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)

      • »
        »
        »
        »
        6 weeks 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)$$$.

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

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

    • »
      »
      »
      6 weeks 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})$$$

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

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

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

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

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

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

  • »
    »
    6 weeks 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?

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

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

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

      I noticed this too

      My problem was calculating the time T

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

  • »
    »
    6 weeks 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]$$$.

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

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

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

    Congrats, you made gold!!!

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

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

    I'm not aware of such a solution.

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

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

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

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

how to solve p3 on plat with G.F?

»
6 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

When the results will be posted ?

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

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

»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

When will the standings be posted ?

»
6 weeks 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!

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

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

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

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

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

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