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

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

Привет, Codeforces!

31 января в 15:00 MSK состоится раунд #289 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

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

Данные отличия в правилах вызваны тем, что этот раунд является вторым отборочным раундом в ЗКШ. Официальный сайт школы — http://it-edu.mipt.ru/zksh2015. Там же вы можете найти правила отбора на ЗКШ.

Алгоритм действий для школьника, желающего поучаствовать в отборе на ЗКШ (вне зависимости от дивизиона):

  1. Зарегистрироваться на школу по ссылке http://goo.gl/kz2qSf, если это не было сделано ранее.
  2. Зарегистрироваться на сайте codeforces.ru, если это не было сделано ранее.
  3. Зарегистрироваться на раунд по ссылке http://codeforces.me/contestRegistration/509. При регистрации требуется поставить галочку в поле "Хотите ли вы участвовать в отборе на ЗКШ?", а также указать фамилию, имя, отчество и email, которые вы указали при регистрации на школу в пункте №1.

По всем возникающим вопросам пишите на адрес оргкомитета: [email protected].

В заключение, наш коллектив авторов (тех. комитет ЗКШ) выражает свою благодарность Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский, Михаилу Мирзаянову (MikeMirzayanov) за вклад в развитие программирования путем создания систем Codeforces и Polygon.

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

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

I have 2 question :

1)Are there any T-shirts ?

2)rated?

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

You can use this picture :)

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

Сколько будет задач и почему только div 2?

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

    Участники из первого дивизиона могут участвовать в соревновании вне конкурса. В частности, школьники из 1 дивизиона могут участвовать в CF #289 вне конкурса, то есть для них раунд будет нерейтинговым, но их результаты будут учитываться при отборе на ЗКШ наравне с див.2 участниками.

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

      Сколько будет задач?

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

        Возможно, в этом вся интрига. Хотя если учесть, что правила ACM (не будет взломов), что участвует только 2 дивизион (не будет особо сложных задач), много времени даётся — будет задач 8 примерно такого уровня: А, Б, Б, С, С, Д, Д, Е.

        Давать меньшее количество задач большей сложности я не вижу смысла, потому что особо сложное второй дивизион всё равно не решит и не важно сколько времени будет дано, а вот чтобы реально занять большую часть второго дивизиона на все 3 часа без взломов — такой набор подойдёт.

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

Can Div1 contestant participate in the selection to WCC?

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

The sign-up is in Russian. Is the WCC available only for Russian speaking students?

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

I want to know how many questions are there?

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

Открываю топик, смотрю на время. Думаю: "обидно, пересекается с отборочным ЗКШ". Смотрю на название...

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

т.е. отбор будет проходить не в едадже а на Codeforces?

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

А я на сайте почему-то не вижу информации о том, что второй отборочный будет проходить здесь.

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

Забыл отметить галочку при регистрации, это можно исправить? :(

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

I think 5000 users register for contest :)

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

During the contest I can realize that I am in Computer AGE.

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

А можно ли как-то пометить тех, кто участвует в раунде как в отборочном? Во первых, во время раунда это покажет примерную картину того, что происходит на отборе(хотя там можно и что-нибудь другое придумать) А во вторых, я постоянно сомневаюсь, поставил ли я галочку. И если я перерегаюсь, и поставлю галочку заново, то снова начну потом сомневаться. А эта возможность развеет мои сомнения навсегда!

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

Will the problems be arranged according to the expected order of difficulty? Also will there be a scoring system or we'll be rewarded on problem count and submission times with 20 mins penalty for wrong submissions?

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

    "we'll be rewarded on problem count and submission times with 20 mins penalty for wrong submissions" is correct. I can't promise anything about tasks.

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

I hope that these rules used in all contests on codeforces ..

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

А регистрация, закрывающася за пять минут до начала, — это по привычке так сделано? Вроде на CF обычно в раундах с полными тестами (где не будет взломов и не нужны комнаты) оставляют регистрацию до конца соревнования.

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

Standard input/output?

How many tasks?

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

Hacks or no hacks?

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

is this rated?

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

Can I participate in this contest without signing up/registering for WCC?

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

What time during the contest will the scoreboard be frozen?

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

Hope to become expert this round))

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

你好

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

By using ACM ICPC rules, does it imply that the language restricted (only C, C++, Java)? I hope it does not.

UPD: my bad. I just opened the rules. We can also use Pascal and Python.

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

let the game begin.. Good luck for all

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

It's 15 minutes past the contest .. and I can not submit my code for A :/

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

Nice System Of A Down reference in Problem E :)

