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

Автор EG0R, 4 года назад, По-русски,

Задача А — Ваня и карточки

Решение задачи заключается в том, что бы просуммировать все числа которые записанны на карточках, и пытатся эту сумму свести к нулю за минимальное количество операций, используя операции +х и -х.

Решение А

Задача Б — Сережа и контесты

Поскольку ограничения в этой задаче не очень большие, то можно написать простой жадный алгоритм. Вначале обозначить в массиве номера контестов которые запомнил Сережа, как занятые. Для нахождения максимального количества контестов, нужно посмотреть сколько ячеек, номера которых меньше за х, еще не заняты. Это и будет максимальный ответ. Для нахождения минимального количества, нужно пройтись по массиву и пытаться как можно больше вставлять контести типа "Div1+Div2" — это можно будет сделать, если будут свободны две подряд ячейки нашего массива. Если же нельзя вставить контест типа "Div1+Div2", тогда в свободный номер забиваем контест типа "Div2". Проделав такие операции, мы узнаем минимальное количество контестов.

Решение Б

Задача С — Команда

Эту задачу можно было делать несколькими способами, я расскажу Вам об одном из них. Обозначим количество карточек на которых записано 0 — n, а количество карточек на которых записано 1 — m. Тогда можно сделать нужную последовательность когда (n - 1 <= m && m <= 2 * (n + 1)).

Если же все таки можно сделать нужную последовательность, рассмотрим 3 случая:

  1. (m == n - 1). Тогда выводим единички и нули через один, но обязательно начинаем с 0.

  2. (m == n). Тогда выводим единички и нули через один, но тут мы можем начинать и с 0, и с 1

  3. (m >= n + 1 && m <= 2 * (n + 1)). В этом случае нам обязательно нужно начинать с 1 и выводит единички и нули через один. В конце тоже должна быть обязательно единичка. Если мы доходим до конца но единички еще остались, то пытаемся прилепить по одной единичке к тем что у нас есть. Например у нас было 10101, у нас осталось две единички, делаем сначала 110101, а потом 1101101. После таких операций мы получим правильный ответ.

Решение С

На счет того что некоторые решения не проходили 11 тест на FPC, но проходили на Delphi, то в этой ситуации участник должен был понимать, что на Паскале вывод займет достаточно много времени, и он должен был или как-то оптимизировать решение, или же написать в другой среде.

Задача Д — Роман и числа

Эту задачу можно отнести к теме динамическое программирование. Используя маски для запоминания взятых уже цифр мы можем с помощью динамики очень легко решить эту задачу. Пускай у нас будет динамика — dp[i][x], где i — маска перестановки, а х — это остаток от деления данной перестановки на m. Будем перебирать сами маски и остаток. При добавлении цифры a[j] будем использовать такой переход:

dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] := dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] + dp[i,x];

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


for i:=0 to 9 do for j:=2 to b[i] do ans:=ans div int64(j);

Для улучшения времени работы программы, можно приписывать одинаковые цифры в порядке их следования в числе.

Решение Д

Задача Е — Олимпиада

Для начала в этой задаче нужно было понять, что пару учеников мы могли задавать в виде прямоугольника. Тогда расстояние между учениками это диагональ прямоугольника. Пускай первый ученик находится в точке (x1,y1), а второй в точке (x2,y2). В этом случае нам нужно что бы выполнялись два условия:

  • L*L <= (abs(x1-x2)*abs(x1-x2) + abs(y1-y2)*abs(y1-y2)) <= R*R

  • gcd(abs(x1-x2),abs(y1-y2)) == 1

Так как поле может быть 100000*100000, то понятно что перебор значений abs(x1-x2) и abs(y1-y2) займет достаточно много времени. Поэтому будем перебирать только одно значение, а количество вхождений второго вычислять из нашего неравенства:

  • L*L <= (abs(x1-x2)*abs(x1-x2) + abs(y1-y2)*abs(y1-y2)) <= R*R

  • L*L - abs(x1-x2)*abs(x1-x2) <= abs(y1-y2)*abs(y1-y2) <= R*R - abs(x1-x2)*abs(x1-x2)

Количество вариантов разместить наш квадрат на поле n*m будет (n-abs(x1-x2)+1)*(m-abs(y1-y2)+1). Вычисление суммы (n-abs(x1-x2)+1) не очень сложное, но вот что бы вычислить сумму (m-abs(y1-y2)+1), где (L*L<=abs(x1-x2)*abs(x1-x2)<=abs(y1-y2)*abs(y1-y2)<=R*R-abs(x1-x2)*abs(x1-x2)), будет немного тяжелее. Нужно использовать метод включения-исключения и найти сумму чисел на отрезке, которые делятся хотя бы на один из простых множителей нашего числа abs(x1-x2).

К сожалению, по моей вине, в раунд попала задача которая ранее была использована на другом соревновании. Так как это не соответствует правилам Codeforces, задача E будет удалена.

