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

Автор ZhNV, история, 8 лет назад, По-русски

Привет, Codeforces!

6 октября 2015 года в 19:30 MSK состоится очередной раунд Codeforces #324 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса.

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

Участникам будет предложено пять задач и два часа на их решение. Разбалловка будет объявлена позднее.

Все герои задач имеют своих прототипов — моих друзей, знакомых, родных, которым и посвящается этот раунд.

Желаю удачи и высокого рейтинга!

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

UPD2 Раунд завершен, всем спасибо за участие!

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

1). Siunaus

2). aasddf

3). M_H_M

4). lal

5). femsub

Разбор

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

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

Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).

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

Hope it will be a great Round :-) Happy coding :-)

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

Hope it's another interesting round. Good luck to all :)

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

I think clear problems with no story are better because there are many coders at codeforces that their main language is not english or Russian

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

    Totally agree. For me it is quite difficult to read and understand the storylines in English. Sometimes I even look up a dictionary for words that I don't know.

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

      It's a part of problem! You must have good English skills to understand storyline clearly. I think English tasks for Russian users will be more fair.

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

    :D

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

Best wishes to ACM ICPC — 2015 regional/sub-regional participants for their upcoming regional/sub-regional contest and congrats to those who already manage to qualify for ACM-ICPC World Finals 2016 — Phuket :)

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

"The scoring distribution will be announced later."
So mainstream ;)

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

Все герои задач имеют своих прототипов — моих друзей, знакомых, родных, которым и посвящается этот раунд.

Как скучно...

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

Меньше, чем раньше . . . :)

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

So much grey。。

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

Lots of down votes here :D :v

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

Заметили? Минусуют одних серых-зеленых-синих, явно же по цвету!

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

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

Желать удачи всем — бессмысленно. Но пусть тебя, дорогой читатель этого поста, посетят вдохновение, пусть твои пальцы порхают над клавиатурой, как синицы в небе; пусть код получается с первой компиляции правильным, пусть идеи решений задач мгновенно настигают и каждый нюанс каждой задачи пусть сразу оседает в твоей голове, не только защищая от хитрых тестов, но и подготавливая персонально для тебя целый ящик со взломами. Удачи тебе, дорогой читатель, и хорошего настроения!

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

    В первый раз — приятно, Спасибо, хз)

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

    Сам написал? Если да, то круто.

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

      Мой друг. Конечно, сам.
      Ну сам подумай, кто посмеет,
      Вопреки вышестоящим минусам,
      Писать о том, что смысла не имеет?

      Ну сам подумай, кто еще
      Будет писать о неизвестном чуде,
      Когда у всех вдруг загорится голова,
      И все задачи все сдадут за полчаса?

      Такого ведь, как автор сознает, не будет никогда.
      А, если и случится чудо спорадически,
      То у координатора поседеет голова.
      (за ритм извиняюсь — нет похожих слов, короче синтаксически)

      Так что, прости, но все, что я писал,
      Оно случится только на бумаге. Но главное я сделал: плюсиков набрал
      А, может, и настроение поднял?..

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

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

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

Gayle Laakmann live session or this contest :D

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

спасибо

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

Пресвятая шоколадница, тут просто кладбище комментариев!

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

All participants good luck.

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

Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).

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

The scoring distribution will be announced later later later late lat la l..........

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

where is scoring distribution ??

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).

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

Ответ по модулю в Div 2 B, серьезно?

