hmehta's blog

Topcoder SRM 743
By hmehta, history, 6 years ago, In English

Topcoder SRM 743 is scheduled to start at 12:00 UTC -5, December 9, 2018. Registration begins 24 hours before the match and closes 5 minutes before the match begins.

Problem Writer: boba5551

This is the second SRM of Stage 2 of TCO19 Algorithm.

Stage 2 TCO19 Points Leaderboard | Topcoder Java Applet | Next SRM 744 — December 14

Hope to see most of you competing! All the best!

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

Comments Comments (20)
| Write comment?
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

tourist already passed to finals. How his results counts in other stages? And what's wrong with sorting by total points?

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

    Sorting is based on the points currently and all the ones with the same score are listed randomly. I will add another sort key on the score to make it better sorted :)

    tourist won't be considered in this and further stages as he has already qualified. :)

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

      But he is considered for giving points in one round?

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

        Yes, but he won't be considered for advancement to finals or to Round 4. If he wins the stage or he ends in top 10, the next one on the leaderboard will advance.

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

          Yeh, second 11-th place in a row. Maybe we can not to count Gennady here too? =(

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

The google event link to the SRM 744 shows the date is on Jan 2019. I assume this is a mistake, could you fix it?

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

How to solve Div 1 300?

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

    Given X, we can easily check whether the answer can be a multiple of X: just take all numbers modulo X and create the pairs greedily.

    All X you need to check are the divisors of A[0]+A[y] for some y.

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

      Or more easier divisors of sum of all numbers

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

    Another solution:

    • Generate all divisors d of all possible A[i] + A[j]. Keep the list of (i, j) pairs that are multiples of d where 0 <  = i < j < n.
    • Search for the maximal d where the graph constructed from its list of (i, j) pairs has a maximum matching (or minimum edge cover) of size n / 2.

    References:

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

Thanks a lot for the round!

Today's challenge phase reminded me: do the SRMs still use the biased room assignment algorithm (https://codeforces.net/blog/entry/57870?#comment-416132)? Given that all SRMs are part of TCO now, maybe they should switch to the fully random one?

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

What was the idea for Div 1 500?

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

    As I see it, the idea is to carefully choose the algorithm with which the largest sum will be computed. It is more or less evident that you will need to compute the probability distribution of the maximal achievable sum and the question is how to do it without introducing conditional probabilities along the way. For example, if you use partial sums, every flip of a coin influences a suffix of the array of partial sums. Therefore, assigning one variable per partial sum does not work (at least not in the straightforward way) because the variables start depending on each other and the computation even of their distributions becomes complicated, let alone of the distributions of more complicated variables such as max(s[r]) - min(s[l]), l ≤ r. Assigning a variable to every segment does not work for the same reason.

    Here is what works instead. Start with the first number and add the numbers greedily while the sum stays nonnegative. If it ever becomes negative, remember the largest sum and discard all the numbers you have seen so far. Repeat until the array is empty. After processing several numbers (and before consuming the number whose turn it is now) all you have to keep track of is the sum of the not yet discarded part and the current maximal sum.

    In the randomized version you can now assign a variable to each of these numbers... only to obtain nonindependent variables again. Luckily, this time there are only two of them regardless of the size of the initial array, so you can keep track of their joint probability distribution. Let p[i][s][m] be the probability that after the execution of our algorithm on the first i numbers the current sum is s and the maximal sum we have seen is m. Flipping a coin to set the sign of the number i we can compute p[i + 1][s'][m'] for all possible s' and m'. To be more precise, for an array of size n you now have 2·(n + 1) variables Si, Mi and the joint distribution of (Si + 1, Mi + 1) depends only on the joint distribution of (Si, Mi) and the probability of writing a minus before the number i. This allows you to compute the joint distribution of (Sn, Mn) from which you can extract the distribution of Mn that you have been seeking all along.

    → Reply