i4018's blog

By i4018, history, 7 years ago, In English

The second USACO contest of the 2016-2017 season has started and will end on Jan 16 at 23:59 UTC-12 time.
Let's discuss the problems here after the contest :)

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

| Write comment?
»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Bringing it back to recent actions

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

Is it possible that I submit my solution even thought I have already competed for 4 hours? Of course this submission will be out of competition.

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

    Contest has ended. No further submissions allowed.

    This sounds convincing, I think. You will be able, but after the contest ends for everyone.

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

How to solve "Building a Tall Barn" and "Subsequence Reversal" from Platinum?

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

    Wait until 16:00 UTC today when the contest ends for everyone.

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

      Really sorry. I thought contest has already ended since it marked ended in clist.by.

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

        This is something repeated every contest... opened an issue for it there.

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

        Its still on for me, I got 10 minutes left :P Got AC on problems 1 and 2 only :/

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

    I was trying this for the third one (couldn't debug in time, ended up with 6/10): note that instead of saying "reverse a subsequence", you could say "select a bunch of pairs of indices such that for any two pairs one of them is contained within the other and swap the values of each pair". Now let DP(l, r, p, q) denote the answer of the subarray (l, r) given that the lis lies within the range (p, q). From (l, r) you can go to either (l+1, r), (l, r-1), (l+1, r-1), or swap a[l] and a[r] and then go to (l+1, r-1).

    Did anyone get ac with this approach?

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

      Yes, I did.

      You can calculate each state in either O(n^2), O(n), or O(1). Anything faster than O(n^2) works, but I did it in O(1). Also, I did it recursively, and I'm sure than a huge number of states were never reached in the computation.

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

        I did it in O(n^2) and get full score. Less than 1 sec in max test. How did you manage to compute the dp in O(1)?

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

          I was computing the transitions in O(1). DP(l, r, p, q) is the maximum of the following values:

          • DP(l, r-1, p, a[r])+1 if a[r] lies in range [p, q]
          • DP(l+1, r, a[l], q)+1 if a[l] lies in range [p, q]
          • DP(l+1, r-1, a[l], a[r]) + 2 if p<=a[l]<=a[r]<=q
          • DP(l+1, r-1, a[r], a[l])+2 if p<=a[r]<=a[l]<=q
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yup, I basically did it like this too.

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

            You've forgotten about the two cases where we do swap the values a[l] and a[r], but only use one of them in the sequence, e.g.:

            • DP(l+1, r-1, p, a[l])+1 if a[l] lies in the range [p, q]
            • DP(l+1, r-1, a[r], q)+1 if a[r] lies in the range [p, q]

            An example of such a sequence would be 3 1 2 100 4 5 6 7 8. Swapping the 3 and the 100 will give you an optimal sequence of length 8.

»
7 years ago, # |
Rev. 7   Vote: I like it +6 Vote: I do not like it

How did you solve 2 (platinum). I did this with n ternary searches inside the binary but it TLE, because it was . After some thinking I removed the ternary and replaced it with a derivative so the final solution became . It passed but I wasted like 2.5 hours on this. So my question is. Is there an easier solution (or actually what is the easy solution)?

code: http://ideone.com/ojPGlI

PS: sorry for the early post

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

    FFS I WROTE IT JUST ABOVE, 16:00 UTC, DO YOU NOT HAVE A CLOCK ONLINE?!!!1!

»
7 years ago, # |
Rev. 6   Vote: I like it +34 Vote: I do not like it

My solutions, short:

platinum 1
platinum 2
platinum 3

UPD: I see a lot of downvotes. CF comments as usual.

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

    They are probably because your spoilers were empty until a couple of minutes ago. I like your solutions, but don't understand what you're saying about the first problem. Why would you need anything that has anything to do with HLD?

    My solution was with the "merging sets" trick, but a set can't answer a query "how many numbers are there smaller than x" so I essentially made n segment trees and for each vertex merged the segment trees of its children.

    EDIT: removed second solution, I got something wrong;

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

      Lol why would I post solution when the contest was running? :D And I did say "short". Very, very short. But I got a lot of downvotes after they weren't empty.

      I call it HLD trick because you're basically building BITs over HLD, although not building or using the HLD paths directly. You can do the same with segtrees and with BITs, but you need to build them first, in that precomputation pass, and then, you can merge only the elements from the trees for the smaller sons into the largest one.

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

        Okay, I get it now, thank you. :)

        We basically did the same thing, but I didn't precompute these paths. Instead every vertex chose its biggest child's tree as its own, and merged all the other seg-trees into it.

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

    After flattening the tree, problem 1 can be solved with a merge sort tree. We keep a vector in each node of a segment tree that contains the relevant range sorted. For querying, we can binary search in current node to find the count of numbers greater than some x. Space and time .

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

    I realized that if k was small, the greedy algorithm above did not work. So if k <= 10^7, I set all b[i] = 1, otherwise I did the above algorithm, and it got AC.

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

    Problem 1 can be solved much simpler in O(NlogN).

    • Do a DFS and store the preorder of each node, then every subtree will be contained in a contiguous range.
    • Now the answer for a node i will be the number of elements greater than Pi in the range [lefti, righti], where lefti and righti are the in and out times of the preorder traversal for node i.
    • Process the nodes in reverse order of Pi and maintain a list of nodes already processed. After processing a node, we add 1 to position lefti. Queries can be done fast with a BIT.
    Here's source code
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, good point. What I wrote was just the first thing that came into my mind.

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

        please, be careful in future for telling these "first things"

