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

Автор Kammola, история, 6 лет назад, По-английски

Hello Codeforces,

I hope you liked the problems! Below you can find the tutorials for all problems.

Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Разбор задач Codeforces Round 465 (Div. 2)
  • Проголосовать: нравится
  • +125
  • Проголосовать: не нравится

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

That feeling, when you are solved the problem C by binary and ternary search... http://codeforces.com/contest/935/submission/35499682

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

    You'll learn geometry bro xDD

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

    can you please explain your approach.

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

      I used binary search too. We can calculate the maximum distance between (x2, y2) and some point of the circle. Let's call this distance L (obiously, if the point is outside the cicle, you can use the its entire area, so let's assume that it lies inside the circle). Please notice that we can make a circle such that its radius is L/2, and its center is some point between (x2, y2) and the furthest point of the circle. Now, let's compute the equation f(x) = Ax+B such that it intersects the points (x1, y1) and (x2, y2).

      Now have enough information to binary search our answer: we need a value V between x2, and the furthest point minus L/2 (because we can't make a circle that has positive area outside the original circle), such that the distance between (x2, y2) and (V, f(V)) is equal to L/2. After binary search, we can print x=V, y=f(V), r=L/2.

      Oh, and cases where x1=x2 or y1=y2 must be handled separately.

      If you didn't understand something, or you have any doubts, please feel free to ask. I hope this explanation can be useful to you :)

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

      I think it's something like this..

      You ternary search for the center along the diameter going through Fafa's position and for a fixed point you binary search for the max radius.

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

In problem C why am I getting WA on test 13 ? I used Binary search like algorithm ..My solution

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

Why for Problem C test 10 0 0 0 0 and with my output 5.0000000000000000 5.0000000000000000 4.9999991000000001 it is wrong answer Too large radius.? The Y coordinate of the top point of the embed circle is 9.999999 and the Y of the bottom point is 0.0000001, so it should fit in and not touch the laptop. Where I'm wrong?

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

    You should use long double I think

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

      I got WA using long double, which is actually a compilation error. I don't know whether I picked the wrong version of GCC or what, but had to replace those long doubles with doubles to get AC. The WA code and the AC code .

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

    Your circle must be fully in given circle The distance between (0,0) and (5,5) = 5*sqrt(2). And if we add your radius, we will get 5*sqrt(2)+5(it's the distance between the centre of circle and the furthest point on your circle). 5*sqrt(2)+5 > 10

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

I have a question involving problem D.

Let p be the number of ways in which I can make S1 greater than S2 (modded, of course)

Let q be the total number of ways (pow(m, number_of_erased_letters)) (modded too)

By dividing p by q using modular inverse you can reach the required solution. I got an AC verdict using this.

My question is: Why does just dividing p by q work? Because we know that in our answer p and q should be coprime. Are they always co-prime? Or is there another explanation to why the above method works?

Can anyone elaborate on this?

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

    You should note that

    if x is not a multiple of 109 + 7.

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

      This code gets AC, but I had to remove the operation of dividing num,den by their gcd.

      If you will notice, the "gd" variable is reset to value 1 just to avoid division by the gcd. Can you explain why dividing by gcd is causing WA?

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

    It will work because of inverse modulo property. Suppose you want to find R = P / Q and it can be calculated using modular arithmetic as well ( given that Q is coprime to mod, it will become ( R = P * invQ ) % mod , where invQ is modular inverse of Q such that ( Q * invQ = 1 ) % mod ).

    let g = gcd(P,Q). then P = g * p and Q = g * q, invQ = invg * invq,

    So, ( P * invQ = p * g * invg * invq = p * invq * ( g * invg ) = p * invq ) % mod, because ( g * invg = 1 ) % mod , due to inverse property.

    you can see simplified as well as non-simplified fraction leads to the same result.

    I hope it helps.

    Happy Coding :)

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

Easier way of finding Xap, Yap, if the point is inside circle (Using ratio and proportions)

Link to Code : http://codeforces.com/contest/935/submission/35502661

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

    Thank you so much for this explanation! I couldn't get why everybody is using this formula! Thanks a lot one more time.

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

      If you try to find the center point for wifi router using vectors you will get the same result

      dist is the magnitude of distance between (x1,y1) and (x2,y2)

      Unit Vector in direction from (x2,y2) to (x1,y1) is (x1-x2)/dist for x coordinate and (y1-y2)/dist for y coordinate now simply

      Here, x0 = x2 and y0 = y2,

      unit_vec_along_x = (x1-x2)/dist

      unit_vec_along_y = (y1-y2)/dist

      Distance is the distance of point (x,y) from (x0,y0) along this line

      Any x = x0 + unit_vec_along_x*Distance

      y = y0 + unit_vec_along_y*Distance
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        dist= sqrt( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) )

        Unit vector from (x2,y2) to (x1,y1)

        along x: ( x1-x2 )/dist

        along y: ( y1-y2 )/dist

        also radius r= ( R + dist )/2

        so coordinates of center x= x2 + ( ( x1-x2 )/dist )*r

        y= y2 + ( ( y1-y2 )/dist )*r

        Right? We don't need to check other direction because we are moving in the direction of a unit vector and can guarantee that it to be the farthest from circle boundary?

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

    it's intuitive, but can you prove that this proportion works?

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

      Idea of similar triangles.

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

      I was also unsatisfied with some of the answers provided thus far, so I decided to write a more formal/verbose proof. In case I am incorrectly embedding the image, you can take a look at this image of the problem I created with GeoGebra. This uses the data from the first example given in the problem statement.

      Problem: identify coordinates of (Xap, Yap), and the radius S of the circle centered at (Xap, Yap).

      Given: We are given (X1, Y1), (X2, Y2), R of the larger circle centered at A.

      First, let's find S.

      1. AB + AF = 2 * S
      2. (AB + AF)/2 = S.
      3. Notice AF = R, so we can rewrite => S = (AB + R)/2.

      Now, we need to find the coordinates (Xap, Yap).

      1. Consider triangles ABE and CBD.
      2. Angles AEB and CDB are congruent — both are right angles.
      3. Angles ABE and CBD are congruent — they are the same angle.
      4. By the angle-angle postulate, we have shown that triangles ABE and CBD are similar.

      Since we are trying to solve for Xap and Yap, we observe that:

      1. BD/BC = BE/AB
      2. BC = S, BD = (Xap — X2), BE = (X1 — X2)
      3. (Xap — X2)/S = (X1 — X2)/AB
      4. Xap = S * (X1 — X2)/AB + X2

      We can solve for Yap similarly. Sorry in advance if my post is poorly formatted.

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

