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

TopCoder Single Round Match 521
Автор yeputons, 15 лет назад, По-русски

Сегодня, в четверг, 13 октября 2011 года в 15:02 по Москве состоится 521-й TopCoder Single Round Match (время в других городах).

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

15 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится
250 (Div 1) какая-то уж сильно халявная.
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

Странно, что мало посдавали 1000.

У меня она тоже, вообще-то упадет, но фиксится вроде одной строчкой.



UPD: гы, прибежела толпа народа, все смотрят, что ж я там такое написал)))
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
мне кажется, это конечно мое личное мнение, но на мой взгляд, это наикоченейш_й раунд
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Мне вообще повезло, я зачелленджил чела по 500-ке, который возвращал рандом. :)
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Товарищи, дайте идею 500 div1.
В 1000 напрашивается динамика, но довольно хитрая, точно не уверен.
→ Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +20 Проголосовать: не нравится
    Идея такая: для начала поймём, что для каждого хорошего множества существует квадрат какого-нибудь хорошего вида. Например, n для него равно либо nlow/nhigh, либо какой-нибудь разнице координат.
    После чего перебираем сторону квадрата. Поймём, что если квадрат для множества есть, то его можно сдвинуть вправо/вниз до тех пор, пока либо у него на верней и левой стороне не окажется по точке, либо он упрётся правой/нижней стороной в какую-нибудь точку, не включая её.
    Теперь у нас мало возможных квадратов, проверяем все и складываем ответы (в виде битмасок) в set.
    → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Правда ведь, что если добавить для каждой точки восемь соседних, то перебирать нужно только квадраты, которые построены одним из четырех способов по любым двум точкам, включая фиктивные? Ну и длины - это все возможные попарные расстояния + nlow + nhigh.
      → Ответить
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +1 Проголосовать: не нравится
      А, и чтобы работало побыстрее при фиксированном иксе можно пробежаться двумя указателями по отсортированному по y массиву точек - тогда будет для икса не O(n*sz(ys)), а O(n + sz(ys)) - оптимайз.
      → Ответить
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    У меня решение за O(x.length5). Расписывать его не готов, вот оно
    → Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Объясните условие Div1-500 :) 
Почему {(0,0)} это 5-squared, но не 10-squared?
→ Ответить
15 лет назад, скрыть # |
 
Проголосовать: нравится -11 Проголосовать: не нравится
Наконец-то я желтый на TC :)
→ Ответить
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Довольно быстро написал решение 500, до конца тура тормозил, не мог додумался до случая с квадратом в нецелых точках.

Опять таргет.

UPD. Нет, в практисе 500 всё равно падает :(
→ Ответить