Med0b1011's blog

By Med0b1011, history, 8 months 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  

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

»
8 months 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?

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

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

»
8 months 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, yjq_naiive. 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)
  • »
    »
    8 months 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.

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

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

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

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

    • »
      »
      »
      8 months 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 yjq_naiive. Sorry and congratulations!

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

  • »
    »
    8 months 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
»
8 months 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?

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

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

First of all, I will upvote anybody I like!! Including Errichto SRM blogs. :-)

I'm trying the Div2 500 in the practice rooms it passes only by 1.994 seconds on the final test case so my algorithm must be wrong. It is O(N^3) which gets fully exercised by the last test case, where all points are on one diagonal and so all my NE lines contain all the points.

If we iterate over all pairs of (NW,NE) lines then that is O(N^2) already. How to do the inner check "count points on either line of the pair" in less than O(N)?

Or was the intention to only take distinct NE and NW lines?

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

    I was keeping a list of points in each diagonal and then computing their pairwise union. Now I realize the idea is to just keep the counts and then substract one if the intersection is one of our points... urgh.