I'm pretty sure most people knew what to do in C, it was all about the implementation part. Could we please get the code in the editorial?

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

    The easy way to implement geometry is with complex numbers or a custom Point class. Something like this should work (code in cpp).

    complex<double> c(x1, y1);
    complex<double> p(x2, y2);
    if (c == p) {
        cout << c.real() + R/2.0 << " " << c.imag() << " " << R/2.0 << '\n';
    } else if (abs(c-p) < R) {
        complex<double> ans = p + (abs(c-p) + R)/(2 * abs(c-p)) * (c-p);
        cout << ans.real() << " " << ans.imag() << " " << (abs(c-p) + R) / 2 << '\n';
    } else {
        cout << c.real() << " " << c.imag() << " " << R << '\n';
    }
    

    EDIT: The original code was untested and full of bugs, sorry

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

In problem F, the profit for adding the i-th (2 ≤ i ≤ n - 1) element by x is something like |x - a| + |x - b| - c, which can be reformed to something like max( - 2x + d, e, 2x + f). So we can maintain the maximum of d, e and f separately with segment trees.

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

    Actually, the other solution of the authors is very similar to this one. Thanks for the comment!

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

    When I saw problem with modules, usually this can be solve convert it to a problem where we need find maximum. Are there any standard technique to do so? Or I will put my question in other way, how you convert this thing |x - a| + |x - b| - |a| — |b| + c to this max( - 2x + d, e, 2x + f)?

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

    I got that the profit was

    |b + x - a| + |b + x - c| - (|b - a| + |b - c|).

    How did you convert this to your expressions?

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

Does anyone know abt any online visualizer for geometry problems? like ploting circle and even any conics

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

    Try GeoGebra :)

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

    CSAcademy has a really nice tool.

    There is also a tool to draw with coodinates on a grid, not useful for this problem but still.

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

    I used the one given here

    It did most of the job I needed like plotting using a formula and when plotting multiple functions it will give you their intersection points.

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

