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

Автор MikeMirzayanov, 14 лет назад, По-русски
Добро пожаловать и удачи на раунде!

Напоминаю, что если у вас возникают вопросы по задачам, то лучше всего использовать веб-интерфейс их посылки со страницы задач.

Позже в этом же посте мы будет обсуждать прошедший раунд.

Желаю высокого рейтинга,
MikeMirzayanov.
  • Проголосовать: нравится
  • +17
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
Здравствуйте, по этому контесту есть два вопросика:
1) Где(как) просмотреть исходный код своих отправок?
2) Ожидаются ли разборы задач и когда ожидать?

Спасибо.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Первый тест в задаче B какой? У меня wa1 стабильно...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Офигеть!

    В решении у меня было такой код для считывания строк:

    while (true) {
    c=getc(stdin);
    if (c=='\n' || c==EOF) {
    a.push_back(str);
    if (str.size()>lenmax) lenmax=str.size();
    str="";
    if (c==EOF) break;
    } else str+=c;
    }

    Я получил WA1.

    Переправил на:

    while (getline(cin,str)) {
    a.push_back(str);
    if (str.size()>lenmax) lenmax=str.size();
    }

    Получил AC.

    Я не понимаю, чем первый код по функциональности отличается от второго?

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Вероятно проблемы с переводами строки (ибо перевод строки не только '\n', но и '\r' в некоторых операционных системах).
      Сам сталкивался с подобной проблемной в частности на сподже.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится
      у Вас будет 1 лишняя пустая строка считана. Типа файл:
      abc\n
      EOF
      у Вас будет считано 2 строки - abc и пустая
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Спасибо за сообщения.

    Мда. Из-за такой тупости запороться.

    Что еще раздражает, так это постоянные минусы за сообщения. Че за неадекваты их ставят?

14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Спасибо большое за контест, но я очень надеюсь, что в будущем не будет задач с чтением до конца файла, ибо:
1. Очень тяжко тестить в Idea без перенаправления потоков ввода
2. У меня по какой-то неизвестной науке причине получался PE 4 по первой задаче на Java (чтение шло через BufferedReader)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    на счет входных данных до конца файла, да, это действительно не очень приятно. все время какие-то баги в IO ловишь, по части из-за непредсказуемости поведения стандартных библиотек. обидно это)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да и в делфе неудобно, приходится выёживаться...
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Вот что у вас было
    Exception in thread "Thread-0" java.lang.ArrayIndexOutOfBoundsException: 1
            at Chat.solve(Chat.java:47)
            at Chat.run(Chat.java:23)
            at java.lang.Thread.run(Thread.java:619)

    Мы улучшим систему, чтобы в таких случаях приходил RE.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Как решите проблему - сообщите способ решения Олегу тоже, а то опять я в PE ударился на последнем кубке...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Проблема решена. Для того, чтобы jvm на неожиданный exception возвращала exit code отличный от 0 надо запустить ее с javaagent-ом, который установит handler для unexpected exceptions. Этот handler и должен делать System.exit с нужным exit code.

        С этого момента неожиданный exception из любого потока приведет к runtime error.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
что-то странное в 8-мом тесте задачи А.
у меня решение на С++ стабильно там падало (например, посылка 10770), а идентичное решение на Java (посылка 12492) прошло.
вообщем, смешно даже, слил контест из-за сложнейше задачи... наверное час А решал....)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Что интересно, у меня не получилось сдать эту задачу на Java, зато прошло то же решение на C++ :)
  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    У меня была та же проблема.
    Вот такой вот код не проходит:
    while(!feof(stdin)) {
    char buf[2000];
    buf[0] = 1;
    gets(buf);
    // if (buf[0] == 1) break;
    input.push_back(buf);
    }
    А если закоменченную строчку раскомментировать - то проходит.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      вот ведь подстава. а я по другому проверял... но по идее тоже самое должно получаться:
          int total = 0;
          while( !feof( stdin ) )
          {
              char buf[ 2024];
              gets( buf );
              std::string str = buf;

              if( str.empty() )
                 break;

              if( str[0] == '+' )
              {
                  std::string name = str.substr( 1 );
                  names.insert( name );
              }
              else if( str[0] == '-' )
              {
                  std::string name = str.substr( 1 );
                  names.erase( name );
              }
              else
              {
                  int p = str.find_first_of( ':' );
                  if( p == std::string::npos )
                      break;
                
                  total += (str.size() - p - 1) * names.size();
              }
          }
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      нда, понял..
      гетс иногда вообще не срабатывает и строка последняя дублируется...
      вот фигня)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, что за первый тест на задаче D ?
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
забавно, что после этого контеста вся первая десятка - майоры =)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Не понимаю как можно решить C за 10-15 минут.
У меня решение почти такое же как и в E.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    она же за два прохода линейных решается...
  • 14 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    Будем решать при помощи ДП. Пусть d[i] - максимальная длина правильной скобочной последовательности, начинающейся с i-го символа строки. Пусть n - длина строки, тогда d[n]=0.

    Если i-ая скобка ")" - то d[i]=0

    Иначе, если i-ая скобка "(", а (i+1)-ая скобка ")" - то d[i]=2+d[i+2]

    Если i-ая скобка "(", а (i+1)-ая скобка "(", то возможны два варианта:

    1) Если (i+1+d[i+1])-ая скобка ")" - то ответ d[i]=2+d[i+1]+d[(i+1+d[i+1])+1]

    2) Если (i+1+d[i+1])-ая скобка "(" - то d[i]=0.

    Вот и все решение :)


  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    А в чем проблема решить E за 15 минут? :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      Ну да, время я как-то не подумав написал.
      Но C и за 5 и за 7 сдавали, а E точно так не сдашь (с учетом прочтения и продумывания).
      А у меня решения почти идентичные в обоих задачах, вот и почувствовал, что перемудрил в С.
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

