sdryapko's blog

SRM 549
By sdryapko, 12 years ago, translation, In English

Today, at http://www.timeanddate.com/worldclock/fixedtime.html?&day=09&month=07&year=2012&hour=07&min=00&sec=0&p1=179 will take place SRM 549. I suggest to discuss tasks in this post after contest finishes.

Good luck everybody!

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

»
12 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

Its the first time(I have logged in hundreds of times) I am getting this error :"Unable to launch the application" when I click on the downloaded applet file..Can anyone tell me why is this so and how to get away from it

UPD: More specifically I am getting this error: Unsigned application requesting unrestricted access to system

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

    Solution found after some googling and searching topcoder forums :

    Sol->Run "javaws -viewer" and delete all instances of the TC arena there. Then open de jnlp file again and it should redownload the TC arena after which everything should work

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

      Yep, I had the same problem two days ago and I solved it in the same way.

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

      Another solution is to go to java settings in control panel (on Windows) and remove temporary internet files.

      → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -16 Vote: I do not like it

output for this should be? (input in edit)

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

    36

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

      My greedy algo. gives 33. So, the following greedy is wrong, right?:

      take the bottom with biggest radius and smallest slope (h/r). and try to match it with largest radius top(>radius of bottom) and with smallest slope (>slope of bottom).

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

        Yes, greedy approach is incorrect.

        The correct solution is the following. Let's assume when we can make magic hat with topH, topR, bottomH, bottomR. Obviously, topR < bottomR, otherwise we either can not put hat on the top or make bottom hat visible.

        Also, topH·bottomR > topR·bottomH must be held ( this can be deduced from similarity of triangles).

        So, we can check if topi and bottomj can be combined. Imagine bipartite graph, first part is top, second is bottom. There is an edge from topi to bottomj if and only if they can be combined. The answer is the size of maximum matching (http://en.wikipedia.org/wiki/Matching_(graph_theory)) in this graph.

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

          Yes. But isn't that a overkill? I thought a greedy algo. of some sort might solve it. ?

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

            No. Because it is standart problem, where you should find maximal matching in graph.

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

              Not necessarily. This problem can be reduced to bipartite maximal matching, but not vice versa. Maybe the matching can be done more efficiently on graph of such special form. Kuhn's algorithm seems like an overkill to me too, but I couldn't find a better solution right away.

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

                See Petr's solution. As far as I understood, after sorting edges from earlier vertexes is subset od edges from vertexes with greater numbers. In that case gready works.

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

            A greedy algorithm that works is: 1) sort the top hats by increasing h/r. 2) sort the bottom hats by increasing r, then by h/r if two rs are equal. 3) go through the bottom hats in order and match each with the first unmatched top hat possible.

            → Reply