Lewin's blog

By Lewin, history, 7 years ago, In English

Didn't notice a post from cgy4ever.

Topcoder SRM 718 will happen in ~4 hours.

Tim: 9:00pm EDT Wednesday, July 12, 2017

Calendar: https://www.topcoder.com/community/events/

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

»
7 years ago, # |
  Vote: I like it +35 Vote: I do not like it

I was the author of this round. You can see some short explanations here:

div2
div1
  • »
    »
    7 years ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Why such a big size in d1-250? I got tle just because I used the map instead of an array...

    Edit. I just checked that |si| <= 1000 would fit within time limit, yet the incorrect O(n^3) solutions would still tle. I really don't get a point in such a huge string size...

    Edit2. Ok — my bad, looks like some O(n^3) solutions might have passed or maybe my test was too weak. Anyway sad that I failed that task. True story is that even though I had O(|s1|*|s2|) solution, I stored a third parameter in the map. After the contest I realized that I do not need this parameter and hence I can use an array, without changing logic...

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

    CircleCity for n ≤ 200 000.

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

      Maybe it's quarterly true, though, I think you should return CircleCity to the problem of Zeptolab's (it means if you solve CircleCity you can solve Zeptolab's if the constraints are same, but not vice versa). Because CircleCity is "placing k teleporters" and after a few ideas it can return the problem of "for given cycle graph you can erase atmost k edges, what is the maximum length of component?". After that it is easy greedy + binary-search because n ≤ 2000, so maybe it is not a main part. And also, Lewin already solved this Zeptolab's problem.

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Any hints for 1000 pointer?

I could prove that for f(P, k) = C(n, k) we must have difference between adjacent elements of P ≥ n + 1 - k. But it seems it is not a sufficient condition.

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

    Your condition is close, but you also need to consider nonadjacent elements. More specifically you need to look at this expression

    spoiler
    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      Is this condition

      Spoiler

      Otherwise, what would you do to compute g(arr)?

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

      How to prove this?

»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

jiry_2's color is red in yellow..., so mysterious! I think it's a bug, right? (His topcoder rating is 2808)