sweiss's blog

TopCoder SRM 594...
By sweiss, 11 years ago, In English

...starts in an hour. You're welcome!

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

Comments Comments (12)
| Write comment?
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Anyone failed to log into the arena as me?

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

How to solve 550-problem?

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

    For example you can reduce it to project selection problem, where white pieces are projects and empty cells adjacent to them are equipments.

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

    It is equivalent to finding minimal vertex coverage in bipartite graph with on '.' and 'o' with edges between adjacent cells and answer is {number of '.' and 'o'} — {coverage size}.

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

How to solve 950? All people who submitted it have bugs?

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

    I believe I had an almost correct solution, though I couldn't debug it in time.

    We can notice that it's always better to leave fewer cells after the chosen one. So, DP: dk, x~--- minimal number of cells left after k moves if the chosen cell ends up in position x. The transitions are clear: we must take all possible rectangles not containing the chosen cell and very carefully count how many cells before and after chosen cells they contain. We can reduce number of transitions to O(n) via moving rectangles to some border when possible.

    It suffices to notice that four moves are always enough to win. So, this solution is O(n2).

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

Can someone help me with Div2, 500 ?

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

    Look at this thought:

    If you have some i,j such that planet corresponds to A[i] is exact same planet that to B[j], then there are have to be some ratioA and ratioB such that ratioA*A[i] == ratioB*B[j]. Lets put all elemets of A multiplied by ratioA to setA <- ratioA*A[i]. And do the same for another array: setB <- ratioB*B[i].

    What you want to do? You want to find such ratioA and ratioB that merged-set ResultSet = Merge(setA,setB) have the smallest possible size Size(ResultSet) -> min.

    Since size of A and B is not more than 50 elements per each, you can check wise ratioA and ratioB for all i and j for O(n^2) and find size of ResultSet in O(n) [or even in O(log n), if you would use binary check of presence, which is not so important, but still is fun].

    So what ratioA and ratioB would be wise to choose for some i and j? Of course, ratioA = LCM(A[i],B[j]) / B[j] and ratioB = LCM(A[i],B[j]) / A[i].

    Final estimate is O(n^3) [or O(n^2 log n)].

    Cheers.

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

      Thanks a lot. I was heading in a similar direction initially, but I couldn't solve it. Thanks again :)

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

Editorial (Part 1)

→ Reply