### EG0R's blog

By EG0R, 7 years ago, translation, #### 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. Tutorial of Codeforces Round #235 (Div. 2) 235, Comments (39)
 » When will the editorials be published ?
•  » » Exactly :D
 » Thank you for tutorial.
 » I know the problem D should be dynamic programming, but I still don't know how to solve this problem
 » I think that you should use Unable to parse markup [type=CF_TEX] to write mathematics formulas.
 » For problem D can you tell me what 'mask of reshuffle' means? sorry i don't get the solution clearly
•  » » 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.
•  » » » 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.
 » 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,
 » 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 ?
•  » » It means that e.g. in 212232, here size of number(212232) is 6 digits. 2 is coming 4 times. so in the frequency array we are setting frequency = 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.
 » 7 years ago, # | ← Rev. 2 →   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.
•  » » This is the solution: for(int i=1;i<2^l;i++) for(int j=0;j 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.
•  » » » Thank you sagar! I appreciate it! :)
•  » » » sagar,the state dp[i][j] is the total numbers close to the number determined by the i mask modulo j, correct?
•  » » » » yes.
•  » » » » » is j the modulo or the actual number represented by the i mask..sorry got confused.
•  » » » » » » j here is always modulo, & the beauty is you can always calculate next modulo after taking any other digit into account.
•  » » » » » » » 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
•  » » » » » » » » 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 = 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.
•  » » » » » » » » » i see..thank you! this definitely isn't a beginner dp.
•  » » » » » » » » » 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<
•  » » » » » » » » » 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.
•  » » » Since we are covering all permutations, how does dp approach reduces time complexity? (over brute force approach)
•  » » » » It's the difference between n! and n*2^n.
•  » » » Really sagar.topcoder, you explained wonderfully. I appreciate your efforts.
 » 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 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 = 7But the 13%8 is equal to 5. Am I missing something here? Where am I going wrong? Can anybody please clarify...
•  » » I think the number that is formed is 31...dp+=dp---->(3*10+1), here the binary string is the mask, and also this one gives 13...dp+=dp--->(1*10+3)
 » 6 years ago, # | ← Rev. 3 →   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: 11114404After 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.). :)
•  » » 3 4 means that the number of zeroes should be 3. 1101101 contains just 2 zeroes. Hence, your solution fails.
 » Can anyone please explain problem C? Editorial is totally incomprehensible to me.
•  » » I don't know if this is still relevant, but, try working out a few examples. That's the only way to understand and solve constructive problems. These type of problems rely heavily on observations. The common pattern in most constructive, atleast upto div1B is that, you first need to find those constraints and observations that divide the test-set into YES or NO. Then, work on developing an implementation for the YES set.
 » Ladies and gentlemen, is this the highest dimensional dp ever written ? http://codeforces.com/contest/401/submission/22059230
•  » » Sorry it's not ==> My submission
 » 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 !
 » Why my code get TL if I submit it in C11 but it get AC if I submit it in C++ ?Problem: 401C - TeamTL: 43464060AC: 43464024
 » 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
•  » » Could you explain it further? what was your intuition behind it?it's hard for me to follow this editorial.
•  » » I have a much easier approach , first you check for -1 conditions , then you fix all the 0's like this : 0 0 0 0 0 , then you start inserting 1's starting after first 0 like this 0 1 0 1 0 0 0 , and keep doing this in circular fashion , we can store number of 1's in cnt array , here's the solution : solutionint n,m; cin>>n>>m; string ans ; if(m>((n+1)*2) || m<(n-1)) { cout<<"-1\n"; return ; } vi cnt1(n+1); int times=0; for(int i=1 ; times