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

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

Завтра в 18:00 по Москве состоится первый из интернет-туров COCI - хорватской олимпиады по программированию. Как обычно - шесть задач на три часа. Система - как на старых IOI (без фидбека, каждый тест оценивается в отдельности). Никакой мегасложной регистрации не надо - всего лишь регистрируемся в тестирующей системе и логинимся в COCI Contest #1.

От себя: мне нравятся такие туры. Очень вкусные задачки вкупе с кошерной системой оценки :-)

Спасибо yeputons за незаметно поданную идею запостить про COCI на КФ.



UPD: Появились результаты.
  • Проголосовать: нравится
  • +42
  • Проголосовать: не нравится

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А условия только на хорватском?
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

вопрос снят

15 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится
А дорешка будет?
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Вопрос снят, я понял условие

15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Кто умеет решать skakac (про коня)?

  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Ты не решил?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Вот только сейчас дописал, но как понял не до конца. Как мне кажется здесь надо как простой динамикой только шустро это все делать. Например мы можем хранить поле в битах (очень здесь помогает битсет). А дальше что-то типа
            for (int i = 0; i < n; i++)
            {
                one[i] = (a[i] >> 1) | (a[i] << 1);
                two[i] = (a[i] >> 2) | (a[i] << 2);
            }

            for (int i = 0; i < n; i++)
            {
                b[i].reset();
                if (1 < i) b[i] |= one[i - 2];
                if (0 < i) b[i] |= two[i - 1];
                if (i < n - 1) b[i] |= two[i + 1];
                if (i < n - 2) b[i] |= one[i + 2];
            }
    Потом можно заметить что клетки у которых 1 или 2 и она такого же цвета как начально, то она всегда будет доступна, поэтому мы делаем маску поля по таком критерию и
            for (int i = 0; i < n; i++)
                a[i] = b[i] & mask[i];
    Все остальные значение рассматриваем отдельно, храня все клетки которые доступны в текущий момент времени.
    int add(int t, int i)
    {
        if (t > T) return 0;
        next[i] = last[t];
        last[t] = i;
        return 0;
    }
    ...
            for (int i = last[t], j; i; i = j)
            {
                a[x[i]].set(y[i], b[x[i]].test(y[i]));
                j = next[i];
                add(t + d[i], i);
            }
    В конце успел только запустить макстест (30 100000 и все 3), около 6 секунд отработало. Думаю если ещё сделать маски для каждого 3 поле, 4 и так пока будет улучшаться, то должно зайти...
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Про коня написал следующий дёрти хак: Прыгаем сначала до простого числа в районе 30к. Простое число такое, что его нету в таблице. Тогда останавливаться мы можем только на 1ках. Потом считаем, что мы находимся в простом числе в районе т-25к, которого нету в таблице, и считаем что стоять можем как раз в тех единичках, которые мы нашли в первой части. И скачем до т. 

    Мне кажется, что завалить сложно. Хотя.. увидим.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А  как решать задачу про сортировку?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +6 Проголосовать: не нравится
    Можно заметить, что после первого хода slope'ы всегда будут длины 2. А это означает, что после первого хода каждый ревёрс будет просто свапом двух элементов, стоящих рядом не в своём порядке, то есть общее количество нужных ревёрсов, по понятным причинам, является количеством инверсий в массиве.

    Тем самым, делаем нужное количество ревёрсов на первом шагу ручками, а далее считаем количество инверсий.
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      А я пытался просто найти число инверсий в исходной перестановке, это естественно не работало, поэтому тупо отправил решение влоб =/
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Первый шаг - в лоб.
    А потом прибавляем к ответу количество инверсий.
    Доказывается так: после первого шага максимальная длина реверса будет два. Значит, их будет ровно столько, сколько инверсий.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
и еще как решать sort и ples?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    В сорт ответ это, сделать первую итерацию алгоритма + количество инверсий в оставшейся перестановке.


  • 15 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +3 Проголосовать: не нравится

    Плес, кажется, можно жадно...Рассмотрим два множества: 1) девушки с - и парни с + и 2) девушки с + и парни с минусом. Народ из разных групп не может создать пару...Далее, в каждой группе жадно набираем пары

    UPD Это действительно работает (110 таки)

