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

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

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.

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

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

Does anyone know how to solve Gold #2?

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

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.

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

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

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

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

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

How to solve platinum P3?

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

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

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

Solutions to plat problems:

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

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

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

    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?

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

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

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

    It can be solved with BIT too.

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

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

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

        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

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

          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

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

            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)

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

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

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

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

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

    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
    }
    
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

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

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