Codeforces will be possibly unavailable in the period between Sep. 19, 19:00 (UTC) and Sep. 19, 21:00 (UTC) because of maintenance. ×

hmehta's blog

By hmehta, history, 3 months 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

»
3 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Starts in: Countdown

»
3 months 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.

  • »
    »
    3 months 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.

  • »
    »
    3 months 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.

    • »
      »
      »
      3 months 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.

      • »
        »
        »
        »
        3 months 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.

»
3 months ago, # |
  Vote: I like it -26 Vote: I do not like it

opened 700, again a trivial problem,already have a solution in mind,misread it in a hurry,3 out of 4 test cases passed,went nuts tryna see wtf is wrong in code, 5 min before the end of contest just gave a shot to read problem statement again, realised we have to add zero when no digit present.. :')

Lesson learned :)

  • »
    »
    3 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    imo, the problem statement would have been a lot harder if no zeroes were to be added.
    Being able to prefix zeroes essentially enabled us to cleanly iterate over all the digits and compute the permutation values for them, after all.

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

      I don't think so,this is my code that I wrote for this problem

      Code
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So when is rating going to be updated?

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

    That will take a few hours, as Div I members are not to be rated. So a little manual effort on that.

»
3 months 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.

  • »
    »
    3 months 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

    • »
      »
      »
      3 months 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.

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

        Yes, you are right!

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

        subsets, not permutations

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

          yes subsets

        • »
          »
          »
          »
          »
          3 months 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.

          • »
            »
            »
            »
            »
            »
            3 months 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.

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

      btw, if someone doesn't know this idea, try searching for meet in the middle technique.

»
7 weeks 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