chrome's blog

Topcoder Single Round Match 689
By chrome, 9 years ago, translation, In English

Hi there!

Tomorrow at 19:00 MSK will be held Topcoder SRM 689.

Let's discuss problems after contest!

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

Comments Comments (41)
| Write comment?
»
9 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I get "sandbox returned nonzero (137):" on my old submissions. What does this mean?

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

Login timeout repeteadly on topcoder web arena. Anyone else facing the same problem ?

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

    yeah, neither web arena works nor the applet.

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

What is the idea for div1 500?

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

    Assume we can build a relation with exactly X invariant subsets on first N elements (call it (N, X) pair). If so, we can build the (N+1, X+1) pair (here N = 4):

    xxxx4
xxxx0
xxxx1
xxxx2
40123

    ... and (N+1, 2X+1) pair:

    xxxx4
xxxx4
xxxx4
xxxx4
44444

    Now you should run a simple DP which shows you which (N, X) pairs are reachable (starting with (0, 0)). It turns out that N=17 is sufficient.

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

      Thanks! Nice solution! But still confused about this, how do you guys come up with the idea that building the good set incrementally to exactly: x + 1 and 2x + 1, is there some intuition or have you just done similar problems before?

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

        For me, it was just intuition. I tried several constructions which didn't succeed. Then I decided to build a solution incrementally. So, if I can do X on N elements, how can I use the next one? I can deeply tie it with other elements (almost not increasing number of subsets) or I can make it almost independent of others (doubling the number of subsets). I ran a simple python script to check if each number is reachable this way, and it turned out to be a solution.

        Actually, if you consider an empty subset, like many participants did, it is a quite standard idea of representing X in binary and juggling with bit representation. I think most contestants came up with the idea that way.

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

          After representing X in binary I ended up with an uglier construction. Let's say P is highest bit of X. We'll take a set of P elements with f[a][b]=b, so each subset of this set is good. Also we'll add 1 "bad" element, such that f[i][bad]=i+1, f[bad][bad]=0, so taking bad element forces us to take all set. This set will discard missed empty subset — right now we have exactly 2^P good subsets.

          Now for each next '1' at position i in binary representation of X, we'll add one more element which will give us 2^i good subsets. In order to achieve this, we'll say that f[j][new_element]=new_element for j<i (so we can take any subset of first i elements plus our new element), and f[j][new_element]=bad_element otherwise (so if we'll take some other element — we'll be forced to take whole set, and such subset has been counted already).

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

          Thanks, brilliant!

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

    First, I'd say take the empty subset into account for convenience (x -> x+1).

    Now, if we have a solution with n items and s subsets, we can do two steps:

    1. Make a solution with n+1 items and s+1 subsets. For example, if 0...n-1 are old elements and n is the new element, make n$0=1, n$1=2, ..., n$(n-1)=0. And n$n=0. This way, whenever we take the new element into our set, we have to take all old elements as well.

    2. Make a solution with n+1 items and s*2 subsets. For example, if 0...n-1 are old elements and n is the new element, just make n$i=n for every i. This way, every old set S can now be duplicated as S+{n}.

    Initially, we have 0 items and 1 subset (empty set). All that's left now is to construct x from 1 using operations +1 and *2. Clearly, if we consider the binary representation of x, we won't have more than 10 of each operation, so n will be no more than 20.

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

    Assume that the empty set is a good subset (so we are looking for a set with x+1 good subsets)

    • If you are given a set with n elements and x good subsets, can you construct a set with n + 1 elements and 2x good subsets?

    • If you are given a set with n elements and x good subsets, can you construct a set with n + 1 elements and x + 1 good subsets?

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

    EDIT: Codeforces was slow when I posted this so it came out completely garbled. Just read Gassa's comment above.

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

    Suppose we have table of size n and answer x.

    Let's build table of size n + 1 and answer 2x + 1: f(p, n) = f(n, p) = p. It is easy to see that we can add element n to any good set and it remains good, and we have new good set {n}.

    Let's build table of size n + 1 and answer x + 1:

    Unable to parse markup [type=CF_TEX]

    . It is easy to see that the only good set with element n is set {0, 1, ..., n}.

    Now we can solve the problem recursively: - x = 0 — empty table -

    Unable to parse markup [type=CF_TEX]

    — solve for (x - 1) / 2 -

    Unable to parse markup [type=CF_TEX]

    — solve for x - 1

    The size of the resulting table will be no more than .

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

    duplicate, CF sends my comment twice

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

Is there any test case that everybody have missed or there is some error with the judge? As everyone failed div2 250.

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

    Some bug in the system tests, there was a notification about it.

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

