Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM%20727&iso=20180111T0200&ah=2&am=0
Author is Errichto
Also check : http://codeforces.me/blog/entry/57011
Please do not upvote my SRM blogs. I don’t want my contribution sky rocketing for something I do not take credit for. I only aware you so you don’t miss SRM’s like I did when cgy4ever ( or in the past, Chrome) stopped posting them.
"Please do not upvote my SRM blogs." — why not? You are definitely bringing value to this community which is broadcasting information about upcoming competition that many people would probably miss without you. Even if you are not the author etc. I would say this is valuable contribution, we need such people and such blogs.
The registration terms in both arenas:
Huh, is that right?
I have also came across this problem. I’m sure that this statement is copied from Wipro Internal SRM. Can you inform to admins if someone can? (I can’t contact because I am out and I have no slack app in my phone, though I wrote here https://apps.topcoder.com/forums/?module=Thread&threadID=910926&start=0&mc=1)
UPD: Seeing Errichto’s comment, the problem seems to be fixed. Thanks to topcoder admins for the fast problem solving.
From arena chat:
I've just emailed admins, just in case. It should be a standard rated round, I think.
Also, a reminder: the contest will start in 3 hours.
EDIT — official response is: the info was incorrect, sorry for a mistake.
So, the round will be standard and rated.
Congratulations to lych_cys for winning and to a close runner up, sunset. Both managed to solve easy+hard, while nobody managed to solve all three problems.
div2-easy MakeTwoConsecutive — code
One solution is to iterate over a character to remove, glue the two parts, and check if we have two consecutive equal characters. The other solution is to do some cases analysis and figure out that the answer is positive only if N ≥ 3 and we have some Si = Si + 1 or Si = Si + 2 — then we will be able to reach the desired property.
div2-med TwoDiagonals — code
Try to first solve this problem if one line should be horizontal and the other vertical. You can iterate over both of them — then you just want to know how many cities line on them and whether there is a city at the intersection point. Now apply the same for tilted lines.
div2-hard ManageSubsequences — code
We want to know the length of the shortest string that has subsequences S and A, and doesn't have B. It's useful to know the algorithm to do that without any forbidden subsequence B — that's equivalent to finding the longest common subsequence. Now you need to add more more dimension to the DP, representing how big prefix of B we already got.
div1-easy OnlySanta — code
There are multiple solutions and I will describe just one of them. We can always add "TA" at the end, so we just have to get a subsequence "SAN" first. If it's already there, do nothing. If there is no 'S', just add "SAN" at the end. Otherwise add "AN" just after 'S'.
div1-med Subrectangle — code
We can iterate over the width of the grid, and the width of the marked subrectangle. Then we know how many marked and empty cells we should get alternately. Starting from the first '#' in the given grid, we know how many characters of each type we want now, and we can greedily add them. The remaining thing is to add some extra '.' at the beginning or/and the end, to make the total length divisible by the grid width, and to make rectangle not to break between lines.
div1-hard DoubleLive — code
We can't do any dp keeping the number of humans and bears. What we can do is dp with the number of 1hp warriors and 2hp warriors, what means we know the total number of warriors. The main trick here is the following:
We fix one human and one bear and we compute the EV of the final number of alive warriors with condition that those two must be alive too. We computed how much one pair (human,pair) contributes to the final strength bears*humans*warriors. Then we multiply the answer by B*H, because this is how many pairs (human,bear) there are.
How did you like the problems?
Two extra challenges:
I really like hard problem even though this was the only one I did not solve. Easy and medium are okayish.
Maybe 500 is harder than 900 because I solved 900 easily but I couldn't find a good way to solve 500:D
Yeah, it's perfectly possible to come up with 900 fast and struggle with 500. Maybe it would happen to me too. Still, the 500 was much easier for the majority.
I should have checked the winner on CF first, before I decided to blindly challenge his hard solution...
I liked div1-hard, but the bounds seemed a bit tight to me. I was able to get my solution to pass in practice, but with 1.987s (your solution seems to take 1.2s). I had spent most of the round trying to constant factor optimize it, but failed to get it to pass during the round.
For sure it wasn't my intention to require a lot of constant optimizing, so I'm sorry for that.
How did you check that my solution takes 1.2s? In MPSQAS (their software for preparing problems) I have 0.56s on max tests, and I always thought solutions are run on the same server. If not, this is an extremely important issue in general.
Also, I've written a wrong name in my post above. Now it's correct — the second place went to sunset. Sorry and congratulations!
I scopied your code into the practice room and ran systests there. I remember there was some issue about timing before so I’m not sure if this is related or if it had been fixed.
I had a slightly different (and unfortunately more complex-to-implement) approach to the 900. I definitely found it harder than the 500.
As before, do a DP on the state space of (total warriors, 2 HP warriors). For each state, keep not only the probability, but all the expected value of H and of H² (where H is the number of humans still alive). Let W be the total warriers. The score for a state is W*H*(W-H) = W*(HW — H²), so using the stored expected values you can compute the expected value of this expression for a given state. The nasty part is figuring out how to compute the new value of H² in the case of a 1HP warrior being hit — I ended up having to write out the formula for expected value and do the algebra.
I've read your explanation on Div1 hard but it's very hard to understand. Can you proof why the EV when you fix one bear and one human is the answer? Thank you a lot :)
Every pair has the same contribution to the answer. Read more here https://codeforces.me/blog/entry/62792
Thank you a lot. Finally I realized my problem. Your video is great and hope you to produce more education videos like that :)
When I ran my code on Example 0 for Div2 500 twice consecutively, the difference in execution time was 374ms (Run 1: 1234ms, Run 2: 1608ms). In System Tests, does Topcoder run submissions multiple times and take the minimum execution time into account?
Probably it's not an option because of nondeterministic solutions. Considering an average time seems to be much better though.