Kaga2s's blog

The USACO November 2013 contest
By Kaga2s, 11 years ago, In English

The USACO November 2013 contest has began. Link

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

»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Thanks for reminding!!!I almost forgot about it.

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

Right on it... wait, it's 4 hours not 3. Crap. I though I'd get more practice before CERC, but I'd miss the train like this.

Oh yeah, major offtopic: this Sunday, CERC takes place.

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

Can anyone tell me what is the level of this contest ?

Is it like div2 or div1 or in between ?

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

    When you start, you're in the bronze division. It's like B-C div2 problrms.

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

    It has 3 divisions Bronze, Silver and Gold, each of them getting harder. If it is you first contest you need write Bronze, otherwise in division at what you was last year.

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

    Maybe some will not be agree with me, but the level is kind of random for me... Some contests are a lot harder than others, even in the same division. This month, it seems the easiest contest since a long moment, and it's like Xellos said, "B-C" div2. But I will say it's more D div2 for third problem usually.

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

ads everywhere in USACO :(

Edit: I'm very sorry about this , it turned out that I'm only the one who is seeing the ads maybe there's a virus on my computer , I'm seeing flash ads and some word being a green linked if I hover on them it will open ads here's screen shot of some websites

USACO:

http://store2.up-00.com/2013-11/1384809729661.png

codeforces:

http://store2.up-00.com/2013-11/1384809729842.png

spoj:

http://store2.up-00.com/2013-11/1384809729943.png

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

    Really? I didn't have any. Just a slow server and one "Judgement failed".

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

Is there any neat solution for the second problem in Gold?

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

    I was able to start just 45 minutes ago and I think it is still possible to start, so you should refrain from discussing problems for about 4 more hours

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

    It should be fine now.

    For each cow C, partition the area in which visible cows can be (given by the circle and tangents to it from C, non-white in the pic) like this:

    The number of cows in the gray area can be found by angle-sorting the points and doing prefix sums. The numbers of cows in colored areas are given by the tangent points on the circle and orientations — list all those tangent points, then angle-sweepline the answers for them. Ugly stuff.

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

      Upd: Contest is over, solution on pastebin (basically the same idea as scott_wu's)

      (I think I've had enough of Codeforces comments now.)

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

        The contest should be over. And if you can't make sure your contest ends when it's supposed to, it's unfair anyway.

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

    I thought the problem was quite nice. Here is my solution:

    Each cow forms two tangent points with the circle. Consider the minor arc on the circle formed by those two points. It turns out that two cows can see each other if and only if their arcs intersect.

    Therefore, we can just calculate the range of angles possible for each cow and solve the well-known problem of counting the number of pairwise intersections in a set of ranges (we need to be careful to handle the fact that the ranges are cyclic though). The total runtime is O(NlogN) since we must sort the list of angles.

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

      That's exactly what I've been looking for! Thanks a lot, Scotty ;)

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

      is there a neat way to find the coordinates of the two points where the two tangents touch the circle?

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

        Yes. If you look at the radii of the tangent points as in Xellos' diagram, you can see that the points of tangency make angles of acos (r / R) with the location of the cow itself (r is the radius of the circle, R is the distance from the origin to the cow). We can find the angles of the tangent points by finding the angle of the cow (atan2 in C++ works great here) and then adding and subtracting acos (r / R).

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

    I have a solution which is a bit more motivated than the one presented by scott_wu.

    For each cow, there is a region it can see: it is bounded by the silo as well as the two tangent lines. The entire half-plane above the upper tangent line is visible, and similarly, the entire half-plane below the other tangent line is also visible.

    In fact, we can simply add up the number of cows above the first tangent line and the number of cows below the second tangent line. Although this doesn't include the region between the cow and the silo, it also double counts the intersection of the two half-planes. Taken together, these two imperfections cancel out.

    Because each pair of seeing-cows is counted twice, you simply divide the total sum by 2 at the end.

    Finally, the problem is reduced to querying the number of cows in a halfplane determined by a tangent to the silo. This can then be reduced to counting the number of pairwise intersections of a set of ranges.

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

      Here is a diagram of my solution above.

      The number indicates the number of times the region is counted. Ideally, all of them would be 1, but this works too (if cow A is in cow B's "0 region", cow B is in cow A's "2 region")

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

        Actually you only need to do one of those half-planes and you wouldn't have to divide by two at the end.

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

i sent a mail to Brain Dean and answered me 45 mins ago.

"I am working on them now, and hope to have them announced soon. The contest only ended an hour ago!

-- Brian"

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

    What do you mean by "them"? Results?

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

    They usually publish results one week after the end of the contest... What do they mean by "soon"?

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

      i asked him why one week later, really even in ioi its announcing in 3 days :D

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

    Results of Usaco announced soon? Wake up man...

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

any hints for third problem gold?

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

    Dynamic programming: for each subset of coins calculate the maximum number of products that can be purchased.

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

      I don't know how to calculate the maximum number of products that can be purchased for each subset , but let's assume it can be done in O(N) for each subset so we hace complexity O(N*2^K) which is not fast enough

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

        My time complexity is O(2^K*K*log(N)).

        For each subset, we can go through every possible choice for the last coin added to the subset. Using dynamic programming we know the maximum number of products without the last coin. The maximum number of products with the last coin can be efficiently calculated using binary search and a prefix sum array.

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

        Let's say the buying works like this: we buy first i products (doesn't matter how) and next, we buy A[i][j] more products using coin number j; A[i][j] is maximum possible. This can be calculated with bin-search or 2 pointers method, if we have the prefix sums of the sequence of products.

        Now, we only need O(1), not O(N) to answer "how many products can we buy using just subset S of coins?", by trying all possible last coins used.

        Complexity O(K2K + NK), code

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

    My bad. It is a wrong solution. :)

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

      Is this fast enough? 16! is a large number.

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

