kliu31415's blog

By kliu31415, history, 8 years ago, In English

The 3rd USACO of the 2015-2016 year is open from February 19-22 (It's February 18 now, and it's open for some reason, but whatever... maybe the opening time doesn't use EST). Unless someone else has already started a blog about this (in which case it'd be nice to have a link in the comments), we should discuss the problems here after it ends.

UPD: Contest is over. Discuss! UPD: Results are here

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

| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I participate??

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

Question: Are we allowed to discuss scores and problem difficulty before the contest ends as long as we don't talk about the problems themselves?

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

Am I correct in stating that the last participants will finish in a little over 2 hours? (If I did the time zone conversions correctly, the last participants started about 2 hours ago, which is UTC-12 23:59, so they will have about 2 hours left)

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

    No, if the contest time is the same as usual, you're not correct. The last participants will start competing in 10 hours and finish in 14 hours counting from now. Check here if you want to know when the last contestants will finish.

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

Does anyone have ideas for the first Silver problem? My friend later told me it was quadratic optimization, but it seemed really hard for a Silver.

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

    Wait three more hours, because some contestants are still solving problems.

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

      Sorry about that! I wasn't aware. Thank goodness no one posted the answer.

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

        for i->n for j->n find first empty entry and fill it with the nearest(not clockwise) filled entry...

        it is optimal...

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

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

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

My solutions (Platinum), in short (fix your LaTeX, CF!):

Load Balancing: try all coordinates of the vertical fence, double binary search for the minimum answer and the maximum possible range on the right+left that gives this answer (the number of cows on the right/left side in a given range with a given y-coordinate can be computed using BITs); check if the ranges have a non-empty intersection; O(N*log^3(N)) with optimisations

Fenced In: sort the N+M+2 fence parts (horizontal and vertical ones together) by length, then remove as many as necessary (without creating cycles) of each length in that order; if there are x processed horizontal and y vertical fence parts and we're processing a horizontal one next, then we need it removed all M times if x = 0 or y = 0 and M-y times otherwise, similarly for vertical parts; O((N+M)*log(N+M))

