[Editorial] Codeforces Round #465 (Div. 2)

7 years ago, # ^ |

can you please explain your approach.

→ Reply

MarcosK

7 years ago, # ^ |

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

Fullmetal_Algorithmist

7 years ago, # ^ |

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

vaibhav1997

7 years ago, # |

← Rev. 2 →

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

→ Reply

Vshining

7 years ago, # |

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

ankitraj

7 years ago, # ^ |

You should use long double I think

→ Reply

saquib2508

7 years ago, # ^ |

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

timfame

7 years ago, # ^ |

← Rev. 2 →

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

Vshining

7 years ago, # ^ |

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

→ Reply

AFN

7 years ago, # |

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

→ Reply

Benq

7 years ago, # ^ |

You should note that

$\text{[math]}$

if x is not a multiple of 10⁹ + 7.

→ Reply

rachitiitr

7 years ago, # ^ |

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

Benq

7 years ago, # ^ |

inv and mpow(m, mod-2) are not interchangeable.

Accepted Solution

→ Reply

divakar_tomar

7 years ago, # ^ |

← Rev. 2 →

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

DollarAkshay

7 years ago, # |

← 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.net/contest/935/submission/35502661

→ Reply

Bch

7 years ago, # ^ |

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

→ Reply

nshul

7 years ago, # ^ |

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

suraj021

7 years ago, # ^ |

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

nshul

7 years ago, # ^ |

Yes exactly. Unit vector sets our direction correct.

→ Reply

Shudi

7 years ago, # ^ |

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

→ Reply

iShibly

7 years ago, # ^ |

Idea of similar triangles.

→ Reply

_boosted

7 years ago, # ^ |

← Rev. 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.

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

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

Consider triangles ABE and CBD.
Angles AEB and CDB are congruent — both are right angles.
Angles ABE and CBD are congruent — they are the same angle.
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:

BD/BC = BE/AB
BC = S, BD = (Xap — X2), BE = (X1 — X2)
(Xap — X2)/S = (X1 — X2)/AB
Xap = S * (X1 — X2)/AB + X2

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

→ Reply

Sinhov

7 years ago, # |

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 →

+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

→ Reply

quailty

7 years ago, # |

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

→ Reply

Ahmad_Elsagheer

7 years ago, # ^ |

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

→ Reply

Stetsyk

7 years ago, # ^ |

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

WhaleVomit

7 years ago, # ^ |

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

diagon_alley

7 years ago, # |

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

→ Reply

quailty

7 years ago, # ^ |

+19

Try GeoGebra :)

→ Reply

awoo

7 years ago, # ^ |

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

AFN

7 years ago, # ^ |

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

Alireza

7 years ago, # |

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

→ Reply

teja349

7 years ago, # ^ |

+11

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

→ Reply

Alireza

7 years ago, # ^ |

Got it, thanks.

→ Reply

AkiLotus

7 years ago, # |

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

Benq

7 years ago, # ^ |

+10

a·b^- 1 + c·d^- 1 ≡ (ad + bc)·(bd)^- 1

can be verified via expansion.

→ Reply

AkiLotus

7 years ago, # ^ |

← Rev. 2 →

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

DaysGone

7 years ago, # |

← Rev. 2 →

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, # ^ |

← Rev. 2 →

Use complex numbers and re-scale the vector PC.

$\text{[math]}$

→ Reply

Melekh

7 years ago, # |

Can you explain the last formula in problem D?

→ Reply

rachitiitr

7 years ago, # ^ |

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

karanbatra

7 years ago, # ^ |

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

→ Reply

rachitiitr

7 years ago, # ^ |

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

karanbatra

7 years ago, # ^ |

Got it, thanks.

→ Reply

Kerim.K

7 years ago, # |

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, # |

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, # ^ |

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, # ^ |

Kindly share an understandable implementation of the model solution.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

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.net/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

XR_Maala

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

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, # |

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

anamibnaharun

7 years ago, # ^ |

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, # ^ |

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

anamibnaharun

7 years ago, # ^ |

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

→ Reply

7 years ago, # ^ |

Thank you so much :)

→ Reply

ninoa

7 years ago, # ^ |

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, # ^ |

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

parth_15

7 years ago, # ^ |

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

noob__coder

7 years ago, # |

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

MarcosK

7 years ago, # ^ |

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

djq_cpp

7 years ago, # |

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:

the x-coordinate of the optimal choice is not greater than -x (or it's not less than 0): just maximize the y-coordinate.
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

Shudi

7 years ago, # |

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

Medo.

7 years ago, # ^ |

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

BaturaDima

7 years ago, # |

"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

GodKira

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

I explained it in reply to ghoshsai5000's comment above

→ Reply

XzzF

7 years ago, # |

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

→ Reply

PetarMihalj

7 years ago, # |

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

lowjack

7 years ago, # |

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

→ Reply

SevenDeadlySins

7 years ago, # |

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

brdy

7 years ago, # |

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

→ Reply

7 years ago, # |

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

→ Reply

7 years ago, # |

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, # ^ |

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

mello

7 years ago, # |

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, # ^ |

it may help : https://www.youtube.com/watch?v=PgvJbi2cJSw

→ Reply

farmersrice

7 years ago, # |

← Rev. 3 →

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

Updown

7 years ago, # ^ |

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

farmersrice

7 years ago, # ^ |

Thank you very much.

→ Reply

7 years ago, # ^ |

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

→ Reply

farmersrice

7 years ago, # ^ |

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