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

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

Всем привет!

Через несколько часов начнется Codeforces Round #164 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса.

Главным героем в задачах будет Манао, немало лет напрягавший умы грузинских участников. Добраться до страничек Codeforces ему помогли Gerald, помогавший мне в подготовке раунда, и Delinur, которая перевела условия на английский, за что им отдельное спасибо. Также задачи тестировали Seyaua, sdya и Aksenov239.

Распределение баллов по задачам немного нестандартное: 500-1000-1500-2500-2500.

Удачи :)

UPD: Соревнование завершено, поздравляем победителей:

  1. first_love

  2. dianbei_10

  3. yefllower

  4. dpij

  5. cenbo

Разбор задач можно найти здесь.

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

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

Have fun. I feel that it will be a good round

»
11 лет назад, # |
Rev. 3   Проголосовать: нравится -41 Проголосовать: не нравится
get(PlaceinRound);
while(TimeLeft > 0)
{
     SuccessfulHacks++;
     PlaceInRound--;
     ProblemsSolved += min(TimeLeft / 30,1);
}
ProblemsSolved = min(ProblemsSolved,5);
Cout<<"Good Luck!";
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Infinite while, place in round decrement with only one when winning 100(successfull hack)+nb_point_of_problem, Problems solved over 9000 before "ProblemsSolved = min(ProblemsSolved,5);" and "good luck" after the end of the contest... And yes, I am very fun at parties.

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

Hi , gojira First contest at codeforces written by you :) , Looking forward for it. Some day I believe I will also write a contest for codeforces :)

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

Who is eligible for round preparation?

»
11 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится
Round 164 'A' - 1  (Div 2)
164 == 
2 * 82 == 
2^1 * (1^2 + 9^2) == 
2^2 * (4^2 + 5^2)) == 
2^3 * (4.5^2 + 0.5^2) == 
2^4 * (2.5^2 + 2^2) ==
2^5 * (2.25^2 + 0.25^2) ==
2^6 * (1.25^2 + 1^2) ==
2^N * (a^2 + b^2)
1 < N < 60;  a,b = ?
»
11 лет назад, # |
  Проголосовать: нравится -23 Проголосовать: не нравится

when i became a red coder :(

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

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

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

    (a-b)^2 + (a+b)^2 = 2*(a^2 + b^2) => 2.5^2 + 3.5^2 = (6^2 + 1)/2 я это имел ввиду када писал убер задачу)

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

segodnia budet 164 raund rebita skora na4netsa u4astvuit 2322 vot tak vot

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

This is round 164 & 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 Here , 12+4+2=10+8=18 Again , 164 = 13^2 — 2^2 — 1^2 = 14^2 — 6^2 +2^2 Here , 13-2-1=14-6+2=10 What a combination :D

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

    As, 164 = 12^2 + 4^2 + 2^2 = 10^2 + 8^2 , the problem points could be distributed like this --> 3000,1000,500,2500,2000 , as 3000:1000:500:2500:2000 == 12:4:2:10:8

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

Один я обновлял страничку с участниками в надежде, что наберётся 3000 ? :)

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

Wow! So many participants!

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

pages of in queue. judges are down?

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

Больше 300 решений в очереди, это нормально?

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

My solution seems to be forgotten.

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

It's testing around 30 minutes

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

I hope I wasn't the only one who didn't know what expected value is :(

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

Как скоро разбор? особенно интересует задача D)))

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

    Выложу скоро после окончания.

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

      Спасибо за контест, жаль не добил задачу Д, интересен разбор, хотел решать графами, но не получилось)

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

В Д нужно было писать оптимизированный O(n*h^4) ?

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

    у меня O(n * h3)

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

    Ну там O(n*h^3) есть, а вообще я видел что O(n*h^4) заходят.

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

      У меня был nh^3*128. Это планировалось?

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

        Изначально планировалось только O(n*h^3) с маленькой константой, но так как на C++ O(n*h^3)-ные массивы свободно умещались в ML и TL, а на Java многомерные массивы тормозят и жрут много памяти, да и задача была не из простых, решили поднять ограничения. Хотя 128 конечно удивительно.

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

      То есть сохранять кто был последним? Тогда там будет 3 дополнительных. Писал волну, которая должна была это учесть, но к сожалению она работала 37 сек :(.

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

        Я хранил, сколько ступенек назад была ступенька в каждом из оставшихся направлений, и для направления последней ступеньки, валидное ли оно или по нему уже не забраться. Получалось [N][2][h+1][h+1][h+1].

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

    Можно было уменьшить количество состояний, если хранить высоты отсортированными.

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

В Алмате экстремальный контест, 6,3 балла а мы пишем cf

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

    Ага. Я допиливаю последние строчки С-шки, весь дом трясет(мы на втором этаже), люстра под потолком пляшет, на меня орут чтобы я на улицу выходил, а в ответ: "Ща С-шку сдам и приду!!!"

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

Combinatorics round with nice problems, I liked it! Thanks to the creators!

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

Спасибо за контест, особенно понравилась задача С :)

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

    Дело было как) Я сперва думал что мое решение правильное, нашел в комнате паренька у которого решение выдавало не то на макс тесте. Решил взломать и тут бац! Оказалось перебор с sqrt не совсем правильно и тут понеслись взломы :) P.S. Все ждал когда меня взломают. Спасибо авторам за контест

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

      Зачем нужен перебор с sqrt?

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

      Даже если 1 ≤ n, m ≤ 1000000

      Всё равно решение уложится.

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

      На самом деле, я не знал, какой тест подобрать для взлома :) На маленьких всё было вроде правильно, а большие вручную не проверишь. Решил выбрать самый большой, не ошибся :)

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

      Это был Я???

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

