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

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

Объявление: Все официальные участники, кто решил три и более задачи приглашаются 26 ноября в офис КРОК (ул. Волочаевская, 5) на финал Чемпионата. Победителей ждут призы, а подарки достанутся всем! Более подробная информация будет разослана по электронной почте.

Добрый день!

Совсем скоро начнется отборочный этап Чемпионата КРОК по программированию среди студентов МГТУ им. Баумана. В конкурсе принимают участие официальные участники чемпионата, все остальные будут в таблице результатов вне конкурса.

Соревнование проводится по широко известным правилам студенческого чемпионата мира по программированию ACM-ICPC. Продолжительность соревнования 2 часа. Допустимые языки программирования — C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml и D.

Раунд будет рейтинговым для див-2 участников независимо от того в конкурсе чемпионата участник или нет. Для див-1 участников раунд нерейтинговый.

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

Всем удачи!

UPD0. Соревнование завершено, всем большое спасибо за участие! Надеюсь, что проблемы с очередью не сильно испортили Вам впечатление от контеста. Завтра будут объявлены результаты отборочного раунда для участников в конкурсе. Рейтинг обновится совсем скоро.

UPD1. Появился разбор. Дополнительная информация для тех, кто участвует в подобном соревновании впервые:

Во всех задачах ввод/вывод стандартный. Примеры простейших программ, решающих задачу A+B, приведены ниже.

Pascal / Delphi:

    var
      a, b: longint;
    begin
      read(a, b);
      writeln(a + b);
    end.

Java:

    import java.util.*;
    import java.io.*;

    public class Solution 
    {
      public static void main (String[] argv) throws Exception
      {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(in.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());

        System.out.println(a + b);
      }
    }

С++:

    #include <iostream>

    using namespace std;

    int main(){
        int a, b;
        cin >> a >> b;
        cout << a + b << endl;    
        return 0;
    }
  • Проголосовать: нравится
  • +88
  • Проголосовать: не нравится

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

Questions will be available on English, right?

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

Сколько всего будет предложено задач?

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

how many problems exist?

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

rating will be updated based on div 2 users results or based on every users results?

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

Problems will be sorted according to difficulties?

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

why contest isn't rated for Div 1 ? will it be a bit easier ?

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

Какой-то из двух обратных отсчётов явно неправильный: http://i.imgur.com/QeQ7O.png

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

    тот который справа — видимо до конца регистрации, слева — до соревнования.

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

      Нет, ошибка в том, что один из них использует время сервера, а другой — моё локальное время без поправки, которое есть GMT+2, а не GMT+4, как в Москве.

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

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

А на каком языке будут задачи?

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

    На французском) А ещё, для тех , кому необходимо, будут так же доступны условия на китайском)

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

    На русском и английском.

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

I had registered in this contest, why i still see Register now ?

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

    I have this problem too, Can you solve it? Also there are different time to contest beginning, what does it mean?

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

      One countdown is for contest start, other — for registation.

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

        Will Registration continue till the contest's finish?

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

        It's quite confusing, I thought the contest would be starting in around 3 hours, but it's starting in less than 1 hour! (~45 minutes)

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

Если я буду использовать PHP обязательно ли объявлять заранее все переменные?

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

    Попробуйте сдать какую-либо простую задачу на PHP в архив задач. Вот пример решения задачи 233A - Идеальная перестановка

    <?php
    $a = range(1, trim(fgets(STDIN)));
    if(count($a) % 2 == 0)
    {
        $b = implode(" ", array_reverse($a));
        print $b;
    }
    else
    {
        print "-1";
    }
    ?>
    
»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How many problems exist? And how long does contest take ? Thanks

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

About 200 new participants , excluding the official contestants . I hope people have not made multiple accounts like last time

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

In queue 4ever...

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

    No more than 10 minutes. About 8-9 minutes mostly. We are sorry about the queue, it is the result of ACM-ICPC mode + very easy tasks for many participants. We will make conclusions and prevent this next time. Sorry again about 9 minutes queue.

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

    Happy that contest is held on CF , upset that CF has a bit weak server. :|

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

Its frustrating to see submission in queue for so long!! Hope admins will "Unrate" this contest. And please run cf in safe mode during contests.

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

    unrate because your result is unsatisfactory? conditions were the same for all of the participants, am I right?

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

      You can disagree but it is rated just among div2 and my rating will surely increase today, so it is not unsatisfactory to me.

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

