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...
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3823 |
3 | Benq | 3738 |
4 | Radewoosh | 3633 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3390 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
Hello Codeforces,
I hope you liked the problems! Below you can find the tutorials for all problems.
Название |
---|
That feeling, when you are solved the problem C by binary and ternary search... http://codeforces.me/contest/935/submission/35499682
You'll learn geometry bro xDD
can you please explain your approach.
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 :)
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.
In problem C why am I getting WA on test 13 ? I used Binary search like algorithm ..My solution
Why for Problem C test
10 0 0 0 0
and with my output5.0000000000000000 5.0000000000000000 4.9999991000000001
it iswrong answer Too large radius.
? The Y coordinate of the top point of the embed circle is9.999999
and the Y of the bottom point is0.0000001
, so it should fit in and not touch the laptop. Where I'm wrong?You should use long double I think
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 .
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
Indeed. Should have had it solved on paper before coding.
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?
You should note that
if x is not a multiple of 109 + 7.
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?
inv and mpow(m, mod-2) are not interchangeable.
Accepted Solution
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 :)
Problem C
Easier way of finding
Xap, Yap
, if the point is inside circle (Using ratio and proportions)Link to Code : http://codeforces.me/contest/935/submission/35502661
Thank you so much for this explanation! I couldn't get why everybody is using this formula! Thanks a lot one more time.
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
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?
Yes exactly. Unit vector sets our direction correct.
it's intuitive, but can you prove that this proportion works?
Idea of similar triangles.
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.
Now, we need to find the coordinates (Xap, Yap).
Since we are trying to solve for Xap and Yap, we observe that:
We can solve for Yap similarly. Sorry in advance if my post is poorly formatted.
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?
The easy way to implement geometry is with complex numbers or a custom Point class. Something like this should work (code in cpp).
EDIT: The original code was untested and full of bugs, sorry
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.
Actually, the other solution of the authors is very similar to this one. Thanks for the comment!
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)?
I got that the profit was
How did you convert this to your expressions?
Does anyone know abt any online visualizer for geometry problems? like ploting circle and even any conics
Try GeoGebra :)
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.
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.
In problem F, should we use lazy propagation for updating the range in segment tree?
We can convert them to point updates because something in middle of range wont get effected by update
Got it, thanks.
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?
can be verified via expansion.
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
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
Use complex numbers and re-scale the vector PC.
Can you explain the last formula in problem D?
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).
Can you explain, why the next term isn't P(i+1)/(m2) ?
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.
Got it, thanks.
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."
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.
The editorial presents ONE solution to E, that is tree DP. ie you memoize your states as you traverse the tree.
Kindly share an understandable implementation of the model solution.
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
anddp_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]}
wherei = 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, sodp_max[v][c] = max{dp_max[left][i] + dp_min[right][c-i]}
wherei = 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.me/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
can you explain your approach for building the tree please ? ehnryx
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.
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.)
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.
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.
Thanks a lot for your nice explanation. Now everything is clear to me about your elegant approach.
Thank you so much :)
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?
According to Fermat's Little Theorem,
x^(p - 1) = 1 (mod p)
, if p is prime andgcd(x, p) = 1
x . x^(p - 2) = 1 (mod p)
`This means
x^(-1) = x^(p — 2)`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
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?
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! :)
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)).
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] ?
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.
"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"
can someone explain dp part of prob. E i cant figure it out. thanks!!
I explained it in reply to ghoshsai5000's comment above
"Fifa and Fafa are sharing a flat."
Should not Fafa's position be within the flat circle? (-_-)
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
Why am I getting WA on test 8 in problem C? This is my solution - http://codeforces.me/contest/935/submission/35524655
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 ?
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!)
can anyone please explain me why the line must passed through (x1, y1) and (x2, y2)?
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!
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.
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.
it may help : https://www.youtube.com/watch?v=PgvJbi2cJSw
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?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 by2·max(0, x - (ck - ak))
which is maximized whenargmink{ck - ak}
is minimized.Thank you very much.
if you don't mind can u please explain F? I didn't understand the approach completely.
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
If you understand it then please explain it! It will be a great help for beginners like me :) Thanks a lot :)
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
https://en.m.wikipedia.org/wiki/Euler%27s_theorem