cgy4ever's blog

Topcoder SRM 708
By cgy4ever, history, 8 years ago, In English

Topcoder SRM 708

Time: 7:00 am EST Thursday, February 9, 2017

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

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

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

And all room winners get T-shirts: https://www.topcoder.com/blog/a-flood-of-love-hits-the-topcoder-community/

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

    Did anyone receive their shirts for SRM 701?

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

    Even for Div2? Why am I in Div1 :(

    And I ended up second in the room.. RIP all who came second in room

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

    I'm lucky :) Do I just have to set my address in the settings? What about T-Shirt size, didn't find any setting?

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

      I don't actually send out the t-shirts, I just follow the news related to them :-) But you definitely have to set your address in your profile.

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

Contest will start in 36 hours!

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

Hour

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

Please, Someone explain his solution for Div 1 250 :)

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

    My idea is to use only 3 characters to support up to 15 strings Like this: a, a ... a, bcbcbc....

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

Solution for 500 ?

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

    I used three DPs:

    • dpOut[i][j] means count of palindromes in substring (i .. j),

    • dpOutReal[i][j] means count of palindromes in substring (i .. j) which strictly have ith and jth characters.

    • dpIn[i][j] means count of palindromes in subsequence (0 .. i); (j .. n-1).

    Then, we choose i for which we want to calculate x[i]. Where can it be in the palindrome. Imagine the palindome:

    abcdedcba
      ^

    Let the last c will be our ith character. So, the inner part of the palindome will be cdedc (it will have our ith element as one of its ends) and the outer part of the palindrome will be ab ba

    So, let's iterate all possible inner parts. Let the beginning of inner part will be the x character, and the ending of inner part will be y (it's easy to see that x = i or y = i).

    Now, for that inner part there will be dpOutReal[x][y] and to choose an outer part for it we will use dpIn[x-1][y+1] + 1 (+1, beacuse we can have no outer part). Now, we'll add to x[i] dpOutReal[x][y] * (dpIn[x-1][y+1] + 1)

    → Reply
»
8 years ago, # |
← Rev. 5   Vote: I like it +84 Vote: I do not like it

WINNERS: rng_58, tourist, Petr, anta and Baklazan. Congratulations guys!

my codes: div2, div1-easy BalancedStrings, div1-med PalindromicSubseq, div1-hard OptimalBetting

div2-med: greedily try to insert strings with as big score as possible (but don't exceed the value of K)

div2-hard: dynamic programming in O(n2). Let dp[i][j] (i < j) denote the number of ways to choose subseqeunces of indices on the left from i and from the right from j so that they will be symmetric. At the end answers are dp[i-1][i+1] or something like that.

div1-easy: First string can be ABABABAB..., the second CDCDCDCDC..., and each of other strings should consist of one letter only (from 'e' to 'z'). You can check that two first strings produce enough "instability".

div1-med: Two dynamic programmings: from inside and from outside. Let dp_out[i][j] denote the number of ways to choose indices on the left from i and right from j so that they will be symmetric, and let dp_in[i][j] denote more standard dp: the number of palindromes in the interval [i, j].

div1-hard: It turns out that the probability of getting to the goal amount of money (when playing an optimal strategy) depends on rounded value of . A naive approach to the given problem is O(goal2·k) dynamic programming. The key observation is that values close to each other in one "interval" (interval defined by the same value of probability of winning in optimal strategy) have similar sets of optimal bets. If you divide numbers from 1 to goal into 2k "intervals", for each previous amount of money the set of good (got from optimal bets) new values in one "interval" is a smaller interval itself. A related fact mentioned earlier: the set of optimal moves from a and from a + 1 (where a and a + 1 are from the same interval) differ only by constant number of elements.

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

    I think you have a typo in your div2-hard explanation:
    "left from i and from the left from j"
    should be from the right of j

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

    Why greedy works in Div2-med? What if we run into situation where we used 49 strings and we still need the score 53 (or any other prime number  > 50)?

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

      The biggest possible score of one string is 26·50 = 1300. You can use it at most times. After using some multiply of 50 in the next string the remaining needed score will be less than 50 (otherwise we would use a bigger multiply of 50). Note that we can use a string with score that is not multiply of 50 but it can only make things better. Finally, in one more string we can get exactly the remaining needed score because it's less than 50.

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

        Note that we can use a string with score that is not multiply of 50 but it can only make things better.

        Thank you! I understood the first part with multiples of 50, but I couldn't understand why using a different number makes things better.

        For example, this code doesn't use multiples of 50 as the last step. I thought that he was lucky before I saw that note. Does this code exhaust the K in the same way you've described?

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

          We can use strings with scores that are not multiplies of 50. It's a possibility, not an obligation. An extra possibility can't make things worse. I don't claim that it's useful though.

          That code uses big multiples of 26 and squares of numbers smaller than 26. It's slightly more complicated to prove its correctness but it indeed achieves any allowed K in at most 50 moves. You can analyze it this way: once you start decreasing a variable len, how big can K be in the next step? And how big can it be in yet another step?

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

REPORT

Admin please have a look into this http://imgur.com/CHav3o4

PS: I would like to know to how add a pic in a comment.

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

    Maybe this is what you wanted :



    EDIT: Seems YoScienceBitch is here to stay RankList

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

      I pity YoScienceBitch for having slow internet connection.

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

        Maybe he thought that submitting 20-30 seconds later will make him look any less suspicious.

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

Can someone explain Div2-Hard in more detail? I don't completely understand the above explanation.

Thanks

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

    Let dp(L, R) denote the number of palindromic subsequences you can choose in the range (0,L) U (R, N-1).

    For each i, you need to calculate dp(i-1, i+1).

    Now the recurrence relation. Divide it into cases.
    Suppose you are at state dp(l,r) and decide to neglect str[l]. Then you move to state dp(l-1, r). If you reject str[r], you move to dp(l, r+1). Add both of these. But this induces double counting, i.e. when you reject both str[l] and str[r]. So subtract dp(l-1, r+1) from the answer.

    Also, when str[l]==str[r], you can choose both and go to state dp(l-1, r+1), so add this value whenever applicable. :)

    To sum up,
    When str[l]!=str[r], dp(l,r) = dp(l-1,r) + dp(l, r+1) — dp(l-1,r+1)
    When str[l]==str[r], dp(l,r) = dp(l-1,r) + dp(l, r+1)

    → Reply