> SKYDOS писал:

> 1) Где(как) просмотреть исходный код своих отправок?

Актуальный вопрос!

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
я, как самый хитрый, предлагаю в тестах задачи А убрать символы перевода строки в последней строке файлы и перетестить посылки... а то, не честно получается и-за того что gets в С++ криво работает, я и думаю еще некоторые люди слили контест... )

представьте, какая происходит деморализация когда почти час не может сдать задачу А.... как тут решать все остальное)

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    +1. Я еще за то, чтобы убрали в последней строке символ перевода в задаче B (т.е. последняя строка и сразу EOF). И сделали реджадж.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      так в Б убрать и не получится, там же по условию пустые строки могут встречаться. а вот в А по условию пустых строк быть не должно...
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        Вообще, простое
        while ( cin >> s ) // или while ( cin.getline(s) )
        {
        ....
        }

        у меня работало что в A, что в B, что во всех аналогичных задачах.
        Так что непонятно зачем здесь что-то еще придумывать, и рассматривать разные случаи.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Нет, ретестить мы ничего не будем. Но впредь в подобных задачах будем стараться задать количество строк в явном виде.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    То, что последняя строка входного файла заканчивается символом перевода строки, нормально и правильно. Специфика работы функции gets - ваша проблема как программиста, решившего зачем-то ее использовать.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Странно, у меня с
      while(gets(s))
      обе за задачи A и B прошли без проблем.
      Может из-за того, что я под MS VC отправлял.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        ну да, так пройдет.
        а я просто не знал что gets может NULL возвращать, и думал что он как минимум '\0' в читаемый буфер запишет, если ничего не прочтет...
        вот и стал паниковать)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      так дело не в специфики...
      просто, из условия задачи не ясно что такое строка входного файла.
      1) это, может быть последовательность (возможно пустая) символов заканчивающаяся '\r' или '\n' или '\r\n'
      по этому определению в тексте "\r\n"  - одна пустая строка, а в тексте "test"  - вообще ноль строк.
      2) или же она может заканчиваться еще и концом файла, тогда в
      "\r\n" - две пустые строки.

      в задаче А пустые строки не допустимы по условию.

      • 14 лет назад, # ^ |
          Проголосовать: нравится +12 Проголосовать: не нравится
        FYI

        while( gets( s ) ) { }

        будет работать как в случае если в конце последней строки есть перевод строки, так и если нету.
        в целом фраза "Н строк" не обозначает ни наличия ни отсутствия перевода строки в конце. любому человеку мне кажется понятно, что файл с 20 непустыми строками, в конце последней из которых есть перевод - это файл именно с двадцатью строками, а не с 21-ой, верно?
        и файл с 20-ю строками, в конце последней из которых нет перевода - это тоже файл с 20-ю строками.
        Так что, казалось бы, надо просто выучить "while( gets( s ) )" :о)
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Ставить перевод строки после последней строки файла — правило хорошего тона.

          Простейший пример того, что это правило удобно — склейка двух текстовых файлов. Если и в файле перевод строки не поставить, и при обработке не задуматься об этом, получится, что к последней строке первого файла приклеится первая строка второго.
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Приятно порадовала скорость проверки. И задчи понравились. Так что большое спасибо за раунд.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Слово "приятно" в предыдущем посте следует убрать(осталось от выражения "приятно удивила") :-) Да и понравились мне не задчи, а задачи. Прошу прощения, просто спешил поделиться впечатлениями.
14 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится
It was great that all feedback was almost immediate. Good job on optimizing the judging!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
вопрос не по теме конечно, извиняюсь, но меня одного через каждые пять минут выкидывает с сайта? Приходится каждый раз заново авторизоваться.
Нельзя ли сделать как в Гугл, чтобы один раз авторизовался и всё?

Браузер Firefox, куки после выхода _не_ чищу.

Спасибо.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Меня тоже частенько выкидывает, да и язык меняет регулярно. Google Chrome, авторизация через Google Account
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Спасибо за CF#5.

подскажите плз в каком направлении двигаться в задаче D и задаче E где надо найти количество пар.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да, я тоже сначала в Е недочитал условие, потом понял-таки, но схватил TLE #16 видимо из-за тупого перебора. Может там какой циклический список надо было прописать :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      если последовательность будет отсортирована тогда, всего пар будет 
      n*2 - 3, может быть тут что то на основе отсортированности  надо думать?
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        предположение такое:
        найти максимальную возрастающую последовательность, посчитать пол-во пар для них по формуле, и прибавить остальные которых уже будет меньше. 
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          Если все числа различны, то задача сводится к следующей.

          Для каждого числа i от 1 до n найти
           - первый элемент от a[i] по часовой стрелке и больший его (пусть его номер равен L[i]), и
            - первый элемент от a[i] против часовой стрелке и больший его (пусть его номер равен R[i]).

          Тогда ответ на задачу равен сумме , где f(i)=0, если L[i] и R[i] не существуют, f(i)=1, если L[i]=R[i] и f(i)=2, если L[i] ≠ R[i].

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

          Да, забыл сказать, что величины L[i] и R[i] могут быть найдены за линейное время алгоритмом очень похожим на КМП.
          • 14 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится
            Там должна быть сумма .
            Без компиляции в техе, конечно, трудно уследить, что получится.
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Поправьте, пожалуйста, слово "Отформотируйте" в условии к задаче "B. Выравнивание по центру".