i think problems at gold division was unbalanced , i have spent just a hour to solve first and third problems. After then i tried to find out solution for second problem for 3 hours.

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

    It seemed to me like easy (1.), medium (2., although a bit too easy for my taste), hard (3., still had a nice solution that hex539 and scott_wu did). That's a good thing. A bad problemset is one with 3 easy or 3 hard problems, because it doesn't give you any learning experience.

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

      But difference between hard and medium problems was too huge.

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

        Not really. The 'hard' problem just required a good idea that lead to an easy implementation, so it seemed that way. Or maybe geometry is one of your weaker points (like mine), so it just seemed really hard to you.

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

          Who knows? may be...

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

          For what it's worth, the second problem was incomparably harder than the others to some of those of us who solved it as well. Like several others I spent most of my 4 hours on "sight" but only had the "AHA" moment about 15 minutes from the end.

          That's definitely the hallmark of a satisfying problem, but also (IMO) one that isn't such a good fit for OI-style contest programming because there isn't much middle ground between "trivial brute force" and "100% correct".

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

            Splitting a problem into subtasks is well possible. It's just that the authors chose not do it. Some examples for subtasks of sight:

            • in x% of the testcases, no 3 cows will be collinear

            • in x% of the testcases, all the cows will lie on another circle (or in some other way, so that it can be solved by a simpler angle-sweeping)

            • in x% of the testcases, the answer won't exceed y / will exceed

            And it just happens sometimes that the hard problem really just has a hard idea. Reminds me of day 1 of IOI 2011 (I didn't compete back there, just read the problems).

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

    As far, as I remember, the first contest of the year is always easier than following ones.

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

I was shocked, but results are already available! Missed the perfect score because of one symbol :( Go check them out!

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

First problem... I used set&vector for solution but it got s = Signal (crashed, exceeded memory limits, invalid syscall). Is my code giving MLE?

Code

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

    Just a set and a vector shouldn't exceed the memlimit, but you can run it on your computer with all the testdata and check what it does.

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

    You never define "m", but you use it on a for loop:

    for(int i=0 ; i<m ; i++)
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, that would be a compilation error. If you look better, you'll see int n,k,m;

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

        He probably wanted to say that m is never initialized and I think he is right. There is no guarantee that m will always be 0 at the beginning.

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

          Yes, that could be it. I'm not sure how auto-initialization works in g++ for global variables (I initialize all manually just to be sure), but m initialized to a positive value could cause crashes quite easily.

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

          I changed but it got s again. But I was idiot. I coded O(NlogN) solution. I complied on my computer and there is not any problem with segmentation fault etc.

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

          Since m has static storage duration, it shall be zero-initialized.

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

Strange... two perfect scorers in gold div. One from USA, other from AUS. One from pre-college category, other from observer category. But both with same name... "Ray Li" :)

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

    Ray Li is just that good

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

    I know the Australian Ray Li in real life and I can tell you that they really are 2 different people. It is a funny coincidence :)

    → Reply