Решение Е

Хочу сказать спасибо Сергею Орышичу (Oryshych) за помощь в написании разбора.

Разбор задач Codeforces Round #235 (Div. 2)
 
 
 
 
  • Проголосовать: нравится  
  • +44
  • Проголосовать: не нравится  

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

А что есть v в задаче Д?

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

D, ответ поделить на количество вхождений каждой цифры — здесь должно быть "на факториалы количества", правильно?

Можно в разбор добавить так же ссылки на авторские исходники? Так будет проще понять сложные моменты. К примеру, Е без исходника как-то очень трудно воспринимается.

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

dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] := dp[i or (1 shl (j-1)),(x*10+a[j]) mod m] + dp[i,x];

И все сразу стало понятно...

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

    Я долго пытался найти различие между выражением "dp[i or (1 shl (j-1)),(x*10+a[j]) mod m]" и выражением "dp[i or (1 shl (j-1)),(x*10+a[j]) mod m]"

    Автор выразил dp[a][b] через dp[a][b] + dp[c][d]. Круто.

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

      Не лучше ли тогда было написать

      inc(dp[i or (1 shl (j-1)),(x*10+a[j]) mod m], dp[i,x]);

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

When will the editorials be published ?

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

Не понял решения D,E. Объясните, плз.

А в задаче С на FPC достаточно было склеить строку-ответ и вывести ее в самом конце)

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

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

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

Thank you for tutorial.

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

Возник вопрос по задаче D. Есть две почти одинаковые отправки: 5991586 и 5991163. Отличие одно: в первой — массив w[2^18][100], во второй — w[100][2^18] (соответственно меняется подсчет). В первом случае решение проходит за 500 с небольшим мс, во втором — лимит по времени не на самом тяжелом тесте. Почему такая большая разница (как минимум, в 8 раз)?

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

I know the problem D should be dynamic programming, but I still don't know how to solve this problem

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

I know the problem D should be dynamic programming, but I still don't know how to solve this problem

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

I think that you should use to write mathematics formulas.

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

I think that you should use to write mathematics formulas.

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

It would be good if authors solution is in C/C++ or java.

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

В "B" создал строку из 1-иц и 0-ов, где нолики — незанято. Тогда ответ составил количество успешных совпадений при жадном поиске c регулярным выражением (regexp) по всей строке (global) — /00|0/g и /0/g. Perl код 5990466.

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

For problem D can you tell me what 'mask of reshuffle' means? sorry i don't get the solution clearly

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

    Bitmask for this problem let you know that whether the i-th digit of the given number has been used or not. For example, if my number is 1223 and my mask is 0100, that mean I have constructed number 2. If my mask is 1110, that mean I have constructed the number which is a "permutation" of number 122.

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

      Someone plz tell me the logic of problem D in detail. I am unable to understand the solution approach of the tutorial. I understand bit masking a little but as a whole how it is being used in this question is very difficult to get.

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

Sorry, but I didn't understand the editorial for Problem D. Is there any similar problem at UVA or TopCoder or in any online judge? If there is any, can you provide the numbers? Thanks for your great effort.

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

Sorry, but I couldn't understand the editorial for Problem D. Others are also very short. Can you elaborate a little? Is there any similar problem at UVA or TopCoder or any other online judge? If you know please give the numbers if possible,

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

In the end we must answer to divide by the factorial number of occurrences of each digit.

What does this even mean ? The english is not correct and I don't understand why we must divide de result ?

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

    It means that e.g. in 212232, here size of number(212232) is 6 digits. 2 is coming 4 times. so in the frequency[10] array we are setting frequency[2] = 4. when we are calculating different numbers via permutation we are thinking that there are factorial(6) new numbers but as in mathematics actually only 6!/4! new numbers are generated. that's why after all the calculation we are dividing the result by factorial(i) for all the values of i from i=0 to i=9. reason is that 8 different permutations of abc are abc acb bac bca cab cba but for 232 as 232 223 322 are the only 3 ( 3!/2! = 6/2 = 3)distinct permutations. Hope you understood the point.

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

For problem D,

I have converted the dp equation to c++

i goes from 0 to 2^l-1
	j goes from 0 to l-1
		x goes from 0 to m-1
			dp [i | (1 << (j-1))] [(x*10+a[j]) mod m] += dp[i][x];

Is my understanding true that dp[i][x] represent the answer for the number whose elements are selected by the i bit mask with divisor as x. In other words it is the answer to the number given by the selected digits and when the divisor is x.

