xiaowuc1's blog

USACO 2017-2018 US Open
By xiaowuc1, history, 7 years ago, In English

Hi all,

The US Open and final contest of the 2017-2018 USACO season will be running from Friday, March 23rd to Monday, March 26th.

As always, please wait until the contest is over for all competitors before discussing any specifics of the contest here.

Update: The contest is now live! Good luck to all competing!

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

Comments Comments (36)
| Write comment?
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

JOI TST 2018 + COI 2018 + USACO Open 2018 + NAIPC 2018 + VK Cup 2018 R2 + ARC 093. Six contests in this week!

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

Auto comment: topic has been updated by xiaowuc1 (previous revision, new revision, compare).

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

Can we begin discussion?

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

    After 2 hours and 40 minutes, yes.

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

    Very Accurate Depiction of True Events

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

      damn xD

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

      You're joking but seriously how to solve platinum P2?

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

        I think I have a theoretical solution. I haven't coded it up yet but I'm pretty confident it would work.

        Spoiler
        → Reply
»
7 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Can anyone explain solutions for platinum P1 and P2?

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

    Here is my code for P1, I think it's rather simple to understand solution:

    https://ideone.com/agAsKt

    I have not enough time to implement P2, my solution is very complicated and I couldn't well implement self memory management using 5500 mem cells :(

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

      Any brief proof of correctness / logic on why this works?

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      .

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

      It's a little bit difficult for a non-native speaker to explain the idea, but I will try :-)

      • The Moo Sort algorithm is stable, therefore the final positions of all elements are clearly known. W.L.G we can assume that a[1...n] are distinct and the array A is a permutation of (1...n)
      • For technical reason, firstly we run one phase of Bubble Sort to get initial partitioning.
      • For each value x, we want to count the number of segments (sub-array with >= 2 consecutive elements) containing x during Moo Sorting. After each Bubble Sort phase, one value greater than x was moved out of segment ... until x is the largest value of segment. After that we might need one more Bubble Sort phase to move x to the end of segment and get a new unit-length segment containing only {x}, the segment {x} is no longer considered.

      So, the algorithm is: For each value of x, COUNT THE NUMBER OF VALUE GREATER THAN x IN THE INITIAL SEGMENT, and if there's exists one value SMALLER than x placed after x, the counter is increased by 1 (because of extra bubble phase)

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

Can someone check out my code for Plat P3 that uses HLD based on this blog post?

I was only able to get TC 1 and WA on the rest. :(

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

    You don't actually need a segment tree for the chain update part.
    All your updates are "Do ai = min(ai, x), for " right?
    But as your queries are sorted by x, you can rephase your updates as "Set ai = x, if ai is currenty unset". Because if you've set a index before, that will mean it is already less than your current x.
    By this way, you can just keep a set of unset indexes and find the indexes which lie in range [l, r] and update them. In total you'll make , so the total complexity becomes instead of (plus possibly many bugs).

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

      @Rezwan.Arefin01 lol I did realize that when I was posting my code up, but I decided to keep it as is because the issue is WA not TLE.

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

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

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

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

How did you do Gold P1 and P3?

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

    For P3 I did knapsack where the dp[i] is minimum weight in knapsack with talent i.

    It is guaranteed at least one dp[i] > W, so there will always be a solution.

    For P1 I haven't found a way to solve the backwards case, it it really hard >:(

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

      Did you get AC with your code? Here is a simple test which gets WA: ideone

      Some minimum weight with talent i is not guaranteed to be > W, only some weight is guaranteed to be > W?

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Yeah I got AC in contest.

        As for the test case:

        120/7 = 17.1428...

        we multiply by 1000 and it's 17142.8..., and then we floor it.

        17142 is correct.

        Also there is guaranteed to be the case where we choose every cow (dp[mxTalent] > W).

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

    Problem 3: https://pastebin.com/bCtzScRY

    It says "maximize talent" but it really means "minimize weight", it originally did 0-1 knapsack with weight and maximized talent but realized the time/space would not fit so did it reversed.

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

Results are out.

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

    My brute force on Plat #3 still gets 14/15 test cases. :P

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

      Oh, haha nice! I spent nearly 2 hours trying to fix a memory issue with my solution to Plat #3 to no avail. But after results came out it strangely got full score (which was nice of course)... unfortunately I don't get my 2 hours of debug back :(

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

      Somebody also told me that plain loop + #pragma gets AC :(

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

If we add n=1 case in platinum P1 , many participants' solutions including author's one would be failed. The correct output should be 0 (because length(A)=1) but author's solution outputs 1.

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

    OMG I think you're right. But most people would probably realize and fix it if it was included. :)

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

    Thanks for pointing it out! My solution should now be fixed.

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

can someone help me debug for plat #3 plz. getting some weird runtime errors for the last few test cases (got cucked by regrading)

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

    jk plz ignore, not a runtime error, but memory limit exceeded :| (solved)

    → Reply