15 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится
Кто нибудь знает, когда результаты будут?
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Ples - паросочетание?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Разве паросочетание зашло бы по времени?

    Я писал жадность, но мне тут сказали, что она не зайдет.
    Может кто-нибудь сумеет нормально объяснить, почему не зайдет?
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Нет.
    Там разбивается на две подзадачи (мальчики, которые хотят девочек повыше и девочки, которые хотят мальчиков пониже и наоборот).
    А дальше замечается, что каждая задача решается жадно посортили и тех, и других по росту и перебрали ответ. Проверку тоже надо соптимизировать.
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Нет. Разобьём людей на две группы. Мальчики, хотящие низеньких девочек с девочками, хотящими высоких мальчиков - в первую группу, а остальных - во вторую.
    Понятно, что люди из разных групп друг с другом танцевать не будут. Значит решаем задачу внутри каждой из групп. Ну а внутри, например, первой группы задача вообще глупая - жадно идём с самого низенького мальчика, подбирая ему самую низкую девочку. Аналогично для второй группы.
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +4 Проголосовать: не нравится
    Я индус =) Спасибо за ответы. Все гениальное просто
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Означает ли столь конкретный вопрос то, что ты решил sort(про сортировку)??)

Если кто придумал как решать последние две, можете сразу написать идею и больше не ждать просьб;)

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

Тупо, что нельзя увидеть таблицу результатов. У меня 398 баллов (0 за Sort, 48 за Skakac).

15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +3 Проголосовать: не нравится

Ну что, сколько у кого по Skakac?
У меня 64 :-(

У меня какие-то позорные WA на 2, 4, 5 и 9 тесте. Хочу тесты.

  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    32 - тупой БФС, который я написал за последние 5 минут.
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    80 с решением, как у aropan, только без оптимизации для единичек-двоечек
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +17 Проголосовать: не нравится
    144 - 1 тест TL
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    96 с решением почти в лоб. Единственная оптимизация - я считал ходы коня битовыми масками за n. На 5й и 6й тесты впритык зашло.
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +12 Проголосовать: не нравится
    Я в шоке, видимо нету макс теста у них, ибо без оптимизации 6 сек работает.

    Task: Skakac
    Score: 160

    Test # Score Time Memory Result
    1 16 0.00s4844 kBCorrect!
    2 16 0.00s4844 kBCorrect!
    3 16 0.01s4844 kBCorrect!
    4 16 0.02s4844 kBCorrect!
    5 16 0.08s4844 kBCorrect!
    6 16 0.27s4844 kBCorrect!
    7 16 0.90s4844 kBCorrect!
    8 16 0.27s4844 kBCorrect!
    9 16 0.58s4844 kBCorrect!
    10 16 0.45s4844 kBCorrect!
    • 15 лет назад, скрыть # ^ |
      ← Rev. 2  
      Проголосовать: нравится 0 Проголосовать: не нравится

      На кф мои 6 секунд превращаются в "Использовано: 1280 мс, 5280 КБ"

      UPD. Оптимизированное, которое работало 2 секунды переходит в "Использовано: 730 мс, 5284 КБ".

    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится
      Они еще будут менять тесты, скорее всего.
      Например, в задаче xor у них в конце тестов мусор.
    • 15 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +3 Проголосовать: не нравится
      Мдя. Как-то даже некруто. А я-то думал, что задача на какую-то мегакрасивую математическую идею формата "чего-то там немного", или "что-то можно не насчитывать". А она, оказывается, на "напиши оптимальненько тупняк, и оно пройдёт - макстестов нет в тестсете".
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Расскажите, как решалась X3 (про xor'ы).
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
По последней неоптимизированное решение с битсетами 144 набрало. Можно еще в 2 раза ускорить, но я уже не успел.
  • 15 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится
    Мало того, оказалось что я за ННТ (без деления на 32) в худшем случае расставлял занятые клетки, когда в таблице много одинаковых значений. После исправления проходит все тесты с макс. временем 0.64.
15 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Кто-нибудь может мне объяснить почему брут на задачу xor  :

readln(n);
  for i:=1 to n do read(a[i]);
  for i:=1 to n do
    for j:=i+1 to n do
      inc(ans,a[i] xor a[j]);
  writeln(ans);
  получает WA?
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Перетестировали. Прошла.
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
А пропустив 1-й контест, я могу участвовать в остальных?
15 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится
Кто-нибудь может выложить свой код по задаче sort?

Пишу так же, как указывали здесь в комментариях, но ни один тест у них не проходит.