Circular Barn: there's a simple DP in O(KN^3) time, where we try all N ways of splitting the circular barn into a linear one and do a DP on the minimum cost of splitting its i-th suffix into k intervals, where we compute each state by trying all choices for the last interval (we can compute the cost of one interval from prefix sums of ri and i*ri); if we try only approx. N/K ways to split the barn, it becomes O(N3) with a good constant, which passes (there's an O(KN^2*log(N)) solution, but why bother)

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

    Load Balancing : You can remove binary search for minimum answer with something like that to make it O(N*log^2(N))).

    whilen(ans > 1 and check(ans - 1))
        ans--;
    

    Circular Barn : Someone can also solve it in O(KN^2) with convex hull trick.

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

      Convex hull trick has an additional log-factor, afaik.

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

        If queries are non-decreasing order, you don't need to binary search.

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

      I solved it using Knuth optimization in O(n3) but low constant made it too fast (100ms max).

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

        Doesn't Knuth optimization make it O(kn2)?

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

          No, the n part is still there. My dp first ran in O(kn2) and after Knuth it runs in O(n(n + k)) which is O(n2) and so it's O(n3) in total.

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

    Load Balancing: Finding left and right ranges can be done without binary search using just a BIT. If for example left side has t points and we want to check if answer is at most m (in binary search), then the range is [((t-m)-th y in sorted order)+1, ((m+1)-th y in sorted order)-1].

    So that reduces time complexity to O(n log^2(n)) ;)

    P.S: CFTeX seems to be fucked up recently. Why the hell O(n log^2(n)) results in Unable to parse markup [type=CF_TEX] !?

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

    for load balancing i tried all vertical fence and then did ternary search for optimal horizontal line since the max value will first decrease then increase for a fixed vertical line

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

      how did you handle the cases when there's equal values in ternary search?

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

        i didn't , i expected a WA but it gave AC.

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

          I didn't know ternary search, so I used a square root decomposition method that ran in O(N*sqrtN*logN), which gave me 11 AC and 4 TLE. Looking back on my code, I think I see a mistake and I should've gotten lots of WA... https://ideone.com/LUGOLn

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

          I got all WA with a ternary search D:

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

    I actually got all but one case in Fenced In with a O(N^4) solution. For some reason I didn't think of the prefix trick and so I had O(KN^3) DP states. I had two hours left, so I did a lot of heuristic optimizations and it (almost) worked. Grader not having the tests bunched + no penalty for resubmission helped a lot.

    (Of course, retrospectively, stopping to think for 10 minutes would've probably been a better idea)

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

      "Grader not having the tests bunched + no penalty for resubmission helped a lot."

      I used this a lot — just wrote the first thing that seemed fast enough and then hammered it into the TL. Why bother finding faster solutions if there's other stuff to do and the grading system is too simple...

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

    if we try only approx. N/K ways to split the barn

    I can't understand this part. How can you try only N/K ways to split the barn? One interval will have N/K length in average, but it's not the case in worst case.. am I missing something?

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

      It's called fitting the program to the test cases.

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

    An O(nlogn) solution for Load Balancing: we swipe from left to right with vertical fence. We keep a segment tree over an y-axis. In vertex of the segment tree corresponding to interval [b, c], we keep 2 numbers: number of points with y from b to c that are on the right of vertical fence and number of points with y from b to c that are on the left of vertical fence. It is easily updated while we move with the fence to the right. Now for every vertical fence we want to "binsearch" the best horizontal fence using the segment tree. We start in the root and go down to one of the sons always trying to decrease the number of points in the area that contains the most points. We do it until we reach a leaf of the tree. (We always consider the horizontal line that divides the segment of the vertex in half — that means it goes between segments of sons). We have checked logn horizontal lines and one of them was the best one for this vertical line.

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

Overall how do you guys think the difficulty of this contest compared to the previous ones (talking about Platinum specifically). I personally thought it was somewhat easier, and definitely easier than the February 2015 Gold contest.

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

    I think this contest had very interesting and fun to solve problems, specially the 2nd one. Comparing it to the previous one, I think it was easier, but it was definitely harder than the December Contest. The Gold contests I took part in last year were also much easier than this one, though I know that a couple of contests I didn't take part had challenging problems.

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

      Interesting. I got an 844 on this contest (I got 11/15 on the first problem, 10/10 on the second, and 8/10 on the third) and a 100 on the December contest (3/10 on the last problem because integer overflows).

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

        I also got 844 on this contest (14/15 on the first problem, 10/10 on the second and 6/10 on the third), but I spent a lot of time solving the problems. I spent over two hours on the 2nd problem and didn't have enough time to properly think the 3rd one. On the other hand, I used only little more than an hour to solve all the problems and get a full score on the December contest.

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

          That's way differently than what I did — I first used a janky solution to get 5/10 on the third problem, spent the next hour to solve the second (which turned out to be easier than I thought), went back to the third to get 8/10 by reducing my constant factor (I had O(KN^3)), and spent the rest of the time trying to think the the first. The first one really annoyed me, because I couldn't find a way to find the minimum of a bitonic function in log(n)^a time.

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

            I solved the first problem rather quick. I used a sweep horizontal line and did two binary searches to find the best position to put the vertical line. I supported the queries with two BIT's, one for points above the horizontal line and the other one for points below. Each time I moved the horizontal line, I updated both BIT's accordingly.

            Also I noted that I only need to process at most 100001 horizontal lines, and it fit in time. Somehow I got WA on test 14 though.

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

    I thought the platinum contest was tougher than January's. Problems had longer solutions and there wasn't a trivial brute force problem like January. Also, the DP #3 was easy to recognize but not at all simple to code(at least for me). I will be surprised if the mean score for plat is above 400.

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

      Scores will be higher, since it wasn't hard to get full points on some problems by writing some wrong solution.

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

Word is that test cases will be added to #3.

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

    Interesting. Where did you find that information (link)? I'm guessing they had too many successful submissions that ran in O(KN^3) when they probably wanted something running around (OKN^2).

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

    I think I have contributed to that decision — http://ideone.com/cgsXeB :D If N<=400, then I do the N^3*K dp and then I hash the input and... yeah, I cheat :D

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

      Maybe this will convince them to switch over to batched tests. It's weird because they have a batched system for their selection camp contests, so it isn't like the infrastructure isn't there. Moreover, batched tests seem to be the standard for OI style contests now.

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

      Can you please explain what you did if n>=400? I didn't get the "hashing the input" part.

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

        Yes, sure! What I do for N<=400 is to actually try all ways to split the circle into an array (from 1 to N). When 400<=N<=1000, then there are some optimal ways to split the array and each of them is from 1 to 1000. So I first submitted a solution which tries to split the cirlce only from position 1 to 50. Then from 51 to 100, then from 101 to 150 and so on. This way I knew for each case which was the interval I need to look at. The only thing left was to find a way to check which case our program is being tested on at the moment. So we can easily hash the input in some way (I used rolling hash with base 1331), then we find the last few bits of the hash for each test (4 were enough here) this way:

        if(h&1) assert(0);
        else while(1) {}
        

        and then

        if((h>>1)&1) assert(0);
        else while(1) {}
        

        and so on we will finally know the hash for each test case :)

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

          I did something similar actually, but I only hashed the input when I wanted to distinguish between the last two cases. Simply summing the array and binary searching with assert(sum>=something) was enough to do that.

          I will shamelessly abuse their grader until they finally do something about it. I think I had about 40 submissions on that problem.

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

            Thank you for further spreading the awareness of how feedback can be used in this manner. I don't think there are plans to do anything about this: more feedback is always helpful for beginning contestants.

            On the other hand, to my knowledge, the coaches do read codes of most camp invitees. So actual cows be warned.

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

              "more feedback is always helpful for beginning contestants"

              There aren't beginning contestants in Platinum.

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

                With the current divisions format, a primary concern is that contestants starting in bronze/silver in DEC can reach plat by FEB / OPEN, at which point they're being considered for the Gurnseys group at camp.

                With the reduced number of contests, a contestant in these plat contests can easily have < 20 hours of 'live' programming contest experience. You'd be surprised about how many 'big cows' first reached USACO camp this way.

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

    LIES!

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

