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

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

Всем привет!

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

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

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

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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...

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

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

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

Anybody can open problems?

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

My love for probabilities at 3 AM is absolutely overwhelming.

»
11 лет назад, скрыть # |
 
Проголосовать: нравится -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

  • »
    »
    11 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 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).

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

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

    • »
      »
      »
      11 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +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.

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

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

    • »
      »
      »
      11 лет назад, скрыть # ^ |
      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.

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

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

»
11 лет назад, скрыть # |
 
Проголосовать: нравится +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 :'(