chrome's blog

Topcoder Single Round Match 654
By chrome, 9 years ago, translation, In English

Salem to everybody!

Tomorrow at 04:00 MSK will be held Topcoder SRM 654.

Let's discuss problems after contest.

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

»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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

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

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

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

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

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

Anybody can open problems?

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

My love for probabilities at 3 AM is absolutely overwhelming.

→ Reply
»
9 years ago, # |
  Vote: I like it -15 Vote: I do not like it

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

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

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

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

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

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

      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.

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

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

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

      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.

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

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

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

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

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

      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)

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

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 :'(

→ Reply