EG0R's blog

Codeforces Round #235 (Div. 2) — Tutorial
By EG0R, 11 years ago, translation, In English

Problem А

We must sum all numbers, and reduced it to zero by the operations +x and -x.

Solution А

Problem B

You must identify the array of numbers contests that remember Sereja, as employed. If we want to find maximal answer, we must count the number of immune cells. If we want to find mininum answer, we must do the following:

if i-th element is free and (i+1)-th element is free, and i<x then we using round type of "Div1+Div2" and answer++, i-th and (i+1)-th elements define as employed. if i-th element is free and (i+1)-th element is employed then we usign round type "Div2" and answer++, i-th element define as employed.

Solution B

Problem C

n — the number of cards containing number 0 and m — the number of cards containing number 1. We have answer, when ((n-1)<=m && m <= 2 * (n + 1)). If we have answer then we must do the following:

  • if (m == n - 1) then we derive the ones and zeros in one, but we must start from zero.

  • if (m == n) then we derive the ones and zeros in one.

  • if (m > n && m <= 2 * (n + 1)) then we must start form one and we derive the ones and zeros in one, but in the end must be one. And if we in the end and we have ones, then we try to stick to one unit so that we have. For example, we have 10101 and two ones, after we have 110101 and one ones, and then we have 1101101.

Solution С

Problem D

This problem we can be attributed to the dynamic programming. We must using mask and dynamic.

We have dynamic dp[i][x], when i — mask of reshuffle and x — remainder on dividing by m.

if we want to add number a[j], we must using it:

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];

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

  for i:=0 to 9 do

   for j:=2 to b[i] do

     ans:=ans div int64(j);

Solution D

Problem E

If first participant of the contest will contain at point (x1;y1) and second participant of the contest will contain at point (x2;y2), then we need to satisfy two conditions:

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

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

Since the hall can potentially be of size 100,000 x 100,000, even considering each possible size of R or L once will take too much time. And if we iterate value abs(x1-x2) and iterate value abs(y1-y2) then it will take much time too. But if we iterate only value abs(x1-x2) we can find confines of value abs(y1-y2). We can do so:

  • 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)

Number of options to place the square in hall n*m will be (n-abs(x1-x2)+1)*(m-abs(y1-y2)+1). The first quantity is easy to obtain, while the second requires a little more work. To calculate the second quantity, we note that, although w could have a large variety of prime divisors, it does not have very many of them. This important insight allows us to quickly find the sum: we find the prime factors of w, then we use the inclusion-exclusion principle to calculate the sum of all numbers between L and R that are divisible by at least one of the numbers.

Unfortunately, my fault, in the round hit the problem that was previously used on another competition. Since it does not comply Codeforces, problem E will be deleted.

Solution E

Sorry for my English.

  • Vote: I like it
  • +44
  • Vote: I do not like it

Comments Comments (30)
| Write comment?
»
11 years ago, # |
  Vote: I like it -40 Vote: I do not like it

When will the editorials be published ?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +30 Vote: I do not like it

I think that you should use

Unable to parse markup [type=CF_TEX]

to write mathematics formulas.
→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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,

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sagar,

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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yes.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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++)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                11 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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];

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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.

                  → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Really sagar.topcoder, you explained wonderfully. I appreciate your efforts.

      → Reply
»
9 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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.). :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 !

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the implementation for C is quite cumbersome.
Let $$$n_0$$$: the number of 0, $$$n_1$$$ the number of 1.
$$$n_1$$$ must be in constraint $$$n_0-1 \leq n_1 \leq 2n_0+2$$$, otherwise there is no solution.
I will solve for range: $$$n_0 \leq n_1 \leq 2n_0$$$, (you should see my code to understand correctly)
Let $$$a$$$ is the number of patterns '110', $$$b$$$ is the number of patterns '10', so:

$$$ \begin{cases}a+b = n_0\\a+2b=n_1\end{cases} $$$

We are solving in range $$$n_0 \leq n_1 \leq 2n_0$$$, therefore $$$a, b \leq 0$$$. With $$$a, b$$$ after solving two equations. We construct a string answer following the greedy strategy. Up to now, the string answer always start with '1' and end with '0'.
I add some padding characters to get answer.
if $$$n_1 = n_0 - 1$$$, add '0' to start of above string.
if $$$n_1 > 2n_0$$$, add $$$(2n_0 - n_1)$$$ '1' to the end of string.
My solution

→ Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    a+b=n0 a+2b=n1

    what s the logic behind these equations ?

    → Reply
    • »
      »
      »
      9 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      '10' contains 1 '1' and 1 '0'. And we have a '10'.
      '110' contains 2 '1' and 1 '0'. And we have b '110'.
      So n0 = a+b and n1 = a + 2b

      → Reply
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what s the relation between pattern 110 and 10 and the number of n0 , n0 consists of only 0 elements , and these patterns includes 1 , and thank you

    → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain how to solve the D problem if I am using normal masking it is giving me tle because 2^18 for mask and 100 for the reminder and for each case we will check at all digit that is 18 so I think there will better solution or how should I optimize this.

→ Reply
»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

" then we must start form one and we derive the ones and zeros in one, but in the end must be one. And if we in the end and we have ones, then we try to stick to one unit so that we have. For example, we have 10101 and two ones, after we have 110101 and one ones, and then we have 1101101."

Crap explanation. Better learn some english first before writing editorials.

→ Reply