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

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

Всем привет!

Сегодня вас ждет раунд по старым-добрым ACM-ICPC правилам. Да, это будет рейтинговый контест для второго дивизиона, а участники из первого дивизиона смогут принять участие вне конкурса.

Задачи для вас делали Nerevar, natalia, MikeMirzayanov и Edvard, а Delinur перевела задачи. Спасибо всем за помощь!

Желаю удачи!

UPD: Рейтинг будет обновлен позже.

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

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

Hello.

I'm almost new here, and I'm wondering what the "ACM-ICPC Rules" will be like. I am thinking that, in this round, when we submit our source code, we will be told the results of all tests, not only ones of pretest, and there will be no Hacks. Is this right?

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

Очень жаль, что утром. Большинство школ нашего города сегодня пишут пробный ЕГЭ по физике. =[

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

    Зато некоторым (и мне в том числе) не придется просыпаться в 2 часа ночи. Не все же в одном часовом поясе. Хотя, конечно, неудобно, если раунд совпадает с каким-нибудь экзаменом, пусть даже и пробным.

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

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

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

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

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

А с opencup это не пересекается? Сегодня opencup будет?
А то в расписании тур раньше был, а сейчас opencup.ru не виден и посмотреть негде.

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

    Вроде как да — 22.04.2012 11:00 "GP of SPb"

    UPD Не будет

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

      "В связи с переносом Чемпионата СПбГУ этап Открытого Кубка 22.04.2012 отменяется. О дате ГП СПб будет сообщено дополнительно. Также в связи с переносом выходных и праздничных дней в РФ Гран-При Урала пройдёт 30.04.2012, а Гран-При Москвы — 07.05.2012 в 11-00."

      UPD: Что-то эта надпись как-то периодически раз в полчаса пропадает. И в расписании — то сегодня опенкап есть, то нет.

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

Честно говоря, отсутствие доступа к opencup.ru и snarknews.info как-то напрягает. Если с доступом ничего сделать нельзя, то надо хотя бы объявления сюда дублировать.

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

А сколько задач?

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

Нашел баг: те кто регались вчера, но после пересчета рейтинга попали в див1 остались в конкурсе.

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

Задачи упорядочены по сложности?

»
12 лет назад, # |
Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

I think, this contest will be difficult :(

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

More information about contest please !!!

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

Эх... Нашел тест "2 9" для B за минуту до конца :(.

»
12 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Why binary search tag is added to problem E? http://codeforces.com/problemset/problem/180/E

I solved it in O(n + m) and I no see any place to use binary search.

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

спасибо авторам задач, было интересно)

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

When will it be rated?

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

Большое спасибо за задачу E! Она очень классная.

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

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

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

    Кстати, нашел баг, пока что не нарисовали табличку и не поменяли рейтинг, но у меня, и у zakharvoit изменился цвет, хотя в комментариях отображается нормально.

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

    Там можно было за квадрат решать.

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

      But in Codeforces strlen of string will be 10^5. It will be Limit in time when we are solving in N^2.

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

How can this be? Some of submissions are quite similar but are written by different people. for example submission number 1609559 and submission number 1609912 for problem E.

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

    It shouldn't be. Admins should take a look at that. If you dig a bit deeper you might notice that the people placed #7, #11, #12, #14, #18, #19 have matching solutions (at least for some problems). They all come from the same city, so I suppose they participated together.

    In general: I have no problem with people joining the contest together (not sure if that would be against the rules) but simply copying solutions is very dishonest towards all other contestants. I don't even see the purpose of cheating here. Do people get an ego boost if they get an increased rating based on somebody else's solution they submitted?

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

      Will this round be unrated ? :/

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

        Probably after update rating, cheaters will be removed :)

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

        I think the ratings have been updated but are not displayed...Take a look at the cheaters profiles...They are all Blue now and this was their first contest..So I guess the ratings have been updated .VNBZTY and Liu_Ts

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

      "but simply copying solutions is very dishonest towards all other contestants."

      I agree this. If some people copied their solution one another and get high ranks together, the position of other people would be lower, and their rating would be lower.

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

    I think both VNBZTY and Liu_Ts are the same people..They submitted the same codes to all the problems(even the variable names and their initial values are same) , solved each problem in exactly the same language and always VNBZTY submitted the code and if it was accepted then within 10 minutes Liu_Ts submitted it...So much cannot be mere coincidence. Take a look at their submissions and compare it ..VNBZTY submissions , Liu_Ts submissions

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

    Administrator will accept it to first user after finishing contest but in it contest it will accept to both users.

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

Будет ли разбор задач?

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

На A задачу нужно было жадник писать? Или есть другой способ?

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

А читеров удалять будут?

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

Hi, I am really new here and I want to know whether there is problem set analysis about codeforces round here or where can I find them ?

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

когда рейтинг пересчитают?

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

No matter how late it will be, will ratings definitely be updated?

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

как решать B?

»
12 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

What is the meaning of UPD? We can see this in every contests in Codeforces.But I can't understand what this means.

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

Can anybody tell me how to solve problem E?

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

    So here is a simple solution: I maintained an array of vectors vector arr[] where arr[i] contained the array of different paints between any two consecutive i. Therefore arr[i] would be empty if the string had no or just one element of the type. If inp= 1 2 3 1 2 3 5 1 1 then arr[1]= 2 3 0 Then, I iterated through all the array of vectors to find the maximum number of consecutive elements that sum to <=k. This is the code for the later part

    for(int i=1;i<100001;i++)
      {
        if(v[i].size()==0)continue;
        int back=0;
        int front=0;
        int sum=0;
        bool frontmoved=true;
        bool backmoved=false;
        while(front!=v[i].size())
        {
          if(frontmoved)
    	sum+=v[i][front];
          if(backmoved)
    	sum-=v[i][back-1];
          if(sum<=k)
          {
    	if(max<front-back+2)max=front-back+2;
    	front++;
    	frontmoved=true;
    	backmoved=false;
          }
          else
          {back++;backmoved=true;frontmoved=false;}
          if(front<back)
          {front++;frontmoved=true;}
        }
      }  
    
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

а почему у задачи F тег графы?

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

    может из-за того, что для решения этой задачи знать что такое граф не обязательно?

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

когда рейтинг пересчитают то?

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

Is there problem analysis for this round?

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

More than 20 hour passed now, when will the rating update?!

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

    Be patient, maybe they ( or the server) are busy now. The main reason you are here because you want to practice more, not to get high score to be contemplated :)

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

Может раунд сделают нерейтинговым?))

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

I would be greatful if someone would provide me a detailed explaination of this source. Also , any other thoughts about problem B would be very helpful. Thanks ! :)

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

Test 57 of problem D???

No idea why my submission fails at test 57. https://codeforces.com/contest/180/submission/49496546