(IEAIAIO and BYOB are both songs by System Of A Down)

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

And dreamoon_love_AA finally has done it! Congrats!

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

Nice problem :)

thanks map

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

Sorry to say this but, imo(i dont know about others) your problemset was the worst i've seen in codeforces.

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

what is the 7th test case in problem C?

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

Мне кажется, последняя задача была бы интереснее, если надо было бы посчитать количество графов, а не деревьев.

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

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

    А я под конец так отчаялся, что удалил часть кода в решении по С и заслал, что привело к прорыву с WA6 до TL21.

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

Как можно посмотреть результаты тех, кто писал отбор в ЗКШ?

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

How do you solve E ? I feel it is dp but not sure how.

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

    you can have a look at my solution .. i did it so simple you even can't believe .

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

    Let call ai = 1 if si is a vowel else ai = 0.

    sumi = a1 + a2 + ... + ai

    Number of vowels in all sub-strings with length x is:

    Pi = (sumxsum0) + (sumx + 1sum1) + ...

    = (sumx + ... + sumn) — (sum0 + ... + sumn - x)

    The result is sum of Pi / i

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

    there can be something like this http://pastebin.com/E2pCyWmu

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

    I didn't solve it either but I think it's dp too. We look at each letter independently and if it's vowel we add to answer sum of some harmonic serieses (we can calculate it using this value for last letter and array of prefix sums of harmonic series)

    UPD: now I see that I was wrong and it can be solved easier another way.

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

    Consider the vowel in the string at the position i. It contributes to the answer only addends of the form , where k ≥ i and j ≤ i, because it is only contained in the substrings of the form si..j, j ≤ i ≤ k. After what, we can sum this expression for all i, j, k such that si is a vowel and j ≤ i ≤ k. Plugging this into WolframAlpha, we can get the final formula for the answer: , where Hi = 1 + 1 / 2 + ... + 1 / i is the i-th harmonic number.

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

When will we be able to look at others' solutions?

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

How to solve problem C? I saw a lot of accept is this problem, but I didn't know how to do it.

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

    At the each step remember a last output value and a sum of digits in it. Then add 1 to last value and try to get the smallest integer which has the desirable sum of digits. To do it basically set less significant digits to 9 if you need to make sum of digits larger or set them to 0 (and +1 to digits before them) if you need to make it lesser.

    Use bignum arithmetic.

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

Hi, when will the practice problemset become unlocked?

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

how CF knew that i have learnt Russian? :P there was also no option to copy the line to paste in google translator.

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

    I have seen two messages (English and Russian). Intelligence is not sleeping. Check your profile setting, maybe.)

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

Any idea about how to solve prob. E ?

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

I really wrote bad and long solution for C but finally I got accepted :D

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

Ладно, how to solve problem F ?

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

    Динамика dp[l][r] -- сколько существует деревьев, таких, что корень в вершине с номером l и при dfs-е из условия получается последовательность b[l], ..., b[r].

    Тогда дерево имеет вид l, (дерево с корнем в l + 1, состоящее из вершин l + 1, ..., r1), (дерево с корнем в r1 + 1 из вершин r1 + 1, ..., r2), ..., (дерево с корнем в rk + 1 из вершин rk + 1, ..., r), причём ri < ri + 1.

    Это можно посчитать ещё одной динамикой dp2[l + 1][r] -- сколько способов разбить отрезок на деревья указанным способом.

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

When clicking on submit button on the right, I sometimes had to wait around 3-5 minutes before my solution got accepted since previous 3 contests. :(

All other websites were working in a decent speed on my internet connection during the time of the contest.

Has somebody else faced this lag, or I do I need to get an alternate connection.

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

    same here site page for submit will not open..

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

    It is always laggy for me too while I am in college but works fine when I am at home . You could go to IPC or library for faster speed.

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

Ну когда уже будут результаты отбора?

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

map, when the editorial would be available ?

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

http://codeforces.me/contest/509/submission/9645857 Why am i getting Wrong Answer on test 1, output is correct on my pc.

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

    But in the system and ideone, your program gives "NO" as the output of the first test case, while the answer should be "YES"

  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
     FOR(K, 0, 102) {
       if(abs(c1[K]- c2[K]) > 1) {
         f = false;
         break;
       }
    }
    

    but your array sizes are 102 and your for loop define is <=.

    Don't try to use defines if you are not familiar with them.

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

Nice contest. Me mostly enjoyed problem C, stringy one.

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

problem C what the output for : 10 1 1 1 1 1 1 1 1 1 1 ???