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

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

Завтра, 31-го августа, за 4 с половиной часа до конца лета (по Москве) будет проходить Codeforces Round #136. Автором этого контеста буду я, это уже мой 6-й контест на CF.

Помогает строить раунд мне Геральд Агапов (Gerald), задачи переведет, как я предполагаю, Мария Белова (Delinur). Спасибо всем.

Надеюсь, вам понравится раунд. Разбалловка стандартная.

Спасибо за участие. К сожалению, большинство моих контестов не пользуются особым интересом, судя по системе "Вклад", но надеюсь все-таки нашлись те, кому он понравился :)

В первом дивизионе ровно 7 участников решили все задачи, они и попадут на главную:

  1. peter50216
  2. yeputons
  3. winger
  4. rng_58
  5. RAD
  6. al13n
  7. KADR

В то время Топ-4 во втором дивизионе выглядит следующим образом:

  1. blue.boy
  2. de_troit
  3. lxyxynt
  4. ilona

На данный момент есть только разбор на английском.

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

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

And again your contest at the very end of august(round #84, 29 aug 2011).
47 to all.

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

Автор оригинален в своих смайликах. Мило.

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

UPD: Пофикшено.

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

    О таком можно и в личку сказать ;)

    Всем удачи на уже сегодняшнем контесте, надеюсь, будет весело)

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

Will the problems be sorted by difficulty or not?

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

What a pity that I cannot attend this match because it is 1st,Sep in my timezone and I must back to school. But I wish everybody will enjoy this match and do your best!

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

    We should back to school the day after tomorrow, so we can do.

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

    I must back to school too.For I haven't finished my homework,I have to stay up to finish them.So I can sttend this match.How happy!

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

      My teacher told me that we'll have an exam on 3rd and it realy shocked me...I wish my test scores will be as many as my rating on CF...700 is enough in fact...

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

    Back to school on Saturday, poor you guy. Anyway, virtual participation is still available for you later :)

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

Wow! Mr. witua always your problemset is great! ;) Thanks for preparing another contest!

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

The cute faces are nice!

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

Let's hope for a * lucky * round to all :)

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

    Unfortunately, it can't be lucky for all of us — someone has to be a looser..:)

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

      It depends on what you expect for the match.

      If I solve 3 or 4 problems, I learn something new (a good idea, algorithm, etc) from one of the problems I solve and I feel happy with my solutions, but many people are lucky so I lose rating, I consider myself lucky in the contest.

      Besides rating is not everything, you can lose rating and then increase your rating in another match, but a good idea or solution that makes you learn something interesting, is never lost.

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

I was expecting it to be on the 29th. Was you n th birthday too great to find a time for contest this year?

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

    Unfortunately, it was scheduled before I was setted as an author. Sorry for disappointing you.

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

I 've Been Missing Normal Score Distribution ! Thank You ! I Wish Luck for Everyone :)

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

Hope all the best from this contest!!!! ........Good luck and Have fun everyone ......:)

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

Can somebody explain the solution for Div2-D ? It drove me nuts.

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

Спасибо за раунд, было очень интересно порешать :)

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

can somebody tell me how to solve problem D in div 2?it drives me crazy...

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

Классный раунд, спасибо автору. Даже если у меня упадут все задачи, я не расстроюсь. Веселье от 11 взломов просто неоценимое.

P.S. Видел решение в С за куб. Ну как такое вообще может в голову прийти?

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

In my opinion, Div2C is the easiest problem.

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

Кто-то знает в чем особенность пятого теста на С?

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

    У меня тоже на нем падает. Почему — пока не могу понять.

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

    Видимо в том, что некорректно считать перестановку циклически замкнутой. Тест сходу придумать не могу, но, кажется, валилось именно из-за этого.

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

    У меня заработало, когда я начал сдвигать перестановку в другую сторону

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

