When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

Medo.'s blog

By Medo., history, 6 years ago, In English

Time : https://www.timeanddate.com/worldclock/fixedtime.html?msg=SRM%20727&iso=20180111T0200&ah=2&am=0

Author is Errichto

Also check : http://codeforces.com/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.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +83 Vote: I do not like it

"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.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The registration terms in both arenas:

Registration Terms:
This is an unrated match, part of a private event.

Huh, is that right?

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    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.

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

    From arena chat:

    NobuMiu> unfortunate copy+paste
    NobuMiu> I saw a comment -> admins: The statement for registeration is wrong — this should be a rated match and public event
  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +47 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 8   Vote: I like it +61 Vote: I do not like it

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

Spoiler

div2-med TwoDiagonals — code

Spoiler

div2-hard ManageSubsequences — code

Spoiler

div1-easy OnlySanta — code

Spoiler

div1-med Subrectangle — code

Spoiler

div1-hard DoubleLive — code

Spoiler

How did you like the problems?

Two extra challenges:

  1. Solve div1-easy with the two special subsequences also given in the input (instead of hardcoding "SANTA" and "SATAN"). It can be done in linear time O(sum_of_lengths).
  2. Solve div1-hard for B, H up to 109 and T up to 3000. (it isn't much more complicated)
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    I really like hard problem even though this was the only one I did not solve. Easy and medium are okayish.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    Maybe 500 is harder than 900 because I solved 900 easily but I couldn't find a good way to solve 500:D

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

      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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I should have checked the winner on CF first, before I decided to blindly challenge his hard solution...

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      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!

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

        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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I had a slightly different (and unfortunately more complex-to-implement) approach to the 900. I definitely found it harder than the 500.

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

    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 :)

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    Probably it's not an option because of nondeterministic solutions. Considering an average time seems to be much better though.