xiaowuc1's blog

USACO 2018-2019 Second Contest
By xiaowuc1, 5 years ago, In English

Hi all,

The second contest of the 2018-2019 USACO season will be running from January 18th to January 21st. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

EDIT: As a reminder, do not post any spoilers until the contest is over, which will be at 4 AM UTC-12 on January 22nd. If you have any issues with the problem statements, please consult the rules on how to contact the contest administrators. The administrators do not monitor social media.

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

Comments Comments (28)
| Write comment?
»
5 years ago, # |
  Vote: I like it -19 Vote: I do not like it

Does anyone know how to solve Gold #2?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

EDIT EDIT: Okay it's actually over now

I ACed gold P1 and gold P2, but unfortunately didn't have time to implement and debug P3 in one hour. It didn't seem very hard at all but my idea could have been wrong.

In some cases this has been enough for plat but I haven't got my hopes up.

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

    Contestants cannot start anymore, but some may still be working. Please wait for discussion.

    → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It is now 4 AM UTC-12 on January 22nd.

Thanks to pacu for being a stellar problem writer (all three in Platinum)!

I can't wait for results to be released :D

→ Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve platinum P3?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since the contest is over now, does anyone know how to solve Gold #1?

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

    Write out a formula and use modular exponentation for an solution (mine ACed)

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +56 Vote: I do not like it

Solutions to plat problems:

redistricting
exercise
tracking2
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can solve redistricting in O(N) using DP + deque.

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

    Would you like to explain for exercise, in the solution, " If the two non-standard trails we are considering have edge-disjoint paths, then it is not possible to create a simple cycle with them. However, if their paths do overlap, then we can create exactly one simple cycle." why we can only create one simple cycle? wouldnt the sample case be the counterexample?

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was #2 Gold supposed to be solved with policy based data structures?

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

    It can be solved with BIT too.

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

      Can you elaborate a little bit on how to solve? I tried using binary search and naive shuffling to no avail.

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

        take the longest descending subarray from the back (i.e a[x] < a[x+1] < .. < a[n]) now insert the elements a[1] to a[x-1] at the right positions in this subarray using PBDS/BIT etc

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

          How does using a BIT or PBDS make the runtime any different from using binary search and inserting the elements at their respective spots? Sorry if this is a dumb question lol

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

            Could it be due to the complexity of inserting in the vector which you are binary searching in? I think that's linear, while point update in a BIT is logarithmic. I wonder if using a set would allow binary search to pass...

            (I didn't solve the problem either, by the way)

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

            It doesn't. One of my friends solved it using binary search and the insert function.

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

              Could you explain how this TLE's then? I'm absolutely stumped.

              Code: https://pastebin.com/kkZVd5u7

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

                Yeah, like I said, it's probably because you are using ArrayList (which has linear complexity for insertion) and not a TreeSet.

                → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me if I was at least on the right track for Gold #3, and if so, where I went wrong?

Code: https://pastebin.com/2NEWWT9P

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

    Using Djikstras to store the parent for every node then backtracking is the correct approach. I believe where you went wrong is when you tried to make sure every cow moved on the lexicographically shortest path. You seem to check for that in the compareTo of the Pair (which are your Edges), but you actually should be checking the vertex id's inside the for loop at line 46. You need to compare to parent of the node at the other end of the edge and current node. The if statement that you are missing is 

    if( distance[v] == distance[node] + w && id[v] > node) {
    //do same thing as your other if statement
}
    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Gold P1 was mine. Solution sketch:

Start by computing the number of possible lines ending in each rhyme class. This can be done using a fairly standard coin DP. Essentially, we have N+K states--one for each of the N possible incomplete line states and for the K possible rhyme classes for completed lines. The N words are our transitions, so in total this has efficiency O(N(N+K)). Note that doing a separate DP for every single rhyme class will be too slow, as this has runtime efficiency O(N^2K), so the key observation is that we can reuse all of potential incomplete lines no matter which rhyme class we're ending with.

Now, for each number of lines X such that some letter appears X times in the rhyme scheme, we want to know how many ways there are to create a set of X rhyming lines. This is fairly easy as well--if dp(i) is the number of lines ending in rhyme scheme i, the number of sets of rhyming lines is the sum of dp(i)^X over all i, since there are dp(i) ways to pick the first line, dp(i) ways to choose the second, and so on. Note that because X can be up to 10^5 and we could have up to N rhyme classes, we'll need to use an efficient exponentiation algorithm. Here's some pseudocode:

exp(base, power):
  if (power = 0) return 1;
  ans = exp(base, power / 2); ans = ans * ans;
  if (ans % 2 = 1) ans = ans + base;
  return ans;

This algorithm runs in O(log X). (You have to be careful while implementing to frequently take the value mod 1,000,000,007 to prevent overflow.)

Finally, to compute the answer, we multiply the above values for each letter appearing in the rhyme scheme together.

→ Reply
»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply