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

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

Всем привет!

Codeforces Round #258 (Div. 2) начнется 24-го июля в 19:30 по московскому времени. Как обычно участники из первого дивизиона могут посоревноваться между собой вне конкурса.

Раунд был подготовлен PraveenDhinwa и мной (JuanMata). Это наш второй раунд Codeforces. Надеемся, что не последний.

Мы старались, чтобы условия задач были понятными и интересными для всех. Очень хочется, чтобы раунд вам понравился. :)

Отдельное спасибо MikeMirzayanov за создание Polygon и Codeforces, Gerald за помощь в подготовке задачи, и Delinur за перевод условий задач на русский язык. Без их помощи соревнование не состоялось бы.

Желаем всем участникам удачи и высокого рейтинга. :)

UPD: На соревновании будет использоваться динамическая разбалловка.

UPD: Соревнование завершилось. Разбор уже здесь. :)

UPD: Поздравляем победителей. лучше 8 (единственные, кто решил все задачи):

  1. skank
  2. western_theory
  3. jurbhm538
  4. chenrui9551
  5. zhouhebin
  6. MaxKU
  7. jmas2711
  8. hzwer

UPD: Замечательную статистику от DmitriyH можно посмотреть здесь. :)

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

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

Hey...It's time to make a Div 1 round! :)

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

Second time from India and third time from Indian subcontinent... :)
*** Editorail of your last round (Round 251) was awesome... Hope the best for this time, too... :)

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

Who is going to be the main character? Devu again? :D

Good Luck

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

Why isn't this post on the home page too like all the other contest announcement posts? EDIT:fixed

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

Thanks, for providing the link of polygon. I was unaware of it.

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

    You could just google it !

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

      I was initially unaware of polygon, I only come to know about it through a blog post. I did not really know that everybody can make problems for even their own contests. polygon is quite nice :)

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

I know JuanMata personally and I can vouch for two things.

One is clear problem statements.

Another is — expect buttloads of football.

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

What was your first Codeforces round that you made its problem statemets?

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

There was a notification that today codeforces will not be available during some time, can somebody please tell me the exact timings when the site will be down, I forgot to note that down :(

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

why 258 is BOLD?

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

Wa!So nice!

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

Wow, such contest, very good, but I'm too young, too simple and sometimes naive. But your contest makes me feel "EXCITED"!

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

Good Luck JuanMata!!

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

and scores??

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

I like the editorials of PraveenDhinwa . They are awesome at codechef and hope here also .

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

YESSSSSS another JuanMata CONTESSSST!!!!

^_^

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

Even though the scoring is dynamic Please can you accept my request to sort the problems in increasing order of difficulty(According to you) so that I am atleast sure of solving the first two problems and don't have to click on standings again and again to confirm which problem is the most solvable .

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

UPD: It is decided to use the dynamic scoring system.

WHY??? :(

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

dynamic scoring = rating drop (in my case)

...but maybe this time finally :-D Never give up!

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

    I think this contest will prove exception to " rating drop (in my case)" :)

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

      If it really prove exception ,it will be my first time to be DIV1 let us play the game till the end and see the results :)

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

        haha, same here, currently I'm a little closer to DIV I, but it can be different after the contest, good luck ;-)

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

          anyway whatever the results I'm happy to solve D ,I think it's my first time ,I need only 6 point for DIV1

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

    same for me, I'm too unlucky in dynamic score

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

I'm so sad when my points gone down and my name change to be green. I will be more hardly.

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

блин, опять динамическая разбалловка :(

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

i am a new user of codeforces can anyone help me please? what does DIV.1 and DIV.2 mean?

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

    When You are a beginner , you are attending the contest from DIV2 . When performing good in some DIV2 contests and achieving a handsome rating(1700+) , you will be able to attend the contest from DIV1.

    the problems of DIV1 are harder than the problems of DIV2. Good Luck :)

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

Задачи идут в возрастании сложности?

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

Dynamic score is ALWAYS dramatic... Can' t adjust the contest very well... And NO new users-without-any-submissions spoil our fun again...

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

Dynamic scoring is usually not very good!

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

In fact,I'm not good at dynamic scoring system.

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

4255 till now ,seems that we will have a long queue :)

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

I register for the contest but after that i realize i can't participate. very sad. wish all participants high rating!

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

Уже 3 раза нажал на флаг России!

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

I didn't see the part of problem D that string is only consisted by 'a' and 'b'. In my opinion you must wrote this important part of statement in problem statement, not only in input.

Btw, great contest, thank you.

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

Problem statement should be tested more carefully before launch. Hope next time we'll not be bother

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

Понравились задачи Д и Е, но я их не решил, а остальные — скучные((

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

С за 16 секунд до конца сдал. UPD: Прошла тесты.

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

Как решать D?

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

    Заметим, что хорошей будет любая строка, у которой первая буква совпадает с последней.

    for (int i=0;i<st.size();i++)
    {
     calcc[st[i]][i%2]++;
     ans1+=calcc[st[i]][1-i%2];
     ans2+=calcc[st[i]][i%2];
    }
    cout<<ans1<<" "<<ans2<<endl;
    
    • »
      »
      »
      10 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      а можно чуть подробней про массив calcc?

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

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

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

    это смешно, но я пытался решить задачу для всего алфавита...

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

Hey guys , I can't see others submission even after locking my problem.This problem is from the beginning. I lock my problem , I go to standings , I double click a submission of my locked problem. then I click the submission number. But nothing happens. After contest it's just fine. But I can see during the contest;. Why?

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

    During the contest, you can only see the codes of people in your ROOM after you lock. The way to do so is in the Room tab.

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

    you must go to the your room, not standing.

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

    You can see and hack only solutions of contestants in your room, so go to your room instead of standings

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

Awesome contest! Thanks, JuanMata and PraveenDhinwa :)

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

I suspect that problem B is difficult to hack, and there are small amount of hacks, but some systest fails will apear.

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

    Got WA on Test 74 :(

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

      I solved problem B incorrectly at 35 min. Later I tried to find mistakes, and found that tests like "3\n2 3 1" do not pass, because answer is "no", but program gives "yes\n2 3". I rewrote code, and had 10 minutes to search the same bug in codes of others, but it was difficult to understand whole long codes, and I didn't try to use this or more difficult test.

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

      I got WA on Test 69, because I did not take into account when n is 1 :(((

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

    507 sysfails! Initially 2187 -> later 1680 !

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

Nice round. Congrats to the authors! How to solve E ?

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

How was problem C supposed to be solved?

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

    First, the condition is n%3 == 0. |Solve this system of equations : |x1-x2| = d1, |x2-x3| = d2, x1+x2+x3 = k with x1,x2,x3 is wins of team 1,2,3. Have 4 cases to solve. After check (n-k) is enough to give x1,x2,x3 to X1,X2,X3 satisfy X1=X2=X3=X.

    • »
      »
      »
      10 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
      5
      3 0 0 0
      3 3 0 0
      6 4 1 0
      6 3 3 0
      3 3 3 2
      

      What with sample 5? It's impossible to play only three matches and have differences three won between 1v2 and 2 won between 2v3.

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

        yes, after k = 3 games this situation is impossible.
        the information given by our friend is inconsistent (what a bad friend, spoiling the football tournament for you! :P).
        so the answer is no by default.

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

      Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.me/contest/451/submission/7234615

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

      Thanx for explanation.I have implemented in the same way suggested by you in problem C but I am getting WA on test 4 and I am unable to determine the bug .Would you please take out your valuable time for it.Any help will be appreciated.Thank You. http://codeforces.me/contest/451/submission/7234615

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

    test for

    d1 =  ± d1

    d2 =  ± d2

    , always checking if you can have K games with those differences. doing so, you just have to solve a system of linear equations:

    Δ V1 + d1 = Δ V2

    Δ V1 + d1 + d2 = Δ V3

    Δ V1 + Δ V2 + Δ V3 = N - K

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

    I used binary search on the winning value of the middle team. Firstly , I have four case ++,-+,+- and --. Now for each case I tried to figure out the configuration that would fit into k. You can see my submission ,7228843.

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

Перед отправкой решения меня выкидывало из аккаунта.У кого ещё была такая же проблема?

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

    Надо поставить галочку "Запомнить на месяц" при входе

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

Wow, such fast system test which only cost 7 minutes.

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

System test is so fast! And I am very happy because I solved four problems in Div2 for the first time!

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

Give us editorial, please

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

worst contest that i see in my life!!!

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

WA on test case 67 :(

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

I scared I will get down rating

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

congratulations TankEngineer !

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

The contest was great! Btw, how to solve problem D ?

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

    Suppose you have found the number of odd and even palindromic substring for the first few characters of the string. For example, aabaaabb have 8 even palindromic substring and 13 odd palindromic substring. At the same time, we maintain the number of 'a's at even and odd positions, and the number of 'b's at odd and even positions respectively. In the above example, we have 2'a's at odd positions and 3'a's at even positions, while we have 2'b's at odd positions and another 'b' at even position.

    When we append a new character to the end of the string, we can compute the number of palindromic substring which ends with the new character. For example, if the appended character is 'a', the number of odd palindromic substring which ends with the new character will be the number of 'a's at odd positions, and the number of even palindromic substring which ends with the new 'a' will be the number of 'a's at even positions. Hence, the new string aabaaabba will have 11 (8+3) even palindromic substring and 16 (13+2+1) odd palindromic substrings (don't forget to consider the new character as a substring of length 1). There are several cases to consider depending on the parity of the position for the new character, but it is not hard to code them out.

    Repeat the above steps, each time appending a new character to obtain the final results. Example solution here: 7227422

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

      I didn't notice that the substring between 2 'a' or 'b' is always a good string :( If I did, I would be violet now :(

      Anyway, thank you very much :D

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

too long, update rating

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

Juanmata, fortunately for you, someone got 258th place, however, no one got 123th place in a round prepared partially by praveen123

If you didn't understand what I am talking about, read this comment

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

Did anyone use Hightail for the contest ? How was the experience ?

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

Nice Round.. Got many fun reading and thinking about the problems.. Still getting fun analyzing the errors of mine... Thank you very much.. Enjoyed the contest.. Hope we will get many more like this..... :D

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

Gave very bad contest but still +11. So sad.:(

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

I got down rating !

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

Thank you for the contest :) Very interesting problems.

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

Unbelievable! TankEngineer solved all problems in less than half an hour!!! Congratulations)

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

Problem D was awesome. Loved it :)

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

Претесты в С плохие. В них перебираются все возможные мелкие варианты переменных, тем самым проверяя абсолютно всю логику решения. Всего 8 решений упало после пятого претеста — и все упали на 35 тесте на 6 строке, которая не чем особенным не отличается. Приготовив такие претесты проблемсеттер убил любую возможность взлома чужих решений. UPD: Без учета двух решений, упавших по превышению лимита времени (но моему тут надо быть кретином, чтобы догадаться написать ТЛьное решение). UPD2: Без учета начинающих программистов, которые вообще не смотрят на ограничение входных данных.

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

    Претесты и в самом деле были очень сильными (на Б-шке более 20 вроде). Хотя в прошлом раунде жаловались на слабые... Сообществу не угодишь :)

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

Hii,

In question B test case 26#

5

373362086 994096202 767275079 734424844 515504383

why "yes 2 5" is not an answer?by applying this, the sequence below is now a sorted sequence.

373362086 515504383 734424844 767275079 994096202

Please tell me if I am doing something really foolish.

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

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

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

Здравствуйте, объясните пожалуйста, если вас не затруднит. Я попытался сдать задачу C , но во втором тесте у меня выдает исключительно ответы yes. При этом в первом тесте такого нет, равно как и при исполнении на моем компьютере (правда, я перенаправляю потоки stdin и stdout с помощью freopen). С чем это может быть связано? Заранее спасибо за помощь!

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

    Ты перепутал "Вывод" и "Ответ". У тебя не выдаёт исключительно ответы "yes", они находится в правильном ответе, а у тебя как раз выдаёт "yes" и "no" и, очевидно, твоё решение написано неверно. Вот моё решение, которое, как мне кажется, выглядит достаточно понятным, в отличии от некоторых решений с миллионом условий: http://codeforces.me/contest/451/submission/7230148

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

      Ой, действительно перепутал — нубло же :) Спасибо большое, еще раз!

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

In the title, why the font of "258" is Times New Roman, but not Verdana as "Codeforces Round"? :P

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

hey... in Problem C, initial number of wins for a, b, and c are not coming to be integer values for some test cases like: -> 999999999980 258442058745 258442058715 258442058720.

Please correct me if I am wrong.