(Для справки: люди, не знакомые с олимпиадами, или только начинающие знакомиться, не знают, как это делать. В лучшем случае они используют Python / Java / C# с их BigInteger-ами, а если они пишут на другом языке — не сдают задачу. Проверено на локальных контестах в университете)

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

    Зато все кто не знал как считать ответ по модулю — узнали. Что в этом плохого? По-моему наоборот здорово.

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

      В том, что они потратили на это 1 час и 50 минут контеста. Не надо так издеваться. В одном из прошлых раундов вот дали два указателя, это еще хуже было. Тебе было бы приятно подолбаться в эту задачу, если бы ты был совсем еще новичком? На A, B div 2 любые алгоритмы и олимпиадные приемы противопоказаны.

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

        Чтож тогда по твоей логике в div 2 A нельзя задачу на цикл давать? Чтобы совсем новые участники не "долбились" в нее? Как развиваться вообще тогда?

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

          Цикл — это конструкция языка программирования. Так что его давать можно. А два указателя, вывод ответа по модулю, динамика, можно много чего еще назвать — это олимпиадные приемы. Если давать это в ранних задачах Div 2, куча народу будет сидеть без дела, а после контеста еще подумает, а принимать ли участие в следующем раунде.

          Мне кажется, развиваться на начальных этапах правильно с помощью архива задач и тренера/друзей/статей, которые расскажут что-то новое. Но не во время контеста! Ну дали тебе задачу с двумя указателями, ну написал ты два вложенных for-а, многому научился? Многим интереснее писать раунды, ведь это PvP и в общем случае весело, однако такие задачи, как сегодняшняя B, отбивают желание участвовать в олимпиадах. Поэтому надо делать задачи как можно более лояльными к новичкам.

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

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

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

              Ну ок. У тебя просто ферлоновские взгляды в этом вопросе, у меня нет) А плюсуют пока обоих.

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

                Вот что точно нужно было сделать, так это дать ещё один тестовый пример с переполнением. Это было бы более лояльно.

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

                Ничего себе, уже не плюсуют. Но у меня рейтинг выше! Huyum_nik, твоя теория терпит крах!

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

    В этой задаче можно было заставить возводить в степень за логарифм, но автор оказался гуманным :)
    Не вижу ничего сложного для "зеленого" и выше в вычислении остатка.

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

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

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

        Вообще-то теория сравнений ещё в советской школе изучалась на факультативе в 7 классе.

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

    Лично мне тоже не очень нравится эта задача на позицию Б див2. По крайней мере потому, что это не просто возвести что-то в степень, но еще нужно вычесть одно слагаемое из другого. Даже не очень большие ограничения не делают задачу лучше.

    По-моему на позицию Б див2 лучше подойдет реализация на 2 цикла, возможно с каким нибудь крайним случаем.

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

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

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

At D I output

3 2 2 23 and I have wrong answer on pretest 1, where n = 27. Why?

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

at problem d i output 3

2 2 23 i have wrong answer on pretest 1 , which has n=27 why? LE : my bad, sorry

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

z

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

B — What's wrong with the solution 3^(3n) - 7^n ?

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

Все заметели, что в топе стало меньше нерейтинговых))

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

Problem 2: Just 3^(3*n)-7^n ;))

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

dafuq is C pretest 9?

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

How to solve problem E ?

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

    Greedily. Problem: sort the permutation with minimum cost. Let's assume that we already sorted first i elements(0-based). Let's p[j] = i. Then we need to find maximum ind such that i ≤ ind < j and j ≤ p[ind], it can be easily done by segment tree. Then swap elements at index ind and j. For each index i you will make O(n) swaps. Complexity O(n2logn)

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

      Are you certain this works? I submitted this and got stuck on pretest 14, and looking at your profile you didn't pass the pretests either (getting stuck much earlier than me).

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

        I wanted to write the same but was sure that it doesn't work;)

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

        Yes, that works. I didn't passed because I had wrong idea. I looked for maximum ind such that i ≤ ind < j and p[ind] > ind. This idea doesn't work for test: 4 4 3 2 1 1 2 3 4

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

    The minimum cost is achieved using any strategy that never moves any element further from its final location, since |i - j| is just the distance by which each element is moved (·0.5).

    One way to solve this would be putting all elements that need to be moved to the right in one set, those which need to be moved to the left in another set and always swapping the first element of the latter set with the last smaller element of the former.

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

