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

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


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

Сслыка на задачи/результаты: http://acm.timus.ru/monitor.aspx?id=100

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

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У кого-нибудь были проблемы с тестом #57 в задаче C? Надо полагать, он на точность. Но никакие шаманства не помогли сдать задачу...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я подгоном точности дошел до 62-ого... с 57-ым не было проблем. Мой епсилон - 1e-5.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      У меня там при любых EPS 1e-2 ~ 1e-6 получалось ВА57...
      • 13 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        у меня прошла только с EPS = 1e-9
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Странно. Я делал все вычисления до исчерпания точности, но начиная с 1e-7 получал ВА на более ранних тестах. Ты как ее решал (мой подход описан внизу)?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нас выручил эпсилон 1e-8. Был 1e-6.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задача С решается в целых числах. Главное - в нужных местах использовать лонг лонг.
13 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится
Меня больше удивляет задача J. Я написал решение, в котором не мог найти ошибку всю заморозку, но так и не прошел дальше второго теста. Условие было написано отвратительно, но для тимуса это привычно. Вообще, я до сих пор не уверен, что удаление одного символа занимает одну секунду. Надеюсь, что это так. Поправьте меня, если я ошибаюсь. Те, кто решил эту задачу, пожалуйста, поделитесь тем, как решали ее, может быть это подскажет мне где же я ошибся. 
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    аккуратно написал Дейкстру на куче
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      То есть можно было теоретически выбрать слово какое-то стрелочками ("вверх" или "вниз") и при этом считалось бы, что у нас набрано это слово целиком? То есть после того, как мы выбрали слово стрелочками, мы могли бы удалить из него пару букв и заменить их?
      • 13 лет назад, # ^ |
          Проголосовать: нравится +4 Проголосовать: не нравится
        нет

        состояние описывается парой (индекс, количество набранных букв)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а какие у тебя веса в графе? не единичные что ли?
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        а как сделать единичные?
        • 13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          кажется можно ввести другие состояния и добавить новый переход - изменение последней буквы (например "a" -> "b", "b"-> "c", из "с" нет перехода).

          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            а, ну такое в голову приходило, но почему-то показалось, что будет 26*100000 состояний, и это в итоге даже дольше работать будет.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        веса не единичные
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Не туда

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать задачу G, ставил вместо вопросов одинаковые символы и релаксировал ответ ВА 30?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нужно было рассмотреть 2 случая: когда в обоих строках вместо вопросов один и тот же иероглиф, и когда в каждой строке - какой-то свой иероглиф (но один и тот же для каждой строки). Такое решение зашло.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    У нас прошло следующее решение:
    Найдем самый популярный символ C1 в первой последовательности. Найдем самый популярный символ во второй последовательности C2.
    Теперь выберем лучшее из следующих решений:
    1) Заменить все нули в первой последовательности на C2, а во второй - на C1.
    2) Заменить все нули в первой и второй последовательности на C (где C принимает все возможные значения от 1 до 100000).
    Проверку несложно осуществлять за O(1).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Какая самая распространенная ошибка в L?
13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Кто как решал задачу С (Angry birds)?


Я для каждой пары обезьян находил множество обезьян, убиваемое выстрелом, проходящим через этих двух обезьян, и потом перебором находил минимальное множество выстрелов.
Для двух данных обезьян угол и скорость, под которыми нужно стрелять, я находил так: угол ищем бинарным поиском. При данном угле из несложного уравнения получаем (точно) скорость, которую нужно развить, чтобы "убить" первую (левую из двух) обезьяну. После этого смотрим: если выстрел прошел под второй (правой) обезьяной, угол выстрела нужно уменьшать, а если над - то увеличивать.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    два бинпоиска вложенных, один по составляющей vx, другой - по vy

    еле затолкал из-за точности =)
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      По сути, подход тот же. Может, они не любят тригонометрию в решениях...
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        у меня нет никакой тригонометрии

        я даже корни нигде не извлекаю :)
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ну да, твой способ понятен, там действительно не надо даже корней. Мне просто интересно - на чем там можно так жестко чикать решения по точности
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Все авторские решения, что у нас были, просто строили уравнение параболы в явном виде и работали уже с ним. Бинпоиски и тригонометрию действительно было упихать сложно. Тесты 57-62 - на проверку точности и некоторых граничных случаев.
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    У меня отличие в том, что когда зафиксировали 2ух обезьян, получаем систему линейных уравнений относительно {p, q2}:

    p · xi - q2· xi2 = yi

    p · xj - q2· xj2 = yj

    Проверяем q2  >  = 0, после чего подставляем остальных обезьян в уравнение. Это всё делается в целых числах, чтоб не было проблем с переполнением брал по разным простым модулям. 

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

Почему в G не проходит такое решение?

Нам нужно максимизировать сумму cnt1[i]*cnt2[i], где i=1...100000.

На каждом шаге, пока не останется знаков вопроса, я выбирал такое число, чтобы сумма была максимальной.

В итоге ВА13.

  • 13 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится +5 Проголосовать: не нравится

    Рассмотрим тест:
    7
    0 0 1 1 2 2 2
    9
    0 0 1 1 1 1 2 2 2

    30

    11
    0 0 0 1 2 2 2 3 3 3 3
    11
    0 0 0 1 1 1 1 2 2 2 3

    77


    10
    0 0 1 2 2 2 3 3 3 3
    11
    0 0 0 1 1 1 1 2 2 2 3

    72


    Нули из первой строки ты будет превращать в 1, т.к. это будет максимизировать твою сумму, а нули из второй строки в 3... Но лучше будет все нули превратить в 2.

    UPD. Шутканул, после того как ты поставишь 1 в первой строке, во второй ты тоже выберишь 1, сейчас додумаю...

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

      У меня тоже ответ 30. Сначала нули из первой строки превращаются в 1, а потом у нас в первой строке уже больше 1 и нули из второй строки тоже превращаются в 1.

      UPD: Спасибо, я понял

