Блог пользователя chrome

Автор chrome, 9 лет назад, По-русски

Всем привет!

Завтра в 04:00 MSK состоится Topcoder SRM 654.

Предлагаю обсудить задачи после контеста.

  • Проголосовать: нравится
  • +40
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Looks like the top 250 after this contest get a free pass to TCO Round 2 (http://tco15.topcoder.com/algorithm/rules/).

Then again, that prevents you from competing in the first three rated rounds of TCO, so maybe it's not a good thing...

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    I hope there will be at least one more SRM before April, 9 — let's wait for updated schedule. Last year we had 4 SRMs and 3 TCO Rounds during April :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Everyone in my room got disconnected from the server -- make sure you're still connected

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anybody can open problems?

»
9 лет назад, # |
  Проголосовать: нравится +50 Проголосовать: не нравится

My love for probabilities at 3 AM is absolutely overwhelming.

»
9 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Swistakk cries again

Eh, I tried hard problem for too long and I lacked literally 1 minute for completing med and I forgot that this is TC and coded instead of O(n2) >_>... Moreover I saw one guy doing easy in O(n3) in my room, but my hacking attempt aiming at TLE was unsuccessful

This looks a little bit too complicated for that problem:

struct Node {
    int sum, pref0, suf0, prefsuf, best1, best2, pref1, suf1;
  };
  Node Join(Node& a, Node& b) {
    Node n;
    n.sum = a.sum + b.sum;
    n.pref0 = max(a.pref0, a.sum + b.pref0);
    n.suf0 = max(b.suf0, b.sum + a.suf0);
    n.prefsuf = max(a.pref0 + b.suf0, max(a.sum + b.prefsuf, a.prefsuf + b.sum));
    n.best1 = max(max(a.best1, b.best1), a.suf0 + b.pref0);
    n.best2 = max(max(max(max(a.best2, b.best2), a.best1 + b.best1), a.suf0 + b.pref1), b.pref0 + a.suf1);
    n.pref1 = max(max(max(a.pref0 + b.best1, a.pref1), a.sum + b.pref1), a.prefsuf + b.pref0);
    n.suf1 =  max(max(max(b.suf0 + a.best1, b.suf1), b.sum + a.suf1), b.prefsuf + a.suf0);
    return n;
  }

:D

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    My deepest sympathy goes to you! I indeed started off with this approach and had no idea why I thought it was O(n2 * logn) at the beginning (which made me believe it was a reasonable solution).

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Initially the constraints were N <= 200000, but we thought it was too complicated for d1 med and decided to make the constraints smaller.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Btw, I learnt that name of class was changed during the coding phase, so I wouldn't even be able to compile it (I think I wouldn't figure out the reason). I use some plugins which allow me to code locally and they won't detect that. Why such a change was made? It is something extremely confusing. Moreover I think I missed or disregarded an announcement, if there was any.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    may you explain your O(N * log N) approach?, thanks.

    • »
      »
      »
      9 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Aren't names of variables descriptive enough? I wanted to have an interval tree supporting operations of asking about the biggest sum on two intervals. In case of one interval you need to keep sum, best prefix, best suffix and best inner result — those informations are easily mergeable and here the idea is the same, but you need more variables.

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Got Div1 easy one minute after coding phase. :( Need to work harder.

  • »
    »
    9 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Got Div1 Medium during coding phase. Had at least half an hour to implement it. Couldn't collect my thoughts under time pressure (as usual) and didn't write it in time.
    UPD: Passed in practice for 432...

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I guess that "came up with solution and didn't write it in time" is not the most unlucky contest story ever :P (that being sad by person which cries after almost all contests :P)

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Got Div2 med several minutes after coding phase. took too long for debugging and you know why? i forgot to return the value of method :'(