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

Invitation ITRIX 11 OPC CONTEST
Автор radhakrishnancegit, 14 лет назад, По-английски
              We would like to invite you all to participate in ITRIX OPC 11(An Individual Contest ), a 2-hour acm-icpc style online programming competition, which is organized as a part of ITRIX 2011 , the Technical fest of DIST ,College Of Engineering Guindy,India.                                                  
Start time : Sunday ,27th March 2011,8 pm IST .[ Find when it starts in your time zone Time in Other Zones]


Problem Setters: innocentboy2,sundargates
Contact: radhakrishnancegit@gmail.com
Problems : 5 - 6 problems with mix of easy (2), medium (2) and hard (1-2) levels.
Prize Money in INR 

First Place: 10000 INR
II place : 3000 INR
III place : 2000 INR



Contest is going to start in 20 minutes ......


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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно послушать кто что писал в задаче про запросы? 
→ Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    Дерево интервалов деревьев интервалов
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Мне кажется, что ваше решение не правильное, если я, конечно, всё правильно понимаю.
      Вот тест. У вас, когда происходит своп двух подпрямоугольников, значения обновляются только в вершине дерева по координате X, которая покрывает данный отрезок, а для всех остальных вершин которые покрывают отрезки, вкладывающиеся в отрезок этой вершины, значения не обновляются. 

      Если же для всех них тоже обновлять, кажется асимптотика поделится на логарифм и умножится на n.

      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Да, неправильно. Ну, значит тесты были кривые
        → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится
        Вроде бы исправил до работающего
        Сложность - O(n log n m log m + q log n log m)
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          Хотя я все еще не уверен в правильности, надо будет подумать еще
          → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Да, это все еще палево. Я, кажется, знаю как доделать, но сейчас мне надо работать, так что напишу потом
          → Ответить
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Не, не знаю. То есть еще один вид тестов я победил, но в целом мне кажется, что это решение не доводится. А еще мне кажется, что вообще нету ничего быстрее куба
            → Ответить
            • 14 лет назад, # ^ |
              ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
              Ну у меня был ответ на запрос за O(n*sqrt(n)), это 10^9 операций на макс тесте поэтому TL. Вроде это быстрее куба.
              → Ответить
              • 14 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ну, за n log n не сложно. Но это у меня тоже вызывает TL
                → Ответить
                • 14 лет назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится
                  Интересно какое вообще решение подразумевалось авторами.
                  → Ответить
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Писал двумерное дерево на объектах http://pastie.org/1726291, на контесте получало TL, сейчас отправил в архив - AC.
    Там вообще делали rejudge после изменений таймлимита?
    → Ответить
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Ну, оно дает сложность для квери n log n
      → Ответить
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Никак не пойму почему квадродерево даёт N*logN, а не просто logN?
        → Ответить
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Потому, что пересекают, но не лежат внутри O(n log n) квадратиков
          → Ответить
»
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

I am very much interested to know ,did the winners get prizes in this contest.

→ Ответить