По задаче Д (див 1) надо было перебирать по размерам стягивающего прямоугольника и поскольку известно, что хотя бы одна точка треугольника будет в вершине этого прямоугольника, то аккуратно расписать случаи? Или я чего-то более красивого не заметил?

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

    Я бы считал кол-во точек с различной парностью координат, а потом просто перебираем 6 чисел(от 0 до 1) — координаты треугольника и смотрим чтобы четная площадь была. Естественно, потом нужно вычесть все треугольники нулевой площади.

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

      да, я бы так же делал, тем более, что такая задача уже была (как я ниже написал) и так я ее и решил, видимо

      в этой задаче, видимо, больше проблема вычислять, сколько троек точек на одной прямой

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

        Да, пожалуй так код выходит проще гораздо, со стягивающими прямоугольниками случай 3 точки на одной прямой отпадает, только получается куча вариантов с подвариантами (1 точка на углах, 2 точки на углах: на одной стороне, противоположные, 3 точки на углах).

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

          что такое стягивающие прямоугольники, можете сказать?

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

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

            То есть, идейно, пребираем все размеры стягивающего прямоугольника (x; y), и если мы аккуратно подсчитаем сколько треугольников туда влезет, и при этом мы знаем что всего можно запихать (W-x+1)*(H-y+1) таких прямоугольников, то ответ должен быть суммой по всем размерам.

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

              "Получается что все точки треугольника лежат на сторонах этого прямоугольника."

              это не так, возьмем треугольник (0,0),(3,4),(1,3) (1,3) не лежит на стороне

              Но все равно, это сильно упрощает решение

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

Lot of TLE's in div2 problem B :)

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

    In div2_B I hacked 4 contestant with one test — max test.

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

      I hacked 5 contestants with max test.

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

        how i can hack solution?

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

          First, you need to block your solution (you can do it on tab "Problems" by clicking on lock icon). Then you'll be able to view and hack solutions of blocked problem by double-clicking into cells in your room.

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

Как всегда не хватило последних секунд...

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

I failed DIV I — C 4 times. Two of them were because the examples were symetric so I misunderstood the way of rotating (I was shifting to the right instead of shifting to the left), and in all the submissions I failed pretest 5. I cannot find where to get the pretests, but it seems a lot of people failed that test case. Can anyone who failed that case, and then fixed it, tell me what was the mistake on your code? Does anyone know where can I find the test case?