»
7 years ago, # |
Rev. 3   Vote: I like it +25 Vote: I do not like it

For tallbarn, you're given a sequence a and asked to minimize the sum subject to . Suppose . We have a lower bound from a consequence of Cauchy-Schwarz inequality, mostly known as Titu's lemma (I wrote an article here)

$o$ with equality when for some constant t. But implies . So we can set and achieve the minimum value . But bi values have to be positive integers, so the sequence b has to be adjusted. First off we should make all bi < 1 equal to 1.

At this step I greedily adjusted the sequence in two ways and took the minimum.

Firstly I replaced bi with bi for all i. Then the new total sum is less than k and the target value has increased. We can add the extra values in a way that the sum will be minimized. If we add 1 to bj for some j then the sum decreases by

.

so pairs (ai, bi) get priority based on this value. We can add all pairs in a priority queue, keep increasing top elements and push them again till again.

Secondly, I replaced bi with bi for all i and did something similar to above. This time the sum will be greater than k and we can delete extra values keeping another priority queue.

Finally take the minimum from these two adjustments.

Code: http://ideone.com/gItN6P

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it -12 Vote: I do not like it

    .

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

    Actually, in reals, with the constraint has its minimum at from Lagrange multipliers (or simply taking derivatives when all but two variables are fixed).

»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

I use Simulated Annealing method on third task and get OK :)

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

    How does it work here?

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

    I like your idea, you didn't bother in implement lis in O(nlogn) :) Nice approach. +1

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

    Can you explain your method in a bit more detail? I haven't heard of simulated annealing, and would like to learn more about it.

    Also, what sorts of problems does one use simulated annealing on?

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

      when n is small and you need to minimaze/maximaze some function you can use Simulated Annealing method. like this task

      i know only where to read about this method in russian, sorry:( i think you can google it and find some information about it.

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

In P2, you can solve with binary search.

Define f(x, i) to be the time you can cut off if room i currently has x cows, and you place one more. Then . You can binary search D such that all rooms have f(x,i)<=D, which you can solve with some quadratic formulas. Complexity is O(n log K)

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

    Your LaTeX is slightly messed up.

    Anyways, what I really wanted to say, your username is really nice, especially appropriate for the tree problem you proposed P1 for the USACO contest. (Is it you?)

    BTW, to whom you send nodes?

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

      No, that guy is some doppelganger who wants to take my name. Really, i am just some poor guy who just sends nodes, particularly segtree ones because low cost :)

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

    How do you make sure the sum of the x's is equal to K?

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

      That's the transition of the binary search: if sum of x's is more than K, try higher differences, else try lower differences.

»
7 years ago, # |
  Vote: I like it +17 Vote: I do not like it

If I'm not mistaken I've achieved in Platinum 1.

First, I compressed values in interval {1, ...N}. Then, put all nodes with their discovery time and finish time in one array, along with values of nodes, and sorted them by position. Finally, by iterating through that array and updating BIT, made solution for every node.

Code.

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

Does this work for platinum 1st problem?
Firstly build eulerian tour over tree. Now sort cows by p. Answer for cow v is (sum on segment [l[v], r[v]]) / 2, and after that add position l[v] and r[v] 1.

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

Is there any way to submit now? I optimised P2 a bit but time was up!!

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

    After the results are published, problems are moved to practice.

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

Where can I find problems? http://usaco.org/index.php?page=contests have only problems till first contest

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

    Read the comments here before asking.

»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it