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

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

Доброго времени суток, сообщество Codeforces!

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

Раунд начнется 8 декабря в 13:00 MSK

Задачи были подготовлены сотрудниками и студентами Саратовского государственного университета, включая MikeMirzayanov, Fefer_Ivan, NALP, HolkinPV и меня.

Разбалловка стандартная: 500-1000-1500-2000-2500.

UPD: Поздравляем победителей:

  1. asalwaysdontbeahero
  2. VKRNVO5
  3. chnluyi
  4. pkwv
  5. Xe4NIK

UPD: Разбор задач.

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

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

Наконец-то анонс! Всем удачи!

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

What will be the scoring? Edit: Scoring added

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

I hate contests in unusual time (Do U know what is time?!)

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

I am coming

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

Forgot to register for the contest T_T. Realized when tried to submit :(

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

Found someone who wrote the following code

int arr[100];
for ( i = 1; i <= n; i++ ) scanf ( "%d", &arr[i] ); //Here n can be 100.

Tried to hack it with a test case where n is 100 ( My first attempt to hack a code in my life ) but failed. Is there any full proof way to make the code go out of bounds?

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

what a greedy contest! :D

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

What is the logic behind Problem D?

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

Oops, my solution for Problem C & D both got WA6 unfortunately. Orz.

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

Как решать Dшку?

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

    Почти наивно. Хранить сет всех неполных сосудов, которые еще не заполнены, и массив для поточного количества воды в сосудах. Если поступает первый запрос, найти lower-bound'ом по индексу первый неполный сосуд, и лить воду, пока можно, удаляя на ходу из сета все заполнившиеся сосуды и обновляя массив поточных количеств. А на второй запрос просто взять поточное количество воды в нужном сосуде из массива.

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

      А я решал через СНМ. Хранил ссылку next, и если сосуд становился полным менял ссылку на ближайший неполный сосуд

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

        Чтобы переходы между сосудами после заполнения работали за О(1), а не за логарифм — можно хранить незаполненные сосуды в виде двусвязного списка.

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

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

what was the idea for E?

Was this to sort the input and work with k consecutive parts ??

I tried this and got WA on pretest 2.

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

Nice contest with really fast system testing :D

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

Can someone help me with B?

My approach was: 1. Factorize a in powers of 2,3,5. 2. Factorize b in powers of 2,3,5.

Answer will be sum of differences of power. To find power, I found all powers of 2,3,5 uptil 10^5, for fast calculation. Yet, for test case -> 1,000,000,000 999,999,999 — it was taking more than 2-3 seconds.

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

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

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

После системного тестирования поднялся на 70 мест. Круто!

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

Как B решается

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

    Очевидно, что наибольшее число, которое может получить лисица — НОД(a,b). Считаем его алгоритмом Евклида. После чего выделяем числа c и d — a/gcd(a,b) и b/gcd(a,b) соответственно. Пытаемся факторизовать их двойками, тройками и пятёрками. Если мы сделали это успешно, то пишем сумму двоек, троек и пятёрок в разложении первого и второго числа, иначе -1.

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

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

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

Как решалась Е?

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

    Сортируем по координате, потом считаем все суммы расстояний на отрезках длиной k станций, выводим те, которые составляют минимальную сумму.

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

     Sent   Hacked   Accepted 
 A | 1235 | 15     | 1020     |
 B | 1132 | 36     | 662      |
 C | 716  | 9      | 285      |
 D | 329  | 0      | 150      |
 E | 95   | 2      | 18       |
Participants count: 1342

More info

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

Почему нельзя смотреть решения сразу после того, как закончился раунд? Раньше было можно. А теперь уже и систесты кончились, и все равно смотреть нельзя. Fix it please

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

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

    Вероятно, сегодня причина та же.

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

Контест просто КЛАСС...!!! Спасибо Авторам...!!!

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

wonder why my submission 5386072 (using recursion) gave MLE. my guess is that stack size of the judge is pretty low, because i used the exact same idea in practice submission 5388703 and got AC.

EDIT: i think the solutions and tests have not yet been made public, so u may need to wait for a few minutes to see them.

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

When I try to see someone's solution here http://codeforces.me/contest/371/standings nothing happens. A pop up is there when I double click on the cell. But the submission link to show the user's actual code doesn't work for me. Any help?

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

В задаче С делал бин. поиск по ответу. На контесте сделал правую границу 10^16 на фул тестах получил WA16, в дорешке сократил до 10^15 все зашло) Видимо случалось переполнение long long. Было бы обидно потерять задачу на такой ошибке, если этот раунд был бы рейтингованным для меня)

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

Отличные задачи. Особенно D понравилась. Спасибо за контест.

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

I have a question about Problem B! In the first sample, how to get the output result 3 ????? I always think the result should be 2. That is, first, 20/2=10, then, 15*2/3=10, and over.

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

Can anyone help figure out why my D is wrong at Test 6 Ans 34th ?? Thx.

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

Is there anyone love to share thoughts on problem E?

My implementation was sort station ids by their location. Then I guess the solution must be k consecutive stations. Then I scan from left to right. I got WA on 15.

Is my algorithm totally wrong or I missed something in my code? Thanks.

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

А разбор задач будет?

UPD: Круто, разбор задач появился через пару часов, после этого поста, а меня минусуют...

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

Worst time ever :( Please move the hour or maybe the day xD