Also for problem B the problem statement was wrong. Even if the examples clarified it, you can choose x = 0 and it also works (it doesn't say x > 0 or x is a positive integer, it just says "number x" and 0 is a number.

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

    I misunderstood the way of rotating too!

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

    Yes, that was a mistake causing WA on test 5.

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

      I tried with both ways of rotating and still got WA.

      I looked at the test case I failed and my bug was considering the permutations as cyclical. I can't believe I looked for the bug for almost an hour and couldn't find it!

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

        Same with me. Fortunately, I decided to skip it after a bunch of submissions and had enough time to solve another problem.

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

      So I WA for 6 times!

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

    where can I find the test case? -> It looks like pretest #5 during the contest is called test #5 afterwards.

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

Seems like there is a test case in problem A that is designed to stuck java's Arrays.sort

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

Научите меня читать:(

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

    К сожалению, если не научился читать к 20 годам, шансов уже нет. Та же фигня =(

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

Задача Д — уже похожая задача была, только там дается n точек, никакие 3 не лежат на одной прямой, нужно посчитать количество треугольников с целой площадью

как я понимаю, задача Д отличается лишь тем, что нужно еще уметь считать, сколько троек точек лежат на одной прямой?

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

System tests are still testing submissions for the first 10 minutes of contest (in DIV I) and it already tested 26% of the submissions. That means that the goal of this match was being very fast to solve problem A, that's not very nice. In my opinion the difference of dificulty between problems A and B was very big.

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

Анти-джаваквиксорт тест :(

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

Am I the only one to have solved div2 A recursively as in the description? :D

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

I didn't do well,but I still like this round very much.It is my first time to do Div1.Thank you!

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

Somebody used an anti-quicksort challenge again. So stupid of me!

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

Не пришло уведомление о взломе -> не пересабмитил. Windows 7, Chrome 21.0.1180.83.

Раньше такого не замечал. С чем это связано? Нагрузка сервера или проблема в браузере/компьютере/еще что? Были ли под конец раунда у кого-нибудь еще такие случаи? Не очень приятно.

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

Как решается C человеческим способом? Я писал дерево отрезков для выбора минимума, в дерево кидались интервалы где некая функция убывает либо возрастает. не успел.

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

    Вместо дерева отрезков делать линейный проход с хипом

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

    линейный проход, с двумя сетами: в одном сете все такие x: posb[x] < posa[x], в другом posa[x] >= posb[x]

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

Почему в A падает такое решениe(WA): 1)Находим неправильные пары чисел(т.е инверсии соседних элементов). 2)Если их много, то говорим NO. 3)Иначе каждое плохое число свопаем со всеми числами в массиве, и смотрим, получился ли он отсортированным.

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

    Потому что, сделав один обмен несоседних чисел, можно убрать 4, как ты говоришь "неправильные пары".

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

      Если в массиве есть аж 4 "неправильные пары", один обмен заведомо не спасёт, так что обнаружив такое их количество, есть смысл сразу вывести NO.

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

        15342 Сколько тут неправильных пар?

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

          Две.

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

            Я, кстати, исходный массив сортировал, а потом смотрел сколько чисел поменяли свои места. если 2 или 0, то YES, в противном случае NO. Во время контеста накосячил (написал условие вместо цикла), но на дорешке сдал.

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

    Со всеми числами или со всеми неправильными? Если со всеми, то TL должен быть. А много -- это сколько?

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

      Ну я вообще только самую левую искал, поэтому работает за линию. Но видел людей, которые брали побольше (10 + eps), и тоже получали WA.

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

This problemset is interesting~~ enjoy a lot... Although I have made a silly mistake in Problem B >_<. One of my friends' Java solution fail because of Arrays.sort's issue...Actually I don't think it is good to put such a case >_<...

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

It Was a Very Nice problemset and I myself really enjoyed it ! Thank You All for preparing contest (and ofcourse participating The Contest :) ) . But I had a Problem With Task E Div1 in Place where The problem Described the pair l,r many people didn't notice that its a1,,,,al,ar,....,an :D i had 4 WA because of it and Didn't manage to read the rest of the problems (after A I jumbed to E :D)

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

witua's rounds have always been good for me, and ratings is always increasing..

Round # Rating diff
77 DNP
84 -47
91 +57
104 +87
129 +96
136 +226
Thank you witua and hope this relation continues ;)

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

I'm 256. in final stadings. And I have 2560 points :D. Interesting numbers :)

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

