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

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

The USACO November 2013 contest has began. Link

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

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

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

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

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.

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

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

Is it like div2 or div1 or in between ?

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

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

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

    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.

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

    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.

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

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

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

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

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

    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

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

    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.

    • »
      »
      »
      11 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится -9 Проголосовать: не нравится

      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.)

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

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

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

    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.

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

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

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

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

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

        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).

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

    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.

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

      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")

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

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

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

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"

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

any hints for third problem gold?

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

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

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

      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

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

        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.

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

        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

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

    My bad. It is a wrong solution. :)

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

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.

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

    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.

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

      But difference between hard and medium problems was too huge.

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

        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.

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

          Who knows? may be...

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

          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".

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

            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).

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

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

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

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

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

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

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

    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.

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

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

    for(int i=0 ; i<m ; i++)
    
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

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

        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.

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

          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.

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

          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.

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

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

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

Подскажите, кто-нибудь как решалась задача В бронзового дивизиона. Есть видео разбор на английском языке. Трудно разобрать все тонкости не зная языка. Может кто объяснит решение на русском доступном языке. Заранее благодарен.

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

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" :)