Topcoder SRM 745 is scheduled to start at 21:00 UTC -5, December 27, 2018. Registration is now open for the SRM in the Web Arena or Applet and will close 5 minutes before the match begins.
For this contest, we are running it as an experimental "fun" SRM, using a bit different format than usual. The 75 minutes of coding, 5-minute intermission, and 15-minute challenge phase will remain the same. However, instead of two separate divisions with three problems each, all competitors will be in a single division, facing the same set of six problems.
The match will be unrated and won't be used for TCO19 Stage 2 Algorithm Point Calculation.
Stage 2 TCO19 Points Leaderboard | Topcoder Java Applet
Hope to see most of you competing! All the best!
75 minutes of coding and 6 problems sound pretty insane
I remember there was some discussion about stack limits after last SRM. Do you have any updates?
Yeah, we re-ran the failed codes with increased stack limits, but all of them were still failing on some test cases. Thus there were no changes to the leaderboard/ratings.
There is no such max in theory for stack limit from the systems end. It is limited to avoid load on the testers. We will try and be more accurate with every problem going forward :)
Are you sure? Could you give me the testcase on which my solution fails? Because I rewrote it without recursion and it got OK in practice. Here's the failed code and here's the code that got OK. The logic is the same, the only difference is that the first code uses dfs and the second uses cycle.
I hope this is just one fun round and all further rounds still have three problems.
In TopCoder Div1, it seems it's hard to find problemsets that are suitable for all people because of too wide range of ratings and small number of problems. Long ago, the division cutoff of CF was 1500, but it was raised to 1900 for the same reason. I think this experiment is an attempt to solve this issue.
Yeah, that's more or less right. There will be some more experiments in the future with other formats. Personally, I expect that keeping two divisions but going up to four problems (and maybe a bit more time) will turn out to be the best new format, but it's always a good idea to have some data before making bold claims :)
Why does Topcoder need new format? In the current state SRM is like facing a problem one to one that above your skill. For beginners this is just an easy problem, for ICPC Finals challengers easy problem is a warm up and a main problem is a medium one.
Topcoder is not about fun, it is about hard training, improvement and post-round analysis. After round you may see all submissions and all test for every problem and the most important coding time for separate problems. I think the problem of topcoder is not about quality or the number of problems. The real problem is a lot of users don't know about this link: https://community.topcoder.com/stat?c=round_overview&er=157&rd=17373 or don't know the on the page you need to click to tiny yellow button to see user submissions details.
I do not understand why it takes "several minutes" to load up a practice problem on topcoder's site, or why we have to suffer through the clunky ui. Unfortunately, the experience on topcoder is not comparable to that of other sites. I hope these issues (mainly how slow everything is) will be fixed soon.
Is anyone able to login using the applet?
I'm not able to login too.
fortunately Um_nik didn't took part in the srm, otherwise he could ask the setters to stop creating problems!
I would like to ask the problem setters to stop creating problems XD
I'm now wondering who was supposed to h a v e f u n at this fun round... :<
// Edit: at least the challenge phase was okay.
Quick solutions writeup:
200: return {x,y-1}
300: Look at a maximal chain backwards. You start with a range of length n. Then, n-1 times you either remove the smallest or the largest of the numbers in the range. Thus, answer is 2^(n-1).
500: Watch out for different representations of the empty interval. [3,3), [5,7) is a valid chain. Other than that, just check that the lengths are increasing and that each interval is contained in the previous one.
600: Each element must be either smaller than or bigger than all previous elements. If you find one that isn't, it's invalid, otherwise its valid or maximal. It's only maximal if each element is either min(all previous)-1 or max(all previous)+1, and ends with min=0, max=len-1. A tricky case is that when you see e.g. {3,?,?} you know that it cannot be maximal any more.
800: All chains of order n = chains that end with [0,n) + chains that don't. The second group has the same size as the first group, minus 1, because you can append [0,n) to any chain from the second group to get a chain from the first group. Size of the second group = 2*chains of order n-1 — chains of order n-2.
1000: Greedy. Keep the number of empty intervals separately, and answer max(# of empty intervals, # of chains of nonempty intervals the greedy below builds). Keep the intervals that don't have a successor yet in a sorted set, sorted primarily by y. Process all intervals in decreasing x order. Each time you process an interval [x0,y0) put it after the interval with the largest y among the ones available.
I thought the problem statement for 600 was somewhat unclear.
The problem defines B as "the smallest integer such that after examining the first B elements of c we can be certain that it isn't the characteristic sequence of any maximal chain."
However, your solution seems to assume that we know the length of the vector c even though this is not one of the things we examined...
Yeah, in retrospect I agree that the 600 should have clarified this better :( Sorry about that, that's completely my bad.
If you have a specific idea in your mind, it's sometimes easy to miss those other interpretations, and there haven't been enough clarification requests during the round to alert me either.
(In this case, the intended meaning was that the length of c is known information because you need it anyway to tell whether it's maximal, and you are just "uncovering" the elements themselves one at a time. This is one of those cases where a story with cards being flipped over would have been clearer than the formal statement. Oh well :/ )
Regarding the clarification thing: forgive my ignorance, but how do I actually ask for the clarifications during the round? I mean, I've heard I should make my way to the admin room, but what next?
Asking the question publicly doesn't seem to be the right thing to do as there could be other contestants in the room as well (and they probably shouldn't overhear anything). I know there's also some kind of PM functionality. This sounds better to me, but how do I actually use it? And how do I know which person to message to get the answer?
Here
Oh, totally didn't see that, thanks!
This isn't mentioned in your link, but I figured out that you can press this [»] button just to the left of the chat input box. It expands to a couple of dropdown boxes which (presumably) allow you to send a message to the admins:
Do I understand correctly this is how I should ask the questions?
Regarding 1000 I think that definitely the most natural approach to finding (cardinality of) minmal cover with chains of partial order is to search for a biggest antichain by Dilworth's theorem, which is standard sweeping using basic segment tree here. However your solution finds this cover as well, so that's an advantage.