hmehta's blog

Topcoder SRM 807 — Rated only for Div II
By hmehta, history, 3 years ago, In English

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

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

Comments Comments (14)
| Write comment?
»
3 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Starts in: Countdown

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

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it's normal SRM, they probably didn't have enough problems (or time) for Div 1.

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

    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.

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

      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.

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

        Thanks for being transparent on the situation. I do appreciate it a lot.

        → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the approach for the 1000 pt. problem (Flagpole)?
I am pretty sure the O(sum * N) solution would TLE.
Thanks.

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

    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

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

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

        Yes, you are right!

        → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        subsets, not permutations

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

          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.

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

            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.

            → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

CODE
→ Reply