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

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

Здравствуйте!

Я рад пригласить вас принять участие в Codeforces Beta Round #57 (Div. 2).
Сегодняшнее соревнование подготовили Amir Goharshady и я.

Мы благодарим Михаила МирзаяноваАртема РаховаMohammad Javad NaderiSaeed Ilchi и Марию Белову.

Сегодняшний контест посвящен Khaje Nasir Tusi, сегодня в Иране день техники.


Желаем хорошего контеста.

Alireza Farhadi и Amir Goharshady

نسخه پارسی این پست را در اینجا ببینید
  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
Good Luck To All!
13 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Thank you very much.
Is it mean many math problems in contest?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
You can download PDF version of statements from these links when the contest starts:
Russian , Persian , English.  текст условий на персидском? Интересно

  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится
    Никит, посмотри кто авторы контеста. А вообще реально интересно.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
my first contest
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Good))
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вы посмотрите, а парень-то действительно не дурак, зря над ним смеялись. Поздравляю с присвоением звания, офицер!
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Кирилл, ты действительно считаешь успехом две задачи в div2 only контесте? Даже если бы он решил больше задач, один контест - слишком маленькая выборка. Впрочем, и отрицательные выводы пока делать рано.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я ничего ни о чём не считаю действительно. Необходимо понимать, что всё, что я пишу, есть ложь и провокация, и этот коммент в том числе =)
13 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится
very thanks for you.
از همه شما متشکریم
13 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Continue having problem statements in Persian language. That's great.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Блин, думал что зарегался, оказывается нет(
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня регулярно такое происходит. Такое ощущение, что иногда вместо перехода на диалог регистрации происходит просто смена надписи с "зарегестрироваться" на "зарегистрирован".
13 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится
nice job!
13 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
i have been trying for 5 minutes to upload , why its not progressing???

Edit: It has become 15 minutes. I am not able to upload . What is the problem?
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
درود !

تو سوال دوم چرا
test case 4 (‫‪Ira__Persiann__Wonderful‬‬)

غلطه ؟؟؟؟؟
لطفا زود تر جواب بدید !
13 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
دمتون گرم!!
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
بیشتر دمتون گرم !!!!!!!!!!! :D

ولی سخت بود !
13 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
!!!ایول اسمه منم گفتی
  :ِD  معروف شدم دیگه 
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Thanks for Mike and all friends.
I hope good luck all friends.
از دوستان ایرانی هم تشکر دمتون گرم
واقعا تو این اوضاع خیلی خوب امدید این کارو.
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
I am facing problem in uploading the source code. I checked at other OJ sites uploading is working there . In gmail also it works fine. I am using Firefox. I reinstalled it.

Please Help!
13 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
As an Iranian I request you not to write Persian here! As we don't like others write in languages we don't know.
The contest was awesome! Except for problem C!! Hope to see more Iranian contests!
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can anyone suggest a solution for problem no 5 ?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    It can be solved in O(nlgn) using a segment tree or using merge-sort
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    First let's find the number of pairs i < j, ai > aj.
    How many numbers aj are there to the right of i such that ai > aj? To answer this question you should maintain a binary indexed tree / segment tree or a similar data structure: go from right to left, calculate the answer for ai and add ai to the tree.

    Having done this, notice that the problem is pretty much the same for triples: the number of pairs aj, ak to the right of i is equal to the sum of the answers to the previous problem for all aj < ai, j > i.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а можно поподробней "go from right to left, calculate the answer for ai and add ai to the tree."
      как именно мы используем предыдущие полученные значения для нахождения ответа для ai
      мы же не за квадрат делаем? :)
      • 13 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
        WLOG ai are numbers from 0 to n - 1.
        where xj is 0 if you haven't yet added j while passing from right to left; otherwise it's 1. Not height, but strength, i.e. the strength of the soldier, I don't know how to edit it now.

        For the second step, xj is either 0 or ans[j].
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Alternatively, you can multiply the numbers of pairs i < j, ai > aj and j > k, aj > ak to get the answer for j.
          This requires two passes: one from left to right and one from right to left.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          спасибо!
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Две задачи... Не очень много, но, наверное, я большее и не осилю. Удивила задача E - вроде самая сложная (по баллам), а решение элементарное (хотя и взломалось моё решение с блеском и феерией).
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
1) В E - дерево отрезков?