just fixed

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

Собственно, вопрос: если есть уверенность, что после удаления лишних тестов полнота набора тестов не уменьшилась — зачем было изначально пихать в набор эти самые лишние тесты в таком количестве? Чтоб солидней выглядело? Или авторам поставили условие "тестов должно быть не меньше, чем..."

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

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

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

      мб реджадж после контеста на "старом" наборе? От греха подальше.

      Хотя тогда не совсем понятно, что делать с решениями, которые упадут на удаленных тестах (если такие будут).

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

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

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

I like this exam . You?

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

Может стоит выставлять таймер на главной странице всегда сколько до соревнования? Я считаю, что удобнее смотреть сколько до начала на главной, чем помнить во сколько оно. Из-за бага регистрации пропустил раунд, оно для меня должно было начаться в момент окончания(

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

Amazing system testing in last.

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

Nice problems! Any tips for C?

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

    IN EDIT

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

    just count it from behind.. if n=7 then count how much we take coin from - 3 6 7 (we must make chest-6 and chest-7 empty) - 2 4 5 (we must make chest-4 and chest-5 empty) - 1 2 3 (we must make chest-2 and chest-3 empty)

    then add the coin left in chest-1

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

Nice problem set.

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

How long time take the Rating's Upgrade?

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

I like these kind of contests :-)

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

in problems F, i wonder whether "the last n seconds" means the last N seconds from the last record, or the last N seconds from any other records?

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

it was awful! wrong testcases .. long time of judging ...

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

Wrong Wrong Wrong! Problem D input 3 -1 3 5 3 -1 4 5 4 -1 according to accepted solution like: http://mirror.codeforces.com/contest/245/submission/2591027 http://mirror.codeforces.com/contest/245/submission/2590877 out put 7 7 5 and that's WRONG if you need to reconstruct array b[][] from accepted out put it will be -1 7(7&7) 5(7&5) -1 7 5 7(7&7) -1 5(7&5) = 7 -1 5 5(7&5) 5(7&5) -1 5 5 -1 so, i think it's wrong, is it?

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

    It's not. Your input is wrong, since it is impossible to generate it in the way, described in statement.

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

    and solutions which accepted input 3 -1 1000000000 1 1000000000 -1 1 1 1 -1 out put 1000000001 1000000001 1 and problem (D) said (0 ≤ ai ≤ 109) CONTRADICTION! how to accept it?

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

      "It is guaranteed that there is sequence a that satisfies the problem conditions. If there are multiple such sequences, you are allowed to print any of them."

      So your input is wrong, because there is no answer for test case.

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

8 задач на 2 часа. Скорость набора начинает играть важную роль.

ИМХО — можно было бы трёхчасовой контест, пусть победителей определяет время сдачи.

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

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

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

Если у меня выбран отдельно какой-то дивизион, то "результаты друзей" не работает (меня просто бросает опять на общую страницу с результатами).

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

Можно сделать так, чтоб при нажатии на соответствующую кнопку бросало на ?friendsEnabled=on, вместо текущего /friends/true (что было, как в рейтинге архива)? Или как-то иначе это исправить — но чтоб я мог посмотреть, какие места заняли участники с моего френдлиста отдельно по второму дивизону? Ведь функционал есть, с ?friendsEnabled=on все работает, но это не очень удобно — вручную адрес дописывать.

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

Мне кажется, или задача G "Возможные друзья" была где-то ранее, ну разве что только без первого абзаца? Именно в формулировке соц сети с возможными друзьями? Если так, не напомните где?

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

Will there be any official editorials ?? If not , please somebody take the trouble of writing it (and in English too) because I liked the problem set very much and would like to know their solutions

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

Мда, надо учиться, учиться и еще раз учиться... Только что зарегистрировался на дорешивание, просмотрел решения, подправил в первой и второй задаче по полстрочки в своем решении — и прошел все тесты. Видимо, опыт имеет значение.

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

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

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

Can anyone explain the solution to problem H? I'm a big newbie (you can check by my rating ;p). It's just a simple DP O(n^2)?