OMG, I've just realized that in the "Batch test" output one should look not on the "Success: true" line, but on the "Correct example: false" :( I've just screwed up my 500 because of that...

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

    LOL happened with me once, didn't happen again ever.

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

    Oh, tell me how to use it! I use KawigiEdit, but today I couldn't easily test any problem at all. I once tried wrong solution at batch test and thought it just didn't work.

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

      You save your solution, compile it and press "batch test". After that you carefully check that each test is passed by looking on "correct example" line (but not on "success" line!)

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

Could anyone explain their solution for Div2 1000 ? Thanks.

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

    I solved this problem using dp and bitmasking. My DP table had two states, one for mask and other for the alphabet last placed. I stored the count of "available" alphabets in temp array. Dont count those for which mask is 1 as they have already been used. Now loop over alphabets for which temp[alphabet] is positive. Find any position i in first string which matches current alphabet and make sure that alphabet in forbid string at index i is not equal to alphabet which is being considered in the loop. Also check that alphabet last placed ( it was passed in recursion and is 2nd state of dp) is not equal to the alphabet you are considering now. If all conditions are satisfied proceed further with recursion. Here is the code code

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

How to solve div1 1000?

I tried 10000 times randomly rotate, then sort, then connect consecutive from left to right, and choose the best option — but it fails.

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

Could anyone explain the solution for Div2 1000 ? Thanks in advance.

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

How to Solve Div2 1000 ? Thanks in advance ...

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

Div1 should go like this. Firstly from wolframalpha learn that 0.636 ~= 2/pi. Then note that 2/pi is expected absolute value of sine function, so if we pick a random line (angle chosen uniformly) expected value of summed length of given matching's projections to that line is 2/pi of its original length. We need to find that line (random should be ok I guess) and produce nonintersecting matching of length at least summed length of those projections. We may divide those points to left and right part as their projections are ordered on that line and find any nonintersecting matching between those parts. Nonintersecting bipartite matching on a plane can be done by for example hungarian (we use minimum cost matching to find matching of sufficiently high length — ironic, isn't it :)?), but there are also many other ways.

Beatiful problem :).

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

    Actually, we don't need to take that line from random solution. We do not need to find it at all. We just need to produce all possible divisions to two halves. Moreover only such halves that can be separated by line. There are n such divisions and we know that one which will be also determined from that good line will produce sufficient solution. That solution do not even need initial matching, it produces matching of length

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

      According to http://www.tau.ac.il/~nogaa/PDFS/noncros.pdf (which I've used during the contest :)), it's well-known that there are o(n^3/2) such partitions, not <=n.

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

        In fact you can get that direction in O(n log n). Hint: the match you need to beat is given.

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

        Did you know this solution prior to the contest? Have you seen this paper before? Or did you just use good search-engine skills to find something that could solve the problem?

        (I'm asking because I would like to know when it is a good approach to stop thinking about a problem and just google it, especially in an SRM... this could save a lot of time)

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

    I submitted a stupid greedy algorithm in honor of your success in SRM 688. Seems like it doesn't work when I do it :P

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

      It looks like all kinds of heuristic algorithms should be broken with regular 200gon with main diagonals or with "almost main" diagonals. But not to make you sad, I also submitted a heuristic solution and failed systests ;) (second time in a row I was 20min late (but this time it was not TC's fault), but I don't think I would have been able to do this problem even if I wasn't be late)

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

    And one note more, minimum cost matching can be omitted. Since there is line separating parts we can always take two points from different parts which are neighbours on convex hull, match them and recurse. That leads to O(n^3) in total. Combinatorial geometry FTW :)

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

      Hello, may I ask a question about the realization of Div1 1000?

      It's that how to divide points into two sets.

      In tester's solution, he just iterate through all pair of points (i, j), where i, j is their id, and divide all other points into 2 sets using cross product. But the code writes something like:

      for each point pair (i, j) of original point sets
  left.add(i); right.add(j);
  for point k other than i and j
    if(ccw(i, j, k) ^ (i < j)) left.add(k);
    else right.add(k)

      I understand that ccw, but what's the point of xoring an (i < j)?

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

        It is the same as ccw(min(i, j), max(i, j), k). Probably he wants to check the orientation of the ordered (i, j) pair.

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

I don't know where I went wrong in div 2 500 pointer. Can anyone explain his approach ?

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

    You need to consider every possible substring from A with length same as B. Then check whether the substring is a possible match with B. A substring will not match with B if for any index i, substring[i] != B[i]

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

My screencast

→ Reply