EG0R's blog

By EG0R, 10 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.

Full text and comments »

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

By EG0R, 10 years ago, translation, In English

Hello everyone!

Codeforces Round #235 (Div. 2) will take place on March 10th at 19:30 MSK.

This is my first Codeforces round and I hope not the last one.

I'd like to thank Gerald Agapov (Gerald), Roman Rubanenko (Rubanenko), Sergey Oryshych (Oryshych) for helping me to prepare round, and Mariya Belova for translation of all problem statements into English.

Scoring: 500-1000-1500-2000-2500

GL & HF!

Top five:

  1. UESTC_XHXJ

  2. GoodByeAhu

  3. OrzSKYDEC

  4. simonlindholm

  5. angelyue

Congratulations of participant hoanglmdiv2, who solved the problem E.

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.

English tutorial

Full text and comments »

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