How to solve D?

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

    If n is prime we print 1 n
    If n — 2 is prime we print 2 2 n — 2
    If n — 4 is prime we print 3 2 2 n — 4
    Else n = p1 + p2 + p3. We find closest prime number to n (p1). And we've got n — k = p2 + p3.
    n — k ~ log(N) (Don't remember why, shame on me). And just by brute force find p2 and p3.

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

      Seriously, without knowing this conjecture, can anybody solve problem D? This kind of problem just piss me off!!!

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

        I solved D without this knowledge:D

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

          Then you (maybe without realizing) assumed that there is always valid p2 and p3 whose sum equals to n — p1. Problem guarantees there is a solution. It doesn't guarantee there is a valid (p2, p3) pair; that's why, you need to know Goldbach's conjecture.

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

            Yeah, you're right... This was just guess.

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

            You don't need to know it since the problem is simple enough to brute force. First check if n is prime, if so print. Else find largest prime smaller than n, now check if you can find one or two primes adding up to this (goes very fast since prime density is quite high), if so print. Else iterate.

            You know from the problem description that there is a solution, and you know that finding multiple fitting large primes is too slow so the only way left is to just find large primes and then see if you can find one or two smaller primes adding up to the result.

            This way you can solve for odd n as well since it is so easy to find a solution.

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

    I can't solve it during the contest due to a small mistake. But i did it right after the ending of the contest :/

    If n = 3, output 1 3 if n = 5 output 2 2 3 else

    since n is odd, n — 3 is even, and then we can use strong goldbach conjecture to solve the problem. Every number N even, greater than 2, can be written as sum of two primes. Since n — 3 is even, we can find this two primes that added form n — 3 and then add it to 3, which is prime. output

    3 3 prime[i] (N — 3 — prime[i])

    I used Sieve of Eratosthenes to find primes between 2 and 10^7, and if some number K didn't fit in this interval, I test it's primality by brute force. And used binary search to try to find N — 3 — prime[i] in vector of primes;

    http://codeforces.com/contest/584/submission/13459478

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

Problem A and Problem B is a joke in Python

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

What is The Solution Of div2 E? I tried to find symmetric group, but it seems hard to calculate the minimum step to sort the permutation

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

How to slove D? Damn I spend all contest to it

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

      Still not sure how to do it.

      It is basically coding Goldbach's weak conjecture, right?

      3, and express n-3 as sum of two primes. Do you just brute force it? What about the time complexity?

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

        No.4 cannot be expressed by your logic

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

        Then we are assuming that '3' is definitely in the answer. Can you prove it?

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

          That is Goldbach's weak conjecture and it has been verified for numbers larger than the input in the question.

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

            In fact, Goldbach's weak conjecture has been mathematically proven to be valid in general.

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

        So handle small numbers manually for simplicity. (Since n is odd, n-3 is even, and you can brute for 2 remaining 2 primes numbers(other than 3) summing upto n). Handle cases of n=3, etc manually.

        For larger n, always try and express it as sum of exactly 3 primes. Find a prime number g below n and close to it.This is one of your 3 primes. Since prime numbers are not too far apart, n-g is now a small even number(my bound was 50000) and you can brute for how to express it as 2 primes.

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

          Thanks. Your gap was 50,000? According to wiki, a gap of 300 would suffice.

          https://en.wikipedia.org/wiki/Prime_gap

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

          There's no need of different method for larger numbers. You can always brute force to express n-3 as sum of two primes. My solution passed with this method. I think the reason for this is that even when n is around 10^9, there is a very high probability of finding a small prime p(upto which you can iterate in time) such that n-3-p is also prime.

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

            Yes, I realized my solution during the contest failed only because my brain missed the "at most 3" condition. I ended up missing primes below 7 (3 and 5) — I thought they wouldn't be in the input since solution was guaranteed... Unfortunate error.

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

BTW, check this problem: http://acm.timus.ru/problem.aspx?space=1&num=1356. It's almost the same as the problem D, just a bit harder (but the solution for 1356 works here in problem D).

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

C pretest 9 ahhhr.

C looks straightforward but did not work out.

My thought.

  1. Count the number of distinct chars in s1 and s2 and tag appropriately.
  2. We can sort based on frequency.
  3. Pick first n1-t and n2-t
  4. Try to find t chars in Universal set but not in union of s1 and s2.
»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

System rating finished

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

Hello! I have a question at the second problem, Div 2. During the contest I printed(put(3,3*n)-put(7,n))%m; and i have got wrong answer on test 7. Now I am printing (put(3,3*n)-put(7,n)+m)%m; and I have got accepted. Why the second method works? Thanks!

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

    put(3,3*n)-put(7,n) may be negative number. So first method would be incorrect (returns m minus right answer).

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

      but why should i add m? m is 10^9 + 7. i don't understant..

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

        put(3,3*n)-put(7,n) = Km + ans
        may be less than zero. 0<=put(3, 3*n)<m ans 0<=put(7,n)<m. So -m<put(3,3*n)-put(7,n)<m

        put(3,3*n)-put(7,n) + m guarantee positive. So mod operation would be correct.

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

For D, I just generated primes upto 10^6 and tried to find the answer with simple check. And it passes. Why does it pass?

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

    Because primes are distributed pretty randomly with log(n) distance between them in average. So, there is no such number N that for all small prime numbers M up to 10^6, N — M is not prime.

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

Очень радует, что в сегодняшнем раунде в Топ-40 находятся только пять "нерейтинговых восходящих звезд".
Цветовая революция пошла на пользу :)

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

    Возможно, многие из них — фейки красных. Те самые, что когда-то давно за один контест стали фиолетовыми.

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

I don't understand.Why 2000 points for problem D??? :o :o :o It was far far easier than B and C.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
swap(C, D);
»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why this submission get WA?

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

how to solve C ?

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

