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!
tourist already passed to finals. How his results counts in other stages? And what's wrong with sorting by total points?
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. :)
But he is considered for giving points in one round?
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.
Yeh, second 11-th place in a row. Maybe we can not to count Gennady here too? =(
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?
Fixed :)
Can we expect editorials for the last two SRMs ?
Those editorials are at https://www.topcoder.com/blog/single-round-match-743-editorials/ and https://www.topcoder.com/blog/single-round-match-742-editorials/
Thanks. But the task I am looking for SRM 742 Div1 hard is missing.
Sorry for being lazy with Div I of 742, I am working on that and hope to have the editorials out in within next two days,
Could you clarify the starting time? I am getting four (!) different times clicking the link above, clicking "in your timezone" at https://www.topcoder.com/community/competitive-programming/ , looking at countdown there, and looking at the TopCoder event calendar.
Thanks for the catch! Should be fixed now.
The match is scheduled for 11:00 UTC-5 Dec 14
How to solve Div 1 300?
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.
Or more easier divisors of sum of all numbers
Another solution:
References:
Thanks a lot for the round!
Today's challenge phase reminded me: do the SRMs still use the biased room assignment algorithm (https://mirror.codeforces.com/blog/entry/57870?#comment-416132)? Given that all SRMs are part of TCO now, maybe they should switch to the fully random one?
What was the idea for Div 1 500?
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.