2) Как решать D?
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    2*сумма длин ребер - длина самого длинног пути от 1 
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В E видел как минимум дерево Фенвика, дерево отрезков и сортировку слиянием. Должны также работать всякие сбалансированные деревья, а ещё вроде как должно получаться с std::set.lower_bound (...). После систеста увидим, что из этого работает.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      А что set.lower_bound() даст? Итераторы set::iterator ведь нельзя вычитать.
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Точно. Видимо, не даст. Хорошо, что я стал слияние писать :) .
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1) можно фенвик, только long long, как я, забывать не надо. Моно rmq.

    2) Ответ - сумма ребер * 2 - длина макс. пути из корня.
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    1. Да
    2. Ответ - 2 на сумму ребер - максимальный путь до листа
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В D нужно найти такой путь от 1 до какой-нибудь вершины X, что он подчиняется условиям:
    • X — лист дерева с корнем 1
    • среди таких путей этот путь максимальной длины
    Тогда все грани графа мы посетим ровно два раза, исключая грани найденного пути, которые мы посетим один раз. Т.е., ответ: 2·(сумма всех w) - (путь этого пути).
    Реализовать можно как обхождение графа, скажем, поиск в ширину.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Условие на лист вроде бы не нужно. Если это не лист, то найдется вершина - лист которая дальше
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    В задаче E достаточно дерева Фенвика.
    В задаче D найдем в дереве лист, расстояние до которого максимально, все ребра на этом пути войдут в ответ ровно один раз, остальные ребра войдут в ответ два раза.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Well, it was a bit frustrating to get 100 points for the fact that despite sys.setrecursionlimit (100000), Python is unable to handle recursion beyond few thousands... It just silently breaks (instead of the "maximum recursion depth exceeded" message if the recursion limit is the default, 1000).
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня было такое же. На форуме страшные вещи написали: http://python.su/forum/viewtopic.php?id=8804
    • 13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Ах вот оно что! Как и "%I64d" vs. "%lld" на MinGW C++, это — тлетворное влияние Microsoft!

      За ссылку спасибо. Предлагаю админам CodeForces ею воспользоваться :) . Но — если так сделать, будут ли эти мегабайты на стек всегда задействованы, то есть не будет ли необоснованных Memory Limit?
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ещё немного frustrating, что решение за O(n*log(n)) на Python к задаче E не проходит по времени. Моё решение на тесте с n = 1000000 работает 45 секунд!
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да это-то уже привычно, что несколько миллионов операций на Питоне в две секунды уже не укладываются...
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет, я это прекрасно знал. И даже знаю, как это обходить ;)
    Просто люблю писать всякую глупость и давать возможность людям почувствовать, какие они умные))
    • 13 лет назад, # ^ |
        Проголосовать: нравится +2 Проголосовать: не нравится
      И как это обходить, кроме того, чтобы не использовать встроенный стек?
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Не пойму как в E дерево Фенвика можно было применить. 
Хотя знаю как писать и использовать это дерево.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Для каждого числа надо найти, сколько чисел левее него и больше него, и сколько чисел правее него и меньше него, и эти два числа перемножить. Это можно сделать двумя проходами с деревом Фенвика: слева направо и справа налево.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится
    Будем втыкать числа в отрезок в порядке их убывания. И не сами числа, а только единички на нужные места.

    Пусть мы втыкаем число на место i. Тогда Чисел больше его и левее его - количество единичек на отрезке [1..i-1], а чисел меньше и правее его - количество ноликов на отрезке [i+1..n]. Нетрудно понять, что количество хороших троек с средним в позиции i - произведение этих количеств.

    Дерево Фенвика позволяет быстро считать сколько там нулей или единичек на нужных отрезках, а так же быстро втыкать новые единички.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Уже как минимум 2 решения по задаче А упали на 99 тесте! Интересно, как такое возможно?)
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    массив маленький завели)))вроде из-за этого
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In this contest, after my code for problem A passed all the pretests, there is NO LOCK option, while in #56 it did have. Anyone knows why?
13 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится
Как-то сегодня медленно тестит.
  • 13 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    Кто-то сегодня сильно торопится.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      В положении всё "Системное тестирование 100%", а меж тем рейтинги уже обновили!
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Должно быть что-то типа "Системное тестирование завершено".
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Так-так... Значит в C число могло быть равно 0, если не римская система счисления. Вот я Слоупок то. Думал, что оно всегда положительное.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Was cin too slow for problem E?
13 лет назад, # |
Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится
После имплементации (вчера?) нового просмотра кода, сейчас я получаю при копировании примерно такое:

   1. #include <cstdio>
   2. #include <iostream>

Было ещё такое

#   #include <cstdio>
#   #include <iostream>

UPD 2. <pre class="source prettyprint"> ведёт себя по-разному. В любом случае скопировать код нормально сейчас не представляется возможности. :(
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как можно узнать тест, на котором решение взломали?
  • 13 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
    Когда квест с тестированием закончится, при просмотре решения снизу будут началы инпутов, отпутов и ответов. Ой, да, не то сказал.)
  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Взломы->нажать на надпись что взлом успешен
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
we are very surprised by this contest.
It has very good design (thanks a lot!).
Plz put persian translate of every problem in every future contest too.
Thnx.
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
By the way, it is 1337 post.
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как можно взять тест, который слишком большой, и не выводится полностью в режиме просмотра решения, и можно ли вообще?
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

If any one have time plz tell...why the difference in output ?

http://ideone.com/GSqVs

Here it gives 3. and there at ideone it gives 7.

This was Q4.

  • 13 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    remove this line :
    maxx = vec[s][i].second;
    change this visited = vector<int> (n ,0);
    to visited = vector<int> (n + 1,0);
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
please can any one explain to me the idea behind problem E ? Thanks in advance.
13 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится
I'm looking forward to the similar international contests. It's a good opportunity to improve the programming skills and learn something about foreign culture simultaneously. Well done :)
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Thanks a lot it was a nice contest :)
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Обидно было на контесте, когда видишь решение за квадрат или за куб, пытаешься взломать его большим тестом, а в тест и генератор влезает только 20 КБ, и уж тут никак не уложится большой тест, хотя можно было бы 100 очков своих получить!
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Ну вы же не писали этот тест вручную, а генерировали его как-то. Вот и отправьте этот генератор.
    • 13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      с генератором или предварительно сгенерирован тест, всё равно не получается совершить взлом, выдавало ошибку по памяти!
      • 13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Значит неэффектиынй или косячный генератор.
        • 13 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          покажите тогда пример не косячного генератора