13 лет назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решать задачу K. На контесте были идеи, но писать не осмелились
  • 13 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    как то так:
    	sort(Z+1, Z+n+1);
    	cout << 5 << "\n";
    	cout << -o_O << " " << o_O << "\n";
    	cout << -o_O << " " << -o_O << "\n";
    	cout << Z[k].FI << " " << -o_O << "\n";
    	cout << Z[k].FI << " " << Z[k].SE << "\n";
    	cout << Z[k].FI-1 << " " << o_O << "\n";

    правда, это решение не совсем верно (можно подобрать тест когда одна сторона будет иметь длину 0)
    но оно как то зашло))
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      и каким образом можно подобрать такой тест? ;)
      • 13 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится
        надо чтобы
        Z[k].FI = -o_O+1
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          хм, и правда, моё решение выводит две одинаковых точки =)
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Я подобрал даже до первого сабмита. Правда, все равно +1, потому что сначала выводил вершины в порядке по часовой стрелке =)

        P.S. И тогда совершенно непонятно, почему народ ее так грязно насдавал, если в тестах таких случаев не было

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

        не туда

    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Даже в таком же порядке как и у меня... а по поводу теста - там же сказано что каждая точка находится на положительном расстоянии от каждой стороны торта...
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Я выпуклую оболочку написал для первых k точек в порядке сортировки. В конце надо рассмотреть тонкие случаи, когда в оболочке вышло 1 или 2 вершины.

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

      Делали так же, только добавили в выпуклую оболочку точки (-1e9+1, -1e9) и (-1e9,-1e9+1). Все случаи отпадают. 

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
В задаче B я пользовался предположением, что в оптимальном решении наши палки - это хорды окружности с центром в основании березы. Предположение оказалось верным. Кто нибудь может доказать это предположение?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я написал через другое предположение: палки образуют тупоугольный треугольник с углом 135 градусов, третья сторона которого - гипотенуза равнобедренного прямоугольного треугольника (катеты - береза и земля). То, что прямоугольный треугольник должен быть равнобедренным, доказывается элементарно, угол 135 градусов - через дифференцирование. Угол 135 градусов опирается на дугу в 270 градусов, а это оставшаяся часть окружности.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А, ну да, дифференцированием можно

      А как нибудь красиво это доказывается?:)
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я глубоко подумал: по-моему, красивее дифференцирования ничего найти не получится (т.к. хотя бы то, что из всех прямоугольников наибольшая площадь у квадрата, доказывается как раз через дифференцирование).
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Это же школьный контест. Конечно, доказывается.

        Разобьём наш 4-угольник на 2 треугольника диагональю, соединяющей точки примыкания палок к берёзе и к земле. Пусть длины палок - a и b. Зафиксируем какую-то длину этой диагонали L. Тогда максимум площади нижнего треугольника очевидно достигается, когда эта диагональ идёт под углом 45. Тогда эта площадь равна 1/4*L^2.

        Пусть теперь угол между палками равен p. Тогда площадь верхнего треугольника равна 1/2*a*b*sin(p). L^2 = a^2+b^2-2*a*b*cos(p). Итого суммарная площадь 1/2*a*b*sin(p) + 1/4*(a^2+b^2-2*a*b*cos(p)) = 1/4*(a^2+b^2) + 1/2*a*b*(sin(p)-cos(p)) = 1/4*(a^2+b^2)+1/sqrt(2)*a*b*sin(p-45). Максимум синуса достигается в 90, т.е. при p=135. Итого ответ 1/4*(a^2+b^2)+1/sqrt(2)*a*b

        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          а я то думаю почему мои тернарники и градиент так плохо запихиваются....
          • 13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            У меня с тернарником по L (в терминах доказательства выше) никаких проблем не возникло
  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    мда, тупо 2 вложенных тернарника по проекциям на оси заходят...
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Я тоже об этом подумал, но предпочел все-таки вывести формулу и написать решение за O(1).
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Хотелось бы узнать, как по-человечеки Кубик-Рубика решать?? (решал bfs)
  • 13 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    ну это почти по-человечески

    мы просто для каждого слоя искали его нужный сдвиг (перебрав сначала общую картинку)

    скидываем цвета, проходясь по кругу, в вектор, и с такими векторами уже все просто

  • 13 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
        for(int i=0;i<6;i++)
        {
            cin>>x;
            if (i!=2 && i!=3) v.pb(x);
        }
        
        int ans=100;
        for(int i=1;i<=4;i++)
        {
            int now=0;
            for(int j=0;j<v.sz;j++)
            {
                int m=min((i-v[j]+16)%4,(v[j]-i+16)%4);
                now+=m;
            }
            ans=min(ans,now);
        }
        cout<<ans;
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Рассмотрим левый верхний квадрат 2*2. Заметим, что если в нем все цвета одинаковые, то картинка такая, какая нужна. Тогда переберем цвет, который в нем будет. Каждая из четырех клеток квадрата лежит на отдельном слое, а каждый слой представляет из себя зацикленную посл-ть 1, 2, 3, 4. Пусть у нас в некоторой клетке верхнего квадрата стоит число i, а мы хотим получить j. Понятно, что мы можем циклически сдвинуть последовательность 1-2-3-4 вправо или влево. Собственно, перебираем цвет левого верхнего квадрата и банально считаем стоимость сдвига его элементов в нужный цвет.

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А что за 14-ый тест в задаче К?