mkagenius's blog

SRM 757 Reminder — 21:00 UTC-4 on April 29
By mkagenius, history, 6 years ago, In English

Single Round Match 757

Topcoder SRM 757 is scheduled to start at 21:00 UTC-4 on April 29, 2019.

Registration is now open for the SRM in the Arena or Applet and will close 5 minutes before the match begins, so make sure that you are all ready to go. Click here to what time it starts in your area.

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

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

Problem Writer: misof

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

    Do you start to announce writers before the round?

    The link doesn't work for me. The correct link is misof.

    Error log:

    TypeError: Cannot read property 'handle' of null
    at p (chunk-1556278029512.js:1)
    at $o (main-1556278029512.js:100)
    at wa (main-1556278029512.js:100)
    at ji (main-1556278029512.js:100)
    at Vi (main-1556278029512.js:100)
    at Cs (main-1556278029512.js:100)
    at Ts (main-1556278029512.js:100)
    at ys (main-1556278029512.js:100)
    at Ji (main-1556278029512.js:100)
    at Object.enqueueSetState (main-1556278029512.js:100)
...
    → Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Reminder: 1 hour to start!

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

https://codeforces.me/contest/850/problem/F

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

Why is the constraints of med so high?

If the intended solution is just a brute force after ignoring max >= size — 1, even size <= 5 should be fine.

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

    Why is it high though? There are only 6.6k reachable states with the current constraints, so even if we multiply it by 2^9 it'll be still not that large.

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

      Ideally, all poorly-written solutions of good complexity should pass and all well-written solutions with bad complexity should fail. Of course, sometimes this is impossible (for example if you want to separate n log n and n^1.5 or something like that), but in this case the difference is absolutely clear (are there any unintended solutions for size <= 6, values <= 10^9 for example?).

      $$$6.6$$$k times $$$2^9$$$ times $$$n$$$ (from which pile should we take stones) times $$$n$$$ (how many stones will we take) times log (memoization cost) is not so small. I challenged one solution because of that.

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

        log(memoization cost) is easy to reduce because we can easily implement hashing function (think about lattice going up or right, where up means 0 and right means 1, and hash into binary).
        But I couldn't submit just because my code still takes 5.2 secs in maximum case.

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

    There are various factors that make problems "harder" (i.e., make success rates lower): requires hard-to-notice idea, requires the knowledge of a bit advanced algorithm, requires lengthy implementation, the sample intentionally excludes corner cases, the TL is tight, etc.

    I understand that misof is trying to make problems easier. My impression is that this is done by lowering the level of ideas. However there are other ways to make problems easier even if we require the same level of ideas. Making problems harder by tight TL feels like a "waste" of success rates.

    For example, I think the easies of both SRM 757 and 756 are very nice. They definitely require observation for me, and probably for other reds too. I think they are enjoyable for reds too and can be good candidates of easy Mediums.

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

      Hey, sorry I wasn't able to reply to you sooner, I was traveling.

      In this particular problem there was no intention to time people out. If the first Java reference solution I write runs in 0.6 seconds without any optimizations, I don't expect C++ solutions to have problems with the time limit. It's unlucky that some did.

      Additionally (and this was something I knew before the round and considered a part of the problem) the total number of states is very small (and, quite intuitively, the number of losing states is very small) so if you happen to time out with a correct idea but an inefficient implementation, it's both easy to realize that this is happening and to precompute the answers locally. This even has a nice algorithmic concept behind it: if you notice that "remove one match" is a valid move, you can precompute everything simply by solving the state (7,7,7,7,7,7,7,7,7) without returning early.

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

    I misread the problem as if the players can set at most one pile on fire, and kept wondering why the hell piles of size n-1 win the game.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it

    There is an observation that the number of states where the second player wins is just 156. Therefore, if your solution is not fast enough, you can notice this observation and precalculate answers locally.

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

Can anyone please let me know their approach to div1-250? I am not able to get the logic for this one. If there is a link for editorial please share that too.

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

    You can use a max heap to always choose the most unfavorable color -- the ones who need more of their kind to be whole (F).

    Here is the code:

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

When will be editorials for this round?

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

    Sorry for the delay, the editorial got lost on its way to you. Here's the draft (and please mention me by name to send me a notification if there is a similar issue in the future).

    Editorial

    → Reply