In problem F, should we use lazy propagation for updating the range in segment tree?

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

One of my friend submitted a solution for D like this: 35495179.

I'm quite curious. How could modulo-adding fractions directly work? Can anyone prove it?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится
    a·b - 1 + c·d - 1 ≡ (ad + bc)·(bd) - 1

    can be verified via expansion.

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

      Ouch, drafted it in my minds lately and it was crystal clear. If only during contest I figured that out.

      Anyway, thanks for the support, pal. :D

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

how to find point q ? I uses two point form to find slope then we get angle and any point of circle can be rep as rcos(angle) rsin(angle) ?? But i think on diff quad my slope obtained will be diff can anyone plzz tell me can the output of xap,yap can be negative or not

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

Can you explain the last formula in problem D?

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

    When both positions are 0,we have m*m ways to fill in the 0s.
    What about the no of ways so that A becomes greater than B? It will be as simple as selecting 2 numbers from m numbers, then filling the greater one in A. So favourable ways will be mC2.

    So probability becomes mC2/(m*m).

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

      Can you explain, why the next term isn't P(i+1)/(m2) ?

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

        Going to next term means making sure that current place has same value in both A and B. So we have m values that we can fill in A and B. In total we have m*m choices. So prob of filling same value is 1/m.

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

I think in F problem's editorial it should be:
"if neither case 1 nor case 3 exists, then we can only the first option of the previous case."

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

