BackendDeveloper's blog

SRM 585
By BackendDeveloper, 11 years ago, In English

Today at 11:00 AM EDT will SRM 585. Lets discuss problems here after end of the contest.

Tags srm, 585, tc
  • Vote: I like it
  • +50
  • Vote: I do not like it

Comments Comments (26)
| Write comment?
»
11 years ago, # |
← Rev. 2   Vote: I like it +14 Vote: I do not like it

Updated compilers and added Python compiler!

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

    But they failed to provide it during contest time. Hope good luck for next time.

    I coded in c++ and have +220. Feeling WOW!!

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

(ignore)

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

Who can't see pictures?

UPD: fixed, sorry.

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

In Div1 250 the answer is [(2^(N+1)-1)/3] +1*((2^(N+1)-1) % 3 !=0). However everybody in my room got something like dp solution. What's the logic of dp solution here?

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

    It is easy to see that you need send car from left leaf to second left, from third left to fourth left, and so on. So, two bottom levels are removed, and repeat.

    UPD: And so we have something looks like

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

      I had the same thoughts, but derived formula instead of doing easy calculation with arrays :(

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

      Yeah, I did the same. That was my quick idea I got from the example tests' pictures.

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

    its dp[0]=1; dp[1]=1; for all i=2 to n dp[i]=dp[i-1]+2*dp[i-2];

    its Jacobsthal sequence sequence http://oeis.org/A001045

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

    Alternatively:

    If you run one car from the leftmost leaf to the rightmost leaf of the tree, what's left is a sequence of pairs of smaller trees with heights 0,1,..,treeHeight-2.

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

When I run applet it always unable to launch. I go to topocder but the page can't be access. I can only launch applet at half of contest and in challenge phase I was kicked out of applet. Anyone tell me it topcoder's error or my network's error?

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

oeis is your friend as well :)

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

can someone explain how to solve DIV2 1000?

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

    step 1 . choose 3 color

    step 2 . choose 1 point for each 3 color O(n^3)

    step 3 . check them . if this triangle covers black points increase ans ;

    in step 3 if u dont know how to check any point is inside the triangle trick is if any pair of points in triangle (p1,p2) if ccw(p1,p2,p3)!=ccw(p1,p2,point) point is outside else inside

    more eficient way is choose 2 points and use binary search for 3.point or another way is for each pair of colors find pair of points that not divides black points O(n^2)

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

      Do you mean that complexity of your solution is O(number_of_black_points * m^3) ?

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

        no there is a paragraph that explains eficient solution.

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

      can you plz expalin this condition : ccw(p1,p2,p3)!=ccw(p1,p2,point) What is CCW ?

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

        CCW means counterclockwise.

        ccw(p1,p2,p3)!=ccw(p1,p2,point) means that the arcs p1-p2-p3 and p1-p2-point do not rotate in the same direction.

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

    Here is another algorithm in O(MMN). I observed that for all valid triangles, two of the three pairs of the vertices are chosen from the two perpendicular sides of the M*M square. Thus we can count them by going through all pairs of the two vertices on the sides colored (R, G), (G, B), (B, Y), (Y, R). For each pair, we can check if it can contain all the points in O(N) and also count the number of the possible third vertices in O(lgM) by using binary search to find the boundary of the possible third vertices on the other two sides of the M*M square. So in the end, the total needs to be divided by 2, because we double count each triangle.

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

Div 1 500 was a quite interesting DP. Unfortunately I couldn't fix my bug in time (2 lines misplaced T T).

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

Help me please. I was participating from my PC, but then electricity fell down. I took laptop, but arena wasn't working on it. It says "Unable to launch the application". What is the reason of problem?

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

    Yesterday I had the same problem. I've cleaned java cache (found this tip at topcoder forum).

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

Nice problems ! :D

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

I'm not sure, but I think another recursion that could be found is an = 2n - 1 + an - 2. It gives the same result as the other recursion.

My approach to find this recursion was to use one car for each of 2n - 1 binary trees of height 1 at down of tree, so the tree without them would be a binary tree with height of firstHeight - 2.

Can someone mention the idea behind using Jacobsthal sequence in this problem, or it's just a consequence?

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

Editorial

→ Reply