Can someone explain how to solve 1st task ? (gold division)

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

I solved the first two problems in Platinum.In the third Circular Barn problem,I used a monotonic queue DP solution(which I proved,maybe proof was wrong or stupid bug) to improve the time complexity from O(KN^3) to O(KN^2) but got wrong answer.I'm surprised O(N^3) can pass...

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

    The dp which I used is like that, dp[i] = i<=j min(x[j] + y[i] + z[j] * i)

    How did you optimize it to O(KN^2)?

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

      My DP was like this:

      f[i]=min{f[j]+z[j][i]} (j<i)

      where z[j][i]=sum(r[k]*(k-j)) (k=j..i, r[k] is the number of cows in position k)

      For any x<y, z[x][i+1]-z[x][i]>z[y][i+1]-z[y][i] (in fact the difference is (y-x)*r[i+1]). So with i increasing, if x is worse than y at some point,it will never be better than y.So we can use monotic queue to optimize the DP to O(KN^2).

      This is the main idea of the solution.Maybe it's very wrong.Or just bug in implementation.I don't know.I stress tested it against a bruteforce but can only find error when n>200 so I can't debug it.

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

        Why does "So with i increasing, if x is worse than y at some point,it will never be better than y." mean you can use monotonic queue? For example you can use divide and conquer optimization with this observation but how can you use monotonic queue?

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

          I think I know why it's wrong.With this observation we can only prove decisions removed from the queue will never be optimal but can't guarantee the best decision is at the front of the queue(i.e. the queue is actually not monotonic).In the contest I didn't think about this.Could you describe how to use divide and conquer optimization?

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

            What you're doing is called convex hull trick.

            it's not necessary optimal decision is in front of queue, but optimal decisions will be always increasing in index so you can still use queue and achieve O(kn^2)

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

            You can search it on Google. Also you can use convex hull trick for this problem.

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

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