Can someone please post code (or link to someone else's code) that implements both of the editorial's approaches to problem E. Both the Tree Approach and the DP approach. It would be really useful to me.

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

    The editorial presents ONE solution to E, that is tree DP. ie you memoize your states as you traverse the tree.

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

      Kindly share an understandable implementation of the model solution.

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

        I'll explain the dp where the number of plus operators is at most 100, the other one is similar. Let dp_max[v][c] and dp_min[v][c] be the maximum and minimum value we could get in the subtree rooted at v with c plus operators respectively.

        If the vertex v is a digit, then we can simply return the digit if c == 0. Otherwise this state is invalid because we must put c plus operators in this subtree, but we can't. Now if c > size of subtree rooted at vertex v, then this state is invalid. If a state is invalid, we can set dp_max[v][c] = -INF and dp_min[v][c] = INF.

        Otherwise, we could choose to put a '+' or a '-' at the root of this subtree. Let's consider dp_max, the transitions for dp_min are similar. If we put a '+', then we want to maximize or minimize the value of both children of v, so dp_max[v][c] = max{dp_max[left][i] + dp_max[right][c-1-i]} where i = 0..c-1. Note that the c-1 is because we have to put a plus operators at v, so there are only c-1 plus operators to pass on to the children. If we choose to put a '-', then we want to maximize the first child and minimize the second child of v, so dp_max[v][c] = max{dp_max[left][i] + dp_min[right][c-i]} where i = 0..c. This time we put a '-' operator, so we pass on c instead c-1 plus operators to the children of v.

        The above is how the dp works. Here is a link to my implementation: http://codeforces.com/contest/935/submission/35531598 It's not great or all that efficient, but it works. Also, since this is a cf round and not a gym, you can look at other people's submissions from the standings to find an implementation.

        EDIT. there were typos in dp transitions

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

          can you explain your approach for building the tree please ? ehnryx

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

          Thank you very much.

          The problem with just going through standings is it's very difficult to find someone who wrote clean and completely understandable code. The model solutions are usually very clean and have one idea, whereas contest code usually has some debugging statements, and handling some special cases, which might not be required.

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

The editorial uses probability for Problem D. I implemented that approach here, but I don't like it. It's not too clean :\

Here's an equivalent approach, but based on counting rather than probability.

Here's the explanation for the same.

(Beginners may find this useful.)

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

    Please Can you elaborate your explanation a little bit more. why does it necessary to compute all the number of ways to fill up positions from i to N (from your GitHub tutorial) ?

    Advance thanks a lot.

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

      When do you say that A > B ? (For example, why do we say that 112345 is greater that 112333 ?

      This is how we compare. First, we check if the lengths are equal. If they aren't the longer number is greater.

      If they are equal, then there must be some position i, for which A[i] =/= B[i], and all j < i A[j] = B[j]

      That is, there is some FIRST position where the strings aren't equal. The strings share a prefix before that.

      (In this case, it is 1123 — this is the common prefix. Note that if we were comparing 2562 and 7891, then the length of the common prefix is 0 Becasue the first unequal position is the first !)

      Now, we want to place a character at the i-th position of A, or B, or both, or neither (If they are both non-zero).

      How do we do this ?

      Suppose A[i] = 0, and we fill a character at A[i] so that A[i] = B[i]

      For instance, A = 0 1 2 B = 5 1 0

      Suppose we fill A[1] = 5, then it means strings A and B are equal till position 1, and the number of ways of making A > B

      is equal to the number of ways of making A > B, by filling characters from (i + 1). There has to be SOME position after i + 1, after which A > B. So, we simply add f(i + 1, G) as that is exactly the information it contains.

      So, f(i, G) = f(i + 1, G)

      If we set A[i] = 6, then A is already greater than B .... And the 0s after position i can be filled by any of the m digits, and A will still be greater than B.

      f(i, G) = (M — B[i])*f(i + 1, ANY_WAY)

      Because there are (M — B[i]) ways of filling position i so that A[i] > B[i]

      And only one way of filling A[i] so that A[i] = B[i]

      Ultimately, f(i, G) = f(i + 1, G) + (M — B[i])*f(i + 1, ANY_WAY)

      I have just shown the case of A[i] = 0 and B[i] =/= 0.

      A similar analysis can be done to all possibilities. Just think how can we fill A[i] and B[i] ... How can we fill them for A = B, (In that case, count f(i + 1, G) and How can we fill them for A > B


      Explanation is elaborated on GitHub as well.

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

    Hi,

    Could you explain or point to some source to present why the inverse function can be implemented as just pow(n, m-2, m) in this case please?

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

      According to Fermat's Little Theorem,

      x^(p - 1) = 1 (mod p), if p is prime and gcd(x, p) = 1

      x . x^(p - 2) = 1 (mod p) ` This meansx^(-1) = x^(p — 2)`

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

        I have done in the same way(by counting the number of ways). Can you tell me why I am getting wrong answer? My submission Link

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

Can someone explain me , what would be the answer in problem C, if x1=x2 and y1=y2? It is written here there are infinitely many solution, but I saw many of the coders printing (x1+R/2,y,R/2). I am not getting it?

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

    If y1=y2, we can make a circle of diameter max(abs(x2-(x1-r)), abs(x2-(x1+r)). The center of the resulting circle will be (x2+(x1 +- r)/2, y1).

    When I write "x1 +- r", it's because you must use the negative sign if x1 is further from the point (x1-r, y1) that from (x1+r, y1), and the positive one otherwise.

    The same idea is used for the case x1=x2.

    If you didn't understand this comment, you may get the idea if you draw an example in paper. However, feel free to ask me anything. Bye! :)

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

I think there's another solution to 935F(rather obvious, but a bit hard to implement):

Let d[i] = a[i + 1] — a[i] (1 — indexed).

For each query in type 2: just increase d[l — 1] by x and decrease d[r] by x.

For each query in type 1:

The answer is sigma(ABS(d[i])) + (ABS(d[p — 1] + x) — ABS(d[p])) + (ABS(d[p] — x) — ABS(d[p])). (where a[p] is increased)

That is, sigma(ABS(d[i])) + (x + 2 * min(max(d[p — 1], -x), 0)) + (x + 2 * min(max(-d[p], -x), 0)).

Or, sigma(ABS(d[i])) + 2 * x + 2 * (min(max(d[p — 1], -x), 0) + min(max(-d[p], -x), 0)).

So we only need to calculate the minimum number of (min(max(d[p — 1], -x), 0) + min(max(-d[p], -x), 0)).

Consider a 2D plane with n points on it: (d[0], d[1]), (d[1], d[2]), ..., (d[n — 1], d[n]).

Just think about these conditions:

  1. the x-coordinate of the optimal choice is not greater than -x (or it's not less than 0): just maximize the y-coordinate.

  2. the y-coordinate of the optimal choice is not greater than -x (or it's not less than 0): just maximize the x-coordinate.

(Although they may overlap, it doesn't matter)

The only case left is [both the x-coordinate and the y-coordinate are between -x and 0], and we need to maximize the sum of the x-coordinate and the y-coordinate.

Just use 2D segment tree and things like stuff.

Maintain sigma(ABS(d[i])) and all points on the plane.

Each query of type 1 needs only 4 modifications, and each query of type 2 needs only 5(1 of them is about the 2D segment tree).

(Complicated data structures like 'segment tree beats' might speed up the algorithm, but I know little about these)

So the total time complexity is O(N log^2(N)).

(Note that modifications on the first and the last position are a bit special, but the time required to deal with this is O(q)).

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

Problem D. Why do we need to divide probability ( p[i + 1] ) by 'm' in the last 3 cases from editorial? Why can't we take just p[i + 1] ?

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

    Because you can only go to p(i+1) if the both characters at position i are equal, since one of the characters is already fixed, the probability of the other being the same as it is 1 / m.

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

"if neither case 1 nor case 3 exists, then we can only the second option of the previous case", maybe need to be: "first option of the previous case"

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

can someone explain dp part of prob. E i cant figure it out. thanks!!

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

"Fifa and Fafa are sharing a flat."
Should not Fafa's position be within the flat circle? (-_-)

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

Was E possible without making a separate min/max memoization array, for both using p plusses and m minuses, and limiting their indexes in [0...100]?

I was wondering if a maximum using P pluses, is actually a negated minimum by using M pluses? This approach did not work though, not sure why.

My code: https://pastebin.com/XjNxtsmA

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

Why am I getting WA on test 8 in problem C? This is my solution - http://codeforces.com/contest/935/submission/35524655

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

Is anyone facing problem/ faced problem in pass 11th test case for 935D — Fafa and Ancient Alphabet? Did anyone find the problem there? as in what anybody might be missing while solving the problem ?

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

Solution to div2 C in O(1).

No need for proof, just quick maths!

Given y = mx + b and (x-h)^2+(y-k)^2=r^2, we want to find the two intersection point.

We plug in our calculator solve((x-h)^2 + (mx+b-k)^2=r^2, x)

This solves for x. Then we copy and paste.

Check which one is nearer with pythagorean.

Edge case is when there is vertical line or when fafa is out of the flat.

Anyone use calculator for D? (quick maths!)

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

can anyone please explain me why the line must passed through (x1, y1) and (x2, y2)?

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

can someone please explain the solution of F? In the editorial i didn't understand why we are considering only the case that (b <  = c). And "f neither case 1 nor case 3 exists, then we can only the second option of the previous case."

Please help me!

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

    Given two numbers b and c, it is always true that at least one of b ≤ c and c ≤ b will hold. Simply label b and c such that the first inequality holds. This is what "without loss of generality, assume b ≤ c" means.

    There are only three cases. If it is neither 1 nor 3, then it must be 2.

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

After reading about the dp approach, I still don't know how to do div2 E. Can somebody explain it in words? I know I'm ahead of myself though.

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

I have some questions for the solution for F:

What does the line mean by if case 1 doesn't exist, then there is at most one element for which case 3 holds (you can prove this by contradiction).

Can't we have something like two mountains?

   /\
  /  \
\/    \/

which will lead to two elements for which case 3 holds?

Also, what is meant by argmin_k? Does it mean the index for which the function of k is minimized?

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

    In this example, case 1 exists also. The statement says " if case 1 doesn't exist, then there is at most one element for which case 3 holds (you can prove this by contradiction)."

    Here is now I understand it. If there are two instances of case 3, then there are two low points. Between the two low points there must be a high point.

    argmin_k is the index when k is minimized because we are incrementing by 2·max(0, x - (ck - ak)) which is maximized when argmink{ck - ak} is minimized.

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

      Thank you very much.

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

        if you don't mind can u please explain F? I didn't understand the approach completely.

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

          I didn't try understanding the part about segtrees yet. Basically I don't know how it works either. I'm planning to look at it soon

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

            If you understand it then please explain it! It will be a great help for beginners like me :) Thanks a lot :)

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

Can someone please explain how do we calculate R such that R = P * Q - 1mod(109 + 7) and why top programmers (and may be others too) doing calculation involving mod — 2. For example 35484191 where does that 2 come from ?. what is the math behind all this ?

Thanks