I did a little mistake in problem C div 2. I counted the number of changes and then, I divided it by two. When I saw that 3 — 2 — 1 gave me only 1, it was late, I was blocked this solution. I got it, it not the same return (cant <= 2) that return (cant / 2 <= 1). Thanks for this great contest.

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

    I was able to solve A-D correctly. After contest... :( But I enjoyed the problems, they are really interesting.

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

В div. 2 — B при решении использовал осмотр чисел от 1 до sqrt(x)+2 и завалил финальное тестирование(

Оказалось, надо было ограничивать sqrt(x)+1.

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

    Ещё можно было добавить проверку, не рассматривали ли мы это число раньше

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

Считалось ли решение В за времени ассимптотически верным? А с такой же асимптотикой по памяти?

UPD. В предыдущих правках были ошибки.

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

    Это про какую задачу?

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

      Это про В...

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

        У меня решение за O((n+m)*sqrt(n)) (ведь имелась ввиду именно такая асимптотика? :) ), памяти O(n+m), с корнем уже не должна влезть

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

          После прочтения Вашего решения я ощутил себя тупицей, постоянно выбирающим страшно неоптимальные пути...

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

          Ты как-то по другому решаешь или же можно другими способами решить, более легкими и простыми? А то в голове у меня небыло такого даже написать. С одной стороны все очень просто, а с другой куча не ясностей.

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

            А вы уверены, что говорите о той же задаче? Они явно обсуждают задачу Б первого дивизиона

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

    Ок, формулу поменяли :(

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

      В смысле?! о_О Посмотрите на решения на С++, использующие 200 с лишним МБ памяти.

      UPD. Насчет n * m — ошибка, разумеется, n + m.

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

My solution for problem A (div1) failed the system test (Time Limit Exceeded). It's quite unclear to me how it could get time limit when it's a O(nlogn) solution with n<=100000. In my computer it works very fast. How can I contact to anyone who can check that? Seems like unfair to me

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

This is not first incident when one contestant asks help from another one during contest. Someone (I won't tell who) sent me message like this:

1)how to solve C help me please

2)it won't do harm for your rating. just + for me....

It won't "+" for you. If I helped:

1)it won't be your really rating.

2)it will affect to others rating.

3)do you really want to practice ComputerProgramming?

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

Сегодня на контесте заметил:  Баг или фича? Я про полосу прокрутки.

Ubuntu 12.04, Google Chrome Version 21.0.1180.89

В FF все нормально

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

    У меня такая же полоса прокрутки в половине сабмитов. Windows 7, браузер — Chrome

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

      И у меня этот баг начал с недавних пор проявляться, win7 x64 Chrome 21.

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

my code is giving correct output(=91) on test case 9 but here it is giving wrong answer on test case 9 2084000

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

    i did submit your solution and it got AC. i just changed, the size of s1,s2,s3 and i submitted it with GNU C++ 4.6, instead of GNU C++0x .

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

      sorry, i forgot the link

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

        @fab But what can be the reason of increasing array size?? on my system it is giving correct answer for test case 9.(=91), for even an array of size 10??

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

          i really don't know. it did give the right answer in my computer too, i just increased the array size to be sure ( it almost never hurts to let it have some air to breath ) i asked some of my friend, one of them, said, it might be the C++0x, and it still might not be completely perfect. but again, i don't know. sorry.

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

          actually 10^9 is 10 digits, so your arrays are too small.

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

            thanx actually i use bloodshed dev c++ compiler which gives correct output even when array size is exceeded by 1 or 2 i think.....

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

              Stop using it, it is old and unmaintained. Try MinGW+Code::Blocks or MS VC++ Express.

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

Господа. Кто-нибудь подскажет мне. Тест номер 5 в задаче E div 2: 10

  • 5 1 6 2 8 3 4 10 9 7

  • 3 1 10 6 8 5 2 7 9 4

Ответ:

  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 2
  • 0
  • 1

