Topcoder SRM 807 is scheduled to start at 07:00 UTC-4 on June 9, 2021.
Please Note: The round will consist of 5 problems with the difficulty level of Div II, and it will only be rated for Div II participants. (Members rated < 1200). Also, this round will not award points towards TCO21 Stage 4.
Registration is now open for the SRM in the Arena or Applet and closes at 06:55 UTC-4. The coding phase will start at 07:05 UTC-4, so make sure that you are all ready to go. Click here to what time it starts in your area
Please take a look at our How to Compete guide to understand Topcoder Algorithm rounds better.
Problem Writer: misof
Learn more about problem writing and testing opportunities.
Some Important Links:: Match Results (match results, rating changes, challenges, individual test case results), Problem Archive, Problem Writing, Algorithm Rankings, Editorials and Older Editorials(SRM 710 and before),
Best of luck!
- the Topcoder Team
Starts in: Countdown
Why isn't it called Rookie SRM? I'm always checking calendar for TC events and if I would not check this blog (which I did by coincidence), I would have no clue about the fact that it isn't normal SRM.
I think it's normal SRM, they probably didn't have enough problems (or time) for Div 1.
I agree. The round should be named something else and Div 1 people should not be able to register. I will definitely get pissed off if I find this out in the arena.
Apologies for the naming issue. This was originally intended to be a regular SRM, hence the name in the calendar. My work hardware died recently (always a joy) and as a consequence we weren't able to provide a full SRM prepared to the standard we want, so we went with a compromise that at least allows people to solve some problems — as opposed to cancelling the round completely. Given the situation, we didn't have any ideal way of communicating the change. We tried to do what we could (including this post by Harshit).
Updating the round name in the public Google calendar is certainly something we should have done, and we'll try to keep it in mind for the future. (Of course, the primary goal is not to have things like this happen at all, but having a better plan for when they do is always a good idea.)
Again, sorry to everyone who was affected by the change.
Thanks for being transparent on the situation. I do appreciate it a lot.
Can someone explain the approach for the 1000 pt. problem (Flagpole)?
I am pretty sure the O(sum * N) solution would TLE.
Thanks.
Divide array in two arrays for maximum 20 numbers. Then create all combination of sums for two arrays and using Binary search find sum difference in 2nd array
Ok, so for every permutation of Array 1, all the permutations of Array 2 which when added to the current sum were producing legal values (values > LO and <= HI) were to be chosen, right?
So the overall complexity would be O(2^20 * 2*LogN), which is totally manageable...
(LogN if a set was used)
Thanks.
Yes, you are right!
subsets, not permutations
Yes, I probably should have used the term subset instead of permutation, but if you visualize the subset as containing a few elements (1 bits) and not containing the others (0 bits), then you can also think of every subset as a permutation of N bits.
(In the same sense an 8 bit number can be said to possess 256 permutations)
But yeah, here the term subset better describes the thing on which the operation is to be performed.
EDIT: Thanks for the correction.
I wanted to point it out because 'subset sum' is a commonly used term. For example, you will get more results from googling 'subset sum' than from googling 'permutation sum'.
Technically, in our context, a subset is not a permutation because different subsets may have different numbers of elements, whereas every permutation of a given bit string will have the same number of bits turned on.
I can't figure out why my code for the last problem (Flagpole) is failing. It passes all the samples though. I'm just using standard meet in the middle. I'd appreciate if someone comes up with a counter case.