just added the condition of a+b+c=n and D passed :( :( :( :(

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

Автокомментарий: текст был обновлен пользователем ZhNV (предыдущая версия, новая версия, сравнить).

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).

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

i forget to say :thanks for no delay

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

Some help on E? I can find the minimum cost but I cannot restore the swaps. I thought about going from left to right and if we see an element which is not on its place (it must go to the right) then let's say his position is i and it must go to position j. Let's first handle all elements that are greater than Ai in the interval [i+1,j] and then somehow solve for the current element. Can you please give me a hint?

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

    can E be solved using greedy method ?

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

      Well, the first part (minimum cost) can be called greedy, I guess. The idea is to find for each number its position in B. Then if we want A to become B, that means that some elements will go to the left and some to the right. We can make the observation that we need to consider only those elements which go to the right. Let's assume that after considering them, there is an element that must go to the left (if there is more than one, consider the leftmost). Moving it to the left means moving one element to the right. A contradiction! So if pos[k] is the position of the element with value k in B, we add to the answer max(pos[Ai]-i,0) for each i.

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

      My solution is actually greedy. What I do is in each step I have a vector that keeps all the numbers that have to go to the right (I iterate the numbers from left to right) and whenever I find a number that has to go to the left I just swap them and move the index of my iteration back so I can start from the number I moved.

      Before that I change the permutations so the second permutation is 1 2 3 ... N and the first one changes so it's the same problem but having to move a permutation to the sorted permutation.

      Let's see an example:

      4 4 3 1 2 1 2 4 3

      The problem is the same as solving

      4 3 4 1 2 1 2 3 4

      Now I start with 3, it has to go to the right so my vector is (3), then 4 has to go to the right so my vector is (3,4), then 1 has to go to the left so I swap 1 and 4 now it's

      3 1 4 2

      And my iterator moves back to where the 1 is, now 1 still has to go to the right so I swap 1 with 3 that is the top of my vector (or stack if you want to see it like a stack). Now it's

      1 3 4 2

      Then I continue iterating, 1 has to stay where it is and the vector is empty, then 3 has to go to the right, 4 has to go to the right too, and 2 has to go to the left, and when I analyze 2 my vector is (3,4) so I move 2 to the left and it's

      1 3 2 4

      And in the last step I change 3 with 2 so it's

      1 2 3 4

      And it finishes the process. This is a greedy approach and it's similar to selection sort I think.

      I start with 4 (it

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

    You can maintain an ordered set (balanced binary search tree) of all elements that need to go to the left (call this set L), and all that need to go to the right of the permutation (call this set R).

    In each iteration you perform one swap, that involves swapping the leftmost element in L with its closest element in R to the left (it clearly has to exist). If you store both the elements and their positions, you can efficiently maintain this structure as you go along in logarithmic complexity.

    You may refer to my code: http://codeforces.com/contest/584/submission/13456405

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

      You don't need such complicated structures as O(N^2) is ok for this problem.

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

        The complexity of my solution is actually something along the lines of O(N^2 log N) in the worst case (something like 5 6 7 8 1 2 3 4) anyway. I try to follow the approach which is easiest for me to comprehend on a high level. If it requires complicated structures, so be it (especially if they're already part of the STL). :)

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

    Consider the element that needs to go to the rightmost location. Lets say that element is in the ith position and needs to go to the nth position. Then, surely there must be an element from positions i+1 to n which needs to go to a position j where j <= i. If no such element exists, then there are (n-i) elements which final location is from (i+1) to (n-1), a contradiction! Find the leftmost element which matches this criteria using a pointer sweep and then swap it with position i then keep repeating until it is moved to its correct location. This is an O(n^2) algorithm.

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

Problem E : For the first time on codeforces, a solution didn't pass for me with cin,cout. My solution failed system tests after passing the pretests. And when I changed it to printf,scanf it passed. I think the problem setters should be careful the next time, as when crtical points and rating gets affected due to such reasons, it feels sad.

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

    Why are you blaming the problem setters for this? It was your fault!

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

      What should be tested is our knowledge, not whether we use fast i/o. And in fact such things have never happened on Codeforces before. Also when you get a problem wrong because of such reasons, it doesnt feel good. I'm not blaming them, but I feel if someone loses out on points for a hard problem, because they didnt use fast i/o, that is just not fair.

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

        If problemsetter increase time limit in order cin/cout submition past, it can cause that slow solutions will past with scanf/printf! Cin/cout speed is well-known fact, be careful, when you use it

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

    Do you use

    ios_base::sync_with_stdio(false);

    ?

    That line can save you from time limits if you use cin/cout

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

    You can add these lines to speed up cin/cout.

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

It is time to midnight,but still waiting for Rating.

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

MikeMirzayanov. When you declare a rating?

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

Happy New Year CF!!! wait(wow), rating still not updated?

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

Wow, my rating is changed to +0 :)

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

What is this?

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

Auto comment: topic has been updated by ZhNV (previous revision, new revision, compare).