Kammola's blog

[Editorial] Codeforces Round #465 (Div. 2)
By Kammola, history, 7 years ago, In English

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...
  • Vote: I like it
  • +125
  • Vote: I do not like it

Comments Comments (88)
| Write comment?
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

    You'll learn geometry bro xDD

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

    can you please explain your approach.

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

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

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

      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.

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

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

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

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?

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

    You should use long double I think

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

      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 .

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    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

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

      Indeed. Should have had it solved on paper before coding.

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

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?

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

    You should note that

    if x is not a multiple of 109 + 7.

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

      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?

      → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +21 Vote: I do not like it
Problem C

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

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

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

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

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

      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
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

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

          Yes exactly. Unit vector sets our direction correct.

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

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

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

      Idea of similar triangles.

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      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.

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

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 8   Vote: I like it +15 Vote: I do not like it

    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

    → Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +30 Vote: I do not like it

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.

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

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

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

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

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

    I got that the profit was

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

    How did you convert this to your expressions?

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

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

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

    Try GeoGebra :)

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

    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.

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

    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.

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

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

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

    We can convert them to point updates because something in middle of range wont get effected by update

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

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    a·b - 1 + c·d - 1 ≡ (ad + bc)·(bd) - 1

    can be verified via expansion.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      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

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

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

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

Can you explain the last formula in problem D?

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

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

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

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

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

        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.

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

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."

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

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.

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

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

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

      Kindly share an understandable implementation of the model solution.

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

        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://mirror.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

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

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

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

          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.

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

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

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

    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.

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

      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.

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

        Thanks a lot for your nice explanation. Now everything is clear to me about your elegant approach.

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

    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?

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

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

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

        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

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

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?

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

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

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

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

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

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

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

    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.

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

"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"

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

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

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

    I explained it in reply to ghoshsai5000's comment above

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

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

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

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

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

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

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

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 ?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it -10 Vote: I do not like it

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

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

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

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

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!

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

    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.

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

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.

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

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?

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

    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.

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

      Thank you very much.

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

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

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

          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

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

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

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

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

→ Reply