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

Codeforces Beta Round #12 (Див. 2)
Автор MikeMirzayanov, 15 лет назад, перевод, По-русски
И снова здравствуйте. Надеюсь, никто не забыл зарегистрироваться?

На этом контесте мы попробуем альфу нашего чата - если пойдет что-то не так, мы его выключим: просьба не паниковать:)

Ссылки:
Авторы проблемсета: Дмитрий Матов и Игорь Кудряшов. За что им большое спасибо.

Желаю выйти в первый дивизион.
Mike Mirzayanov.
  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

15 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Mike, приблизительно, когда появится возможность принимать участие в контестах, к которым ты не допущен по рейтингу?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Возможность есть и сейчас, только под другим аккаунтом :)
    → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Просто вне контеста.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Так не интересно. :) Ты уже видишь задачи, пишешь решения, а сдать ещё не можешь.

      Правда в случае допуска произвольных участников (в том числе опоздавших с регистрацией, но, конечно же, пишущих уже без рейтинга) приоритет в проверке будет отдаваться основным участникам.

      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Я хотел сказать — участвовать как все, только не занимая никаких мест (оставаясь где-то внизу таблицы положения) и без изменения рейтинга (конечно же). Кстати, пример такого вне-конкурсного участия можно увидеть на z-trening.
        → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Люди,в чем 3-й тест задачи D?

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Думаю там есть точки с одинаковыми координатами x. Поэтому если решение со структурой данных то обновление нужно делать после того как обработаются все точки с одинаковыми x.
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is problem solution available
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Yep
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Это не по теме . . . У меня гугловский браузер когда захожу на страничку рейтинг,то таблица вылазит за свои приделы,закрывая область моего профиля... это так и должно быть или я туплю? 
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Это у многих так... будет переделываться потом. Но странно что у тебя глючит.. на моём хроме всё норм
        → Ответить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Видимо зависит от разрешения. На 1280 нормально, но на разрешениях меньше могут быть проблемы.
          → Ответить
          • 15 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Конечно зависит. А ещё и от браузера. У меня уже после восьмого раунда проблемы начались. 1024.
            → Ответить
          • 15 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Кстати, такой вопрос:
            а смысл делать так
            Указывает на одну тему, но почему разница на 10?
            → Ответить
            • 15 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Ага, есть такая бага.

              Проблема в том, что во второй ссылке темы не видно, первого собщения.


              Вторые сообщения приходят на почту.

              → Ответить
              • 15 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Переписывался с Майком, оказывается всё просто. Комменты это отдельный объект который привязан к другому объекту. Это может быть топик блога, может быть обсуждением задачи и т.д. Т.е. эти ссылки никакой связи не имеют.
                → Ответить
            • 15 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

              Спасибо за ответ.

              → Ответить
              • 15 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Ну это уже довольно старая тема, что из мыла нет редиректа сразу к топику. Опять же спрашивал на эту тему, насколько я понял там какая то принципиальная проблема.
                → Ответить
            • 15 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Я не про редирект к топику из мыла.

              Я про то, чтобы к странице комментариев сверху прикручивался оригинальный пост.

              Кстати мы с тобой обсуждаем это не в той теме и в английской ветке к тому же...

              → Ответить
              • 15 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                :-D Есть такое. 
                Не в том дело. Прикрутить ссылку просто так незя. Там как то надо хитро подумать на сколько я понял. В общем это видимо в туду. :)
                → Ответить
    • 5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Where?

      → Ответить
15 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

У меня есть небольшое пожелание :

Я на автомате для задачи D завёл массивы с названиями i,b,r

И сперва не понял в чем проблема, когда циклом for(int i = 0; i < n; i++) стал ходить по массиву i[].

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

→ Ответить
15 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Ох уж эти лидирующие нули :)

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я использовал next_permutation(), тут с нулями все просто - проверяем что при перестановке первая цифра не 0.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Просто посортить числа, и, если первая цифра 0 и длинна числа не 1, то меняем первый ноль с первым не нулём.

      Зачем там next_permutation()?

      → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can anyone tell me in problem b  why we cant take m as integer and although m is given as integer