My solution was really forgotten(

It's still testing on the test1

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

Баг, скорее всего: когда идет систест, то процент(сколько завершено) не обновляется.

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

По поводу обновления статуса: добвляются какие-то древние посылки(6минута, когда уже показываются результаты 40-й)

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

    Я заметил такое: нажимаю отправить, появляется страничка со статусом, решение идет где-то в тестах 6-7, затем опять показывает первый и по порядку.

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

ДА! ДА! ДА! У меня на Д зашло ТАКОЕ решение! 3029636 :)))

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

Спасибо, контест был довольно-таки интересным, несмотря на то, что задачи были скорее A-A-A-E-E. Кстати, кто как ломал C? У меня +3 тестом «6 6».

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

    тоже самое, тоже +3 :)

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

    аналогично) я еще одного по Б сломал на тесте 2000, у него было переполнение:D

    int t; cin >> t; cout << (t * t * t + 5 * t)/6;

    а формула довольно-таки интересная)

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

    +5 тем же тестом

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

Can anybody help me in understanding the reason behind using comparision function ??

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

    The change in expected total length from swapping the order of adjacent tracks [i] and [i-1] is equal to

      track[i  ].length*track[i  ].chance*(1-track[i-1].chance)
    - track[i-1].length*track[i-1].chance*(1-track[i  ].chance)
    

    since [i] might now be repeated due to [i-1], but [i] can no longer cause [i-1] to be replayed. Swapping has an effect on the expected playtime of these two tracks alone, so it's always best to swap pairs for which such a change is positive.

    You could intuit that continuing to make such swaps would look a lot like bubble-sort (or rather, is bubble-sort); more rigorously, use some simple algebra to show that the expression above is consistent as a comparator.

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

      and how do we calculate the expected total length?

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

        A song will be replayed every time it is liked but a later song is disliked, plus the once the first time it is seen. We take the chance of being liked multiplied by expected number of later dislikes and add one:

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

I am new to codeforces , can anyone tell by when my rating willbe update :) ?

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

nice problems, enjoyed the contest

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

Hi gojira,

I really enjoyed the problems, thanks for the contest. I saw a lot of hacks for 3rd problem, that's good, thanks again ;-)

B.

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

Love win =) standings(смотреть среди официальных участников)

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

9 successful hacks in problem 164C - Автоматное программирование :D it was really funny :D

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

9 successful hacks in problem C :D it was really funny :D

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

whew,that was really lucky for me,first time contest writer from my country first time div 1 ^_^

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

В задаче B зашло решение в 1 строчку(если не считать ввод и вывод): s:=n*(sqr(n)+5)/6;

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

Could not understand Problem B — Buttons. Can anyone explain it? words "push" and "press" are same? "some" does it mean single button or can be group of buttons?

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

    Yes the words "push" and "press" mean the same. You can only push one button at a time and you need to output the maximum value of the number of times you can push the button, before getting the right permutation.

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

My submission with id 3029515 got wrong answer on first test case. But its giving the correct answer in my system

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

    How is that possible?

    http://codeforces.com/contest/268/submission/3029515

    It really returns 2 on your system?

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

      It returns 3 on my system which is the correct answer. On the judge it returns 2. It is pretty weird.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        return pow(sqrt(ds),2)==ds;
        

        Are you sure? This line doesn't really do anything except check for floating-point error...

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

        On my PC it works too, but on ideone it does NOT — http://ideone.com/ooqeop

        In debug mode there is different output:

        ideone:

        a=(0, 1)
        b=(0, 2)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(1, 0)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(1, 1)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(1, 2)
        (pow(sqrt(ds),2)==ds)=1
        a=(1, 0)
        b=(1, 2)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 0)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 1)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 2)
        (pow(sqrt(ds),2)==ds)=1
        2
        0 1
        1 0
        

        my PC:

        n=2, m=2
        a=(0, 1)
        b=(0, 2)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(1, 0)
        (pow(sqrt(ds),2)==ds)=0
        a=(0, 1)
        b=(1, 1)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(1, 2)
        (pow(sqrt(ds),2)==ds)=0
        a=(1, 0)
        b=(1, 2)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 0)
        (pow(sqrt(ds),2)==ds)=0
        a=(1, 0)
        b=(2, 0)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 1)
        (pow(sqrt(ds),2)==ds)=1
        a=(0, 1)
        b=(2, 2)
        (pow(sqrt(ds),2)==ds)=0
        a=(1, 0)
        b=(2, 2)
        (pow(sqrt(ds),2)==ds)=0
        3
        0 1
        1 0
        2 2
        
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    In 268A, I submit 3 times and get WA on test 6, which have the right answer is 6, but the system returns 83. Anyone can explain that for me ?

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

Поздравляю всех с новым рейтингом(пусть даже нехорошим)! Самое главное в соревнованиях такого типа я думаю "Опыт", а опыт всегда повышается! Поздравляю! =)

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

please can someone tell the way to solve problem C...

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

Спасибо за раунд! Интересные задачи и понятный разбор:) Было бы интересно порешать Ваш див1-раунд.