gridnevvvit's blog

By gridnevvvit, 4 years ago, translation, In English,

336A - Vasily the Bear and Triangle

val = |x| + |y|. Then first point is (val * sign(x), 0), second — (0, val * sign(y)). Swap points if needed according to statement.

Let's see why this is the answer. Conditions x ≠ 0 and y ≠ 0 give us that one point is on X-axis, and the other on Y-axis. Let's see how it works for x > 0 and y > 0. Other cases can be proved in similar way. We need to show, that (x, y) belongs to our triangle(including it's borders). In fact (x, y) belongs to segment, connecting (x + y, 0) with (0, x + y). Line through (x + y, 0) and (0, x + y) is Y =  - X + x + y. Using coordinates (x, y) in this equation proves the statement.

Author's solution

336B - Vasily the Bear and Fly

Also you could iterate circles, adding distance for each of them and dividing by m2 in the end. Let's see how the i-th iteration works 1 ≤ i ≤ m. Distance to m + i-th circle is 2R. Distance to m + j-th circle, where |j - i| = 1, is . For other circles it's quite simple to calculate sum of distances. There are i - 2 circles which located to the left of current circle. So, sum of distances for these circles is . In the same manner we can calculate answer for cirlcles which are located to the right of the current circle

Рисунок для теста с 3-мя окружностями

Author's solution

336C - Vasily the Bear and Sequence

Let's check max beauty from 29 to 0. For every possible beauty i our aim is to find largest subset with such beauty. We will include in this subset all numbers, that have 1 at i-th bit. After that we do bitwise and as in statement, and if the resulting value is divisible by 2i, then there is the answer. Solution works in O(n).

Author's solution

336D - Vasily the Bear and Beautiful Strings

any — random binary string, s + g — concatenation of strings, MOD = 1000000007.

String 1 + any always transforms into 0, string 1 — into 1. String 01 + any always transforms into 1, string 01 — into 0. String 001 + any transforms into 0, string 001 — into 1, and so on. Using these facts let's consider following solution.

Cases like strings without ones or zeroes are easy. For every i (in zero-based numbering) let's assume that it is position of the first occurence of 1 in our string. Using already known facts we can understand what is the final result of transformations for such string. If the result equals to g, we add C(cnt[0] + cnt[1] - i - 1, cnt[1] - 1) to the answer. Calculation of binomial coefficients is following: fact[i] = i!%MOD, , C(n, k) = fact[n]inv(fact[n - i]fact[i]), where inv(a) — inverse element modulo MOD. inv(a) = aMOD - 2, because MOD is prime number.

Author's solution

336E - Vasily the Bear and Painting Square

Pretty tough problem. Consider following DP dp[lvl][op][cur][type] — number of ways to take op triangles, if we have 2lvl + 1 squares. cur, type — auxiliary values. Answer will be dp[n][k][0][2]k!. type means type of transitions we make. cur — amount of used quarters (cur = 4 — 2 quarters, cur < 4cur quarters). It is important to distinguish cur = 2 from cur = 4, because amount of consecutive pairs of unused quarters is different.

Значения cur для различных ситуаций

About transitions. type = 2. Iterate amount of pairs (considering cur) of consecutive quarters that we will take. It is important for them to have no common quarters. We can get two pairs only in case cur = 0. Let's also take some quarters that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value dp[lvl][op - choosen][newcur][1] * cntwaystochoose. For better understanding of type = 2 check my solution (calc(n, k, cur, type) — isfordp[n][k][cur][type]).

type = 1. Now we take triangles at the borders (number of squares is 2*lvl + 1). "at the borders" means marked X, see the picture.

Iterate amount of pairs (considering cur) of consecutive triangles we take. It is important for pairs to have no common triangles. Let's also take some triangles that are not in pairs. Calculate number of ways to select corresponding triangles and add to the current DP-state value dp[lvl][op - choosen][cur][0] * cntwaystochoose.

type = 0. We take triangles at the borders (number of squares is 2*lvl). "at the borders" means marked X, see the picture.

Take some triangles, not in pairs. Calculate number of ways to select corresponding triangles and add to current DP-state value dp[lvl - 1][op - choosen][cur][2] * cntwaystochoose. Starting values: dp[0][0][cur][1] = 1, dp[0][cnt][cur][1] = 0, cnt > 0.

Author's solution

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

»
4 years ago, # |
  Vote: I like it -6 Vote: I do not like it

for Problem 336A, 4th condition is that the area of triangle should be minimum, for test case 1 (x=10,y=5) point 'A' should be A(0,10) and point 'C' should be C(20,0) which gives the smallest area of triangle ABC (0.5*20*10 = 100) but answer is given as point A(0,15) and C(15,0) which gives area of triangle as 0.5*15*15 = 112.5, please tell me what I m missing?

  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    It's should be isosceles triangle.

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

    The triangle needs to be Isosceles.

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

    you have to choose such points so that other two angles i.e ACB and BAC should be 45 degree.If you chose other point then angle will be different.For example in first test case we are finding x1,x2,y1,y2 using trigonometry formula i.e. tanθ = perpendicular / base. Suppose D is point having coordinate x and y.From point D we make a perpendicular to line BC and AB and name these point as E and F resp.we know BE = x = 10 and FB = y = 5,we have to find EC (BC = BE + EC) ? , we use tan formula to get FB/EC = tanθ here θ = 45 degree so EC = FB = 5(tan 45 = 1); so x2 = BE + EC = 15; Similarly we find AF(AB = AF + FB), AF/BD(BD = BE = 10) = 1(tan45 = 1) so AF = 10; y1 = AF + FB = 15;

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

gridnevvvit May you please tell us the manner in which these geometric shapes are generated? I think they are really elegant.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The pictures are broken, please fix them.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem C: we have b1 and b2 and ... and bk = 0, is it an accepted answer? 0 mod n = 0 with any n.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Problem B it is mention that experiment repeats for m^2 days. But in authors solution the experiment is running only for m days. Please tell me am i missing something..

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

    Experiment is running m2 days. Authors calculate answer by using following idea. We fix some circle with index i (1 ≤ i ≤ m). After that we calculate sum of of distances to circles with indexes m + j (1 ≤ j ≤ m) by using formula.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem C you have written: after doing bitwise AND of all numbers whose ith bit is set, we have to divide it by 2^i. Can there be a case when it is not divisible by 2^i but divisible by for some other power of 2?

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    It is possible that the bitwise-AND result of numbers with the ith bit set to 1 might be divisible by 2^j, j!=i. But let us analyse what such j's can be.

    Case 1: j>i. If the set chosen for i is such that the jth bit = 1 for all numbers in that set, then this set will indeed be divisible by 2^j. But, since we are iterating i from 29 to 0, this particular j (>i) would already have been considered and a set with equal or greater no. of elements as compared to the set corresponding to i would already have been found out.

    Case 2: j<i. Again, since we are iterating i from 29 to 0, we need not consider the case that the result obtained by bitwise AND of the set corresponding to i will be divisible by 2^j since this will be checked in future iterations of i when it is decremented further till i=j. Here, we may end up with this same set only or perhaps an even larger set which is perfectly divisible by 2^j.

    To sum up, though the set under consideration might be divisible by 2^j (j!=i), but we need not consider divisibility by j's != i since this has already been/will in future be checked. Hope, this clarifies the issue.