thanks!

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

    Yes. dp[i][j] = number of palindromes in the [i,j] substring.

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

    First you check this:

    isp[i][j] = "is the substring [i,j] palindrome?" After that you can try this simple DP:

    dp[i][j] = number of palindromes in the [i,j] substring.

    So it's easy to see that dp[i][j] is equal to dp[i+1][j] + dp[i][j-1] — dp[i+1][j-1] + isp[i][j].

    The intersection between [i,j-1] and [i+1,j] is equal to [i+1,j-1], so "dp[i+1][j] + dp[i][j-1]" calculates dp[i+1,j-1] twice and you've to subtract this one more time to maintain the correct result. Also, you've to add 1 in the solution if the substring [i,j] is palindrome.

    A lot of contestants solved this problem by using Manacher Algorithm + DP, but it's only a matter of time complexity.

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

      Thanks a lot, nice explanation!

      At first I though that I would have to use Manacher, since I haven't study this algorithm yet, I just gave up. Later I saw others contestants solution and I saw this DP, that's why I asked.

      Thank you very much!

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

        Yes, but Manacher give us the length of the longest palindrome centered at Ti. But, between both solutions there isn't a big difference in time complexity.

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

      how do you check isp[i][j] efficiently

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

        isp[i][i] = 1, isp[i][j] = isp[i+1][j-1] && str[i] == str[j].

        It means, if the substring [i+1,j-1] is a palindrome one and str[i] is equal to str[j], so [i,j] is a palindrome substring.

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

      I tried solve with manacher however not work, someone could tell me that I have bad

      http://www.codeforces.com/contest/245/submission/2595260

      thx

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

      I get this solution only 5 minutes after understand this problem Anyway, one karma for you :D

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

I think that in this round there was a discrimination to some contestants. More precisely, I think that time that one was waiting in queue was calculated with the rating the contestants have.How is possible that I waited around 10 mins for every submission and some people had already solved 2 problems in the first 5 minutes. This is not a good thing, and I hope that I am wrong, because if it is true, it is really unethical.

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

    Queue was formed based on submission times. Those that solved first two problems really fast were in the beginning of the queue.

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

    It is obvious thing.. The queue was only formed becuase there were many submissions which the judge could not handle all at once. Obviously during the first 5 minutes there were very few people who made submissions and so received quick judgements. And no points for guessing that these were high rated coders.

    I hope you had done a lot of research before posting this , becuase this is a algorithmic platform , judge here is not a rascist and decisions are not taken here based on colors .**Colors only affect when you get upvotes and downvotes in the community** :P

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

Can someone explain the solution for problem G?

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

    The idea is similar to the last CF problem D (div 2). There are N guys (N is at most 2*M) and M pair of friends. You just do a brute force to check for all x, how many y has the most common friends (to check common friends you need a linear algorithm, like sorting everyones friends and doing a two pointers thing, or even easier calling set_intersection ;) ). It seems to be cubic, but its not, for one guy you do at most N*A + M operations (A is the number of his friends), the total complexity will be N*A + M + N*B + M + N*C + M + ... = N*(A+B+C..) + N*M = N*M + N*M = O(M^2). Here is my implementation if it is not clear yet: http://mirror.codeforces.com/contest/245/submission/2602015

    I hope it helps :)

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

      i used another method, for each one, i get a set which has all the friend of him, so each pair in this set pair(a,b) should add one point. than i got a matrix, a[i][j] means how many friends, i and j have in common. this methods looks like n^2, but my solution time out at test 8, not sure why, anyone has any ideals? maybe stl just very slow....http://mirror.codeforces.com/contest/245/submission/2607465

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

        Try to replace strings by numbers, so you will not need map to hold the friends list.

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

Так сколько человек переходят в следующий этап? На мои вопросы не в анонсе, не в переписке, не где не отвечают.

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

    А минусующие, видать, знают ответы на мои вопросы, но набирать текст они не умеют, вместо этого минус нажимают.

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

      Объявление: Все официальные участники, кто решил три и более задачи приглашаются 26 ноября в офис КРОК (ул. Волочаевская, 5) на финал Чемпионата. Победителей ждут призы, а подарки достанутся всем! Более подробная информация будет разослана по электронной почте.

»
12 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Более подробная информация будет разослана по электронной почте

Мне одному письмо не пришло?

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

Похоже, что тесты не полные к задаче С. Неверное решение 2638262, которое на

3
1 9 1

выдает "1", проходит все тесты. Если в нем исправить ошибку ("k > 2" на "k >= 2") 2638264, то оно начинает выдавать на указанный пример правильный ответ "9", и при этом тоже проходит все тесты.