If someone can explain the dp equation in simple terms, that would be a great help. I can only understand that the number with one digit less is somehow related to the number with one digit more.

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

    This is the solution:

    for(int i=1;i<2^l;i++)
            for(int j=0;j<m;j++)
            {
                if(!dp[i][j])continue;
                for(int k=0;k<l;k++)
                    if(!(i&(1<<k)))
                        dp[i|(1<<k)][(j*10+f[k])%m]+=dp[i][j];
            }
    

    say input is {15354} & m=9. The idea is dp[i][j] will contain sum of all cases for particular instance of problem. Say initially, you have counted number 3 only i.e. i = {00100} & j = {3}. Now you may go to i = {10100} (by using 1) or {01100} (by using 5) or {00110} (by using 5) or {00101} (by using 4).

    All these will be generated in loop-k. If you choose 1 then j = ((3)*10+1)%m i.e. ((earlier value of j)*10 + current value of j)%m, similarly we can calculate 5 or 4.

    Coverage of all cases is done like this: initially we set for all single digits in the given number, so i-variable will be executing for {00001, 00010, 00100, 01000, 10000}

    Now to reach 01110 we have following ways:

    01000 --> 01100 --> 011100 & 01000 --> 00100 --> 011100 {this will be covered while using i = 01000 first & then applying above logic}

    00100 --> 01100 --> 011100 & 00100 --> 00110 --> 011100{this will be covered while using i = 00100 first & then applying above logic}

    00010 --> 00110 --> 011100 & 00010 --> 01010 --> 011100{this will be covered while using i = 00010 first & then applying above logic}

    Now if extend this logic to every case, you will see that indeed all the permutation has been covered. To sum up, with each combination we need to do OR operation with all possible Shifts of 1 so that next set of combination is generated for some specific permutations & similarly all the permutation is being generated.

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

      Thank you sagar! I appreciate it! :)

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

      sagar,

      the state dp[i][j] is the total numbers close to the number determined by the i mask modulo j, correct?

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

        yes.

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

          is j the modulo or the actual number represented by the i mask..sorry got confused.

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

            j here is always modulo, & the beauty is you can always calculate next modulo after taking any other digit into account.

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

              i am not getting what the j loop is doing..why is it cycling through all modulo from 0 to m..can you plz clarify that?

              for(int j=0;j<m;j++)

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

                the thing is you do not actually know which modulus you will get when you will count upto a state like in case of 3, d[00100][3] = 1, but if say we reach a state i = 00111 we could have multiple modulo because of the sequence we took & we need this modulo at last. So make this modulus j a part of dp state itself & update it.

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

                  i see..thank you! this definitely isn't a beginner dp.

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

                  maybe i am not understanding some properties of modular arithmetic but i am not getting why are we shifting the mod left. Couldn't we just do f[k]%m instead of (j*10+f[k])%m?

                  dp[i|(1<<k)][(j*10+f[k])%m]+=dp[i][j];

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

                  no we could not, becoz f[k]%m will always be same for a particular k, but real modulus depends on sequence of digits we have chosen.

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

      Since we are covering all permutations, how does dp approach reduces time complexity? (over brute force approach)

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

It's ironic how some problem setters are so smart at coming up with problems, but so lousy at explaining solutions.

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

    I'm sorry I tried. If you do not understand something, write me.

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

what does this (j*10+f[k])%m do ?

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

Can somebody explain this to me in Problem D...

We know, dp[i][j] -> contains no. of all possible numbers in the ith mask having modulo j (wrt m)

Now suppose input is {1,5,3,4,5} and m=8. we have selected 3, i.e. the mask(i) is 00100 and j is 3, then dp[3][3] equals 1.

now if we select 1 with 3, i.e. the mask is now 10100, then according to the tutorial, new modulo of this number(i.e. 13) wrt m(8) = (3*10+1)%8 = 7

But the 13%8 is equal to 5.

Am I missing something here? Where am I going wrong? Can anybody please clarify...

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

    I think the number that is formed is 31...dp[10100][7]+=dp[00100][3]---->(3*10+1), here the binary string is the mask, and also this one gives 13...dp[10100][5]+=dp[10000][1]--->(1*10+3)

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

UPD: Sorry, my bad, I didn't read problem statement correctly.

I don't know if anyone will pay attention to my comment now, but I was doing Problem C while practicing and found that the alternative solution is not being considered by the judge.

In case 5, ie. 3 4, my code outputs 1101101 but the judge declares it's wrong, citing the Jury's solution as 1010101 and message as wrong answer. The number of ones should be 4, but found 5; The number of zeros should be 3, but found 2;

My submission is here: 11114404

After re-reading the question several times, I'm quite sure my answer satisfies all constraints mentioned in problem. 1101101 doesn't have more than 2 adj. 1 and no more than 1 adj. 0.

I request the author, EG0R to kindly look into this problem and resolve this issue(and in case it's my own mistake, point it out.). :)

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

Can anyone please explain problem C? Editorial is totally incomprehensible to me.

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

Ladies and gentlemen, is this the highest dimensional dp ever written ? http://codeforces.com/contest/401/submission/22059230

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

For problem D , my submission get time limit on test 35 and I can't find how to optimize my solution.

This is my submission 36532811 . Any help please !