but if i am taking m as integer i am getting wrong answer. although  in problem statement  it is goven that  m may have leading zeros  but m is integer  so  no meaning of leading zeros.. so can any one tell me correct thing

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Leading zeros in M are very important, because they "take part" at constructing minimal number

    for example: M = 0123. minimal number is 1023. If you escape leading zeros in reading M you lost Zeros in result.

    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      first thing we dont have to find  answer for m we have to fing=d minimal number for n .

      so  ur example is nt correct

      i m asking here that what is importance of leading zeroes in an  integer 

      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        If you take m as an integer, there should not be any problems. Make sure you don't take n as an integer.
        → Ответить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Sorry, in the previous post I thought about I/O problem. But here is an algorithmic mistake, as explained in posts below.
          → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Sometimes providing corner cases helps much.
    I missed one such case in Problem B. Finally got ac just after the contest.
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    You can omit all corner cases if you read first integer as a string and sort it. Then you can just exchange first 0 with first digit != 0.
    → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    *first leading 0
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Как решается задача D?
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Мне кажется там нужен просто брут с хорошими отсечениеями.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Может его и можно впихнуть но получил ок с правильным решением(уме его доказываеть) со временем работы nlogn.
      → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      мне кажется ты не прав, и перебор тут не пройдет.

      сортировка + дерево отрезков.

      → Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я решил во время контеста зарешать тремя поисками самой неубывающей подпоследовательности, но не успел доотлаживать(.
    → Ответить
15 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
Hello,

I could not find enough explanation about the standing page, in particular:
- what does the penalty represent ?
- for each problem, I finally understood that I have to click on the "+" or negative number but is there a specific penalty for each failed submission ?
(is there a forum for questions related to problems ? I am quite curious about case 9 for problem B - Correct Solution)

It was my fist participation and I really enjoy the web site and how it works, thanks a lot !!
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится 
E:

for(i=0;i<n-1;i++)for(j=0;j<n-1;j++)a[i][j]=1+(i+j)%(n-1);

how to obtain this formulation? i use patterns but i need to determine a[i][n-1] by my self.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Очень понравилась задача Д, хотя омрачил меня тот факт, что формат входных данных оказался совершенно неожиданным, я думал что будет N строк в каждой из которых содержатся параметры для дам (как по мне это логичнее), получив ВА 3 я полчаса пытался найти баг, наверно я не один столкнулся с такой проблемой.
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Я нарочно сделал такой формат ввода. И, само собой, сэмпл 3 на 3. Да еще такой, чтобы ответ был один и тот же при обоих вариантах.
    → Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

@ADMIN    pls  make an statement about question b

in question  m is an integer

but  i got 3 wrong submission if i m taking m as integer

ans i got accepted wen i made  m a string.

why wrong on taking m as integer...?/? 

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Test:
    4
    04

    Answer:
    WRONG_ANSWER
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      @ADMIN  i dunno but wen taking m as 04  if one using int  m then it will be  4 and answer will be "OK"

      so  there is no mistake in int m 

      correct me if i am wrong

      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        For M = 4 answer is 4. But Valera's answer was 04.

        Look at the M and Valera's answer as string(not as numbers)

        → Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
can anyone tell me in problem C ,what tricks
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Any hints / explanation for Problem - D (Ball) ? Its a nice problem.
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How to do with Problem D？ Can anyone tell me？
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    I have sorted by first parametr and then make rmq where indexes were second parametr and value is third. Becouse of stecific rmq request you can use Fenvik tree insted of interval tree and I have done it.

    But i saw tthat some submited solutions are more easy.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      is problem D smilar to this one .
      http://www.spoj.pl/problems/MDOLLS/
      Quick Sort and Binary Search ?
      Sorry for my bad english .
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        No, they are not similar. Here we have 3 parameters to look for and range is [0,109] for each value, and at most 5x105 such triples and we need to just find for each value, if there is a value greater than this.
        ---
        @kuniavski: could you please explain it a little more. Each value can be as large as 109, so how are you using a BIT ?
        → Ответить
        • 15 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Of course firstly i mae them smaller. the absolute value are not necessary. So you can say that malist value is 1, next is 2 and etc. So values should be not more 5x105.
          → Ответить
          • 15 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Thanks. Done it :) . . superb problem it is ! Any other ways of solving it, other than 'sorting with x and using rmq ( or bit ) on (y,z) ' ??
            → Ответить
            • 15 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится
              Could you please describe this approach more specific?
              → Ответить
              • 15 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится
                Approach is, we sort it with X and process the bunch of entries with same X at a time.., thus reducing the problem to take care of Y and Z. As relative difference only matters, we can enumerate all Y's, thus getting them in range [1 - 5x105] in worst case. Now, with Y as key and its corresponding Z as value, (Y,Z).. we can use BIT, to store the cumulative maximum. From this, we can query "what is maximum Z for Y in range [1,y]?" in O(log n) and also can update this table in O(log n). I hope you got rough idea of what we are doing.
                ...
                I think I have written a well readable code.. you can check that by clicking the number of solved, beside this problem in the problems list. Submission id is 40387.
                → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      I don't know what is "Fenvik tree",  nor can i find it by Google it . Can anyone tell me ?
      → Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Проблемсет оч хороший, спасибо!
Только одно пожелание - можно условия задач делать более позитивными? (я про самоубийства). Ведь не сайт для готов же :)
→ Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

@ADMIN  can you please give us input.output of problems ...

so that we can find bugg in our programs

→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
How do you think, why 40676 doesn't pass, while 40679 is accepted?
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
а что за 9ый тест в задаче B? .. у меня пишет ошибка времени выполнения.. даже представить не могу почему там такое возникает! :-(
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
уже разобрался
→ Ответить
15 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Well after my registration I found that I'm on train to Beijing to attend APIO2010 when the contest started.

I calculated the time wrongly due to the timezone difference.

I wonder whether it will affect my rating. I really hope I can cancel my registration but it seems impossible to do so.

And I really hope that zero submissions will not affect the rating. (I don't know whether topcoder is like this due to the fact it doesn't support PASCAL).`
→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    For solving timezone problem now you can use this calendar (for Codeforces by darnley) or this (by me).
    I think possibility to check contest time at timeanddate.com will be implemented, but later.
    → Ответить
    • 15 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Thanks, but it seems impossible to cancel the registration now.

      Time on that calendar is still Moscow Standard Time (UTC +4), so i had to add 4 hours on it.
      → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        There is no need to cancel registration. The rating changes here only if you have submitted a solution.
        Yep, you have to add this calendar to your account at google.com (there is a link in bottom right corner), after that you'll see all events in your time zone. :)
        → Ответить
      • 15 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        "And note that with Google Calendar you can set SMS and e-mail notifications, in order to never miss a Codeforces round. Not only can you do this for a single event, but I also recommend you to go to the Settings menu and set automatic notifications for all events of this calendar."
        (Codeforces Calendar)
        → Ответить
15 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

@ ADMIN  whenever i got mail for new comments i got this url to .ru extension like

"http://mirror.codeforces.com/comments/349#comment-4505"

so u can make it   ".com"   for english users......

→ Ответить
  • 15 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    BTW (I'm from Russia), I receive urls from:
    codeforces.ru
    codeforces.com
    (and even!) www.codeforces.com

    Besides they have different cookies and I need login every time to make some action (answer, give plus, etc).
    → Ответить