Почему? Ведь после первого сдвига перестановки будут такие:

  • 5 1 6 2 8 3 4 10 9 7

  • 4 3 1 10 6 8 5 2 7 9 Как минимальное расстояние может быть равно 0?

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

    Сдвиг в другую сторону.

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

      Спасибо. Я смог завалить 2 задачи из-за своей невнимательности. :-(

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

Can someone please explain in detail how to solve problem D in Division II?

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

    number x must appear more than x times,add them together,so the numbers that are useful are no more than sqrt(n).You can use the prefix sum and calc all the number'time by brute force.Notice the time limit is 4 seconds.(sorry,my English is poor.)

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

    By the way,who is the person in your photo? It seems to come from Star Wars.

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

Господа, прошу помощи. Я не пойму задачу про слоника и функцию. Поясните пожалуйста. Ответ такой n, 1, 2,...n-1; Но ума не приложу почему. Если я правильно понял, то мне нужно получить последовательность, чтобы подав ее в функцию f получилась последовательность 1..n. При рекурсивном спуске всегда получается ответ n, 1, 2,...n-1; Но если подавать эту последовательность на вход, я не могу получить возрастающей последовательности 1..n . Где я ошибаюсь?

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

    суть задачи заключалась в том что нужно данную функцыю запустить задом на перед.И некоторые в условий задачи понимали не правельно и делали так что свапали елементы местами и потом запускали функцыю но нужно запусть функцыю для следуйщего елемента а потом свапнуть.вот наглядный премер функцый задом на перед вызываем функцыю для первого элемента у нас последовательность такая.

    1 2 3

    вызываем для 1 функцию

    функция вызывает функцыю для 2 а потом свапает но так как функцыя для 2 ещо не закончилась она не может свапнуть функция для 2 вызывает 3 и тоже не может свапнуть потом функция для 3 уже не может идти дальше потому что элемент последний и заканчивает роботу тем самым функция для 2 свапает 2 и 3 элемент уже вид последовательности такой 1 3 2 функция для 2 заканчивает свою роботу тем самым заставляет функцию для 1 свапнуть 1 и 2 елемент теперь последовательность принимает окончательный вид 3 1 2

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

      Простите, кажется я не понимаю условие. Пусть f- функция слоника, тогда должно быть так:

      f(n) /* n<>1 -> f(n-1) -> swap -> ..-> f(1) -> n,1,2,...n-1 теперь происходит возврат f(1)->swap->f(2)->swap->f(n-1)->swap... Также должно быть? если да, то у меня не получается возрастающей последовательности, если подам на вход n, 1,2,... n-1; Пока не понимаю...

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

        ну вот смотри мы запросили функцию слоник f(n) она запустила функцию f(n-1) а потом свап таким образом что свап не задействуется пока функция f(n-1) не закончитса и так оно будет вызывать до 1 а потом просто функция вылетит и все функций начнут свапать будет происходить так (3 1 2 тут функция вылетит) (1 3 2 функция для 2 свапнить x и x-1 элемент тоесть 2 и 1) (1 2 3 функция для 3 аналогично свапнить 3 и 2 элемент)

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

Интересный был контест, только мне почемуто кажитса что во втором девизионе первые три задачи были слишком легкие

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

    Но ты почему-то 2 задачи решил и ты на 768 месте:)

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

      третью не решил потому что забыл эвристику квиксорта а остальное баги в проге помогли.А так задачи были не очень сложные

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

        Если смотреть на D и E, то первые 3 задачи халявы. На этом контесте роль играл скорость и конечно hack(кстати, это у меня первый раз). Если смотреть на результаты, участники между 50 местом и 500 местом, многие решили только первые 3 задачи.

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

          ну так я и говорю что первые 3 задачи лёгкие

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

По задаче D(div2). Пока еще не разобрался с решением в разборе, но придумал вот такое: Отсортим все запросы по правой границе. Пройдемся по массиву, начиная с первого элемента и если он меньше n, то сделаем следующее: добавим в вектор, который отвечает за это число его индекс. Теперь, если мы получили, что размер этого вектора больше или равен этого числа, то это означает, что чтобы этот элемент был включен в ответ, то левая граница запроса должна располагалаться между индексами (cnt[b][sz — b — 1] + 1) и (cnt[b][sz — b]) (включая концы). Пометим это, прибавив 1 на этом отрезке, но не забывая отнять 1 на прошлом отрезке для этого же числа. Теперь, чтобы ответить на запрос, нам всего лишь нужно вывести l-ый элемент. P.S. cnt[b] — вектор с индексами элементов b, sz — его текущий размер. Кому интересно, вот код: 2086625. Надеюсь, решение не слишком тупо. Извиняюсь, если я неправильно понял решение из разбора и изложил его же своими словами.

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

thanks for preparing the contest and the problemset. i had a little problem with task C ( div.1 ) and i thought it might be someone elses' problem, too: i saw that a lot of people ( including myself ), got wrong answer on test 5 and i think, they made the same mistake that i did, and it could easily be prevented, just by making better thought, sample cases. the problem was that, i ( and i think some other contestants ) did make a little mistake in understanding how the shift works, so, the solution we outputed, was just bacwards. but if the test case 5 ( which is a reasonable case with n = 10 ) was a sample case, we could easily have realized this and get it right.

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

    I WA on test5 too,and I realized the reason after my brute force program get Wa too.I think it is important to understand the problem more carefully.I just hope that we won't make the same mistake in the future contests;

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

      i do think it's important to be careful and try not to make mistakes, like this. but it's not an implementation problem, and in this problems, finding the algorithm is the most important part, not little things like this. and second of all, i think the idea behind sample cases, is to prevent this kind of mistakes ( and/or for understanding the problem, better ) and it seems to be a common mistake, because at least more than half of the contestants ( the ones that i checked ) who got WA in this problem, did get WA at least once on 5. i don't think it's that important.

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

А на чем Б-шку ломали?

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

    Видимо, некоторые делители до n / 2 перебирали, а не до корня.

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

      Некоторые делители до n / 2, некоторые до n перебирали.

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

    Блин, почему у меня в комнате такого не было((((

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

Кто подкажет, почему qsort улетает на 82 тесте в задаче C (div 2). Тест 81, где 99996 чисел пролетает за 60 мс, а тест 81 с 100000 числами падает по TL.

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

    Потому что у тебя опорный элемент в середине. Представь, что случится, если там всякий раз будет оказываться максимум или минимум.

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

      А куда лучше всего его передвинуть или что можно изменить?

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

        Ну как минимум нужно брать случайный.

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

          Пытался написать рандом от L до R и упал по времени на тесте 6

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

            Не значение элемента рандомное, а его индекс в массиве.

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

              Упс, вот в этом я и правда ошибся. Большое спасибо Вам за подсказку ;)

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

It was my first CF round where I was to rank up, after 3 contests losing rating...

I found the problemset very interesting and I was able to get accepted for 2 problems, A and C!!!

I wish that we can have more rounds like this in a near future and wish good luck to everyone in the upcoming school year as well!!

Bruno

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

Очень странно ведет себя задача D из Div2. Написал решение — получил WA33. После получаса поисков решил посмотреть на АС решения других участников: понял, что моё концептуально не отличается. Попробовал сдать чужие АС решения — WA33, кто-нибудь знает в чём дело?

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

    Интересно, что тест 33 поменялся со времени соревнования: раньше начинался на

    100000 100000
    413 212 432 39 177 169 ...
    

    , а теперь на

    100000 100000
    362 328 428 153 323 415 ...
    
    • »
      »
      »
      12 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Это либо ошибка, либо своеобразный rejudge =) Есть ли смысл пытаться сдать эту задачу сейчас, я имею в виду, у кого-нибудь сдается его решение?

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

        Неа(

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

        Только что пересдал. Спокойно прошло.

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

          Хмм… Эта посылка, так: 2096960? В ней тест 33 снова отличается от приведённых выше.

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

            Странно вот что : если отправлять по коду 221D то WA33, а если по 220B, то AC. Мистика.

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

              У мне на обоих кодах решение получает WA33

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

      Та же ерунда. Тест 33 начинается на

      362 328 428 153 ...

      И таска не проходит

      Третий вариант, который встречался:

      250 302 154 91 381 407 ...

      На нем проходит.

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

Hi,

Can anyone help me in knowing what can be done in https://mirror.codeforces.com/contest/220/submission/63940597 whose complexity is O(nlogn + m sqrt(n)logn) to get AC.

(Problem:https://mirror.codeforces.com/contest/220/problem/B)]

Thanks,