Hello, Codeforces!
I'd like to invite you to Codeforces Round #465 (Div. 2) which takes place on Monday, 19 February 2018 at 19:35 MSK. The round will be rated for division 2 participants. However, as usual division 1 can take part out of competition.
The round is prepared by my friends Kammola, Ahmad_Elsagheer, MostafaAbdullah and me (AhmedSoliman). Besides, many thanks to 300iq, mike_live, Arpa, GreenGrape and FalseMirror for testing the round, KAN for coordinating the round and MikeMirzayanov for the great Codeforces and Polygon platforms.
You will be given 6 problems and 2 hours to solve them. The scoring distribution will be announced later. Good luck!
UPD1: Scoring is 500 — 750 — 1250 — 1750 — 2250 — 2750
UPD2: Congratulations to the winners!
Division 1 :
Division 2 :
UPD3: The Editorial is available now!
Thank you everyone!
a bit late for Chinese users.
Yes. It's late for me and I will fell a bit tired during this contest.
have to stay up late again :)
I slept for it at noon
It is raining contests!!!
5 rated contest in 6 day :))
and after this, 6 days without contests :))
and after this, there will be Codeforces Round #466(a rated contest) :))
and after this there will be the ladder of "after"'s
and after this what will happen? :P
after this or after after this comment, new reply thread won't be created anymore
For me, it was more like a storm, losing 224 points in 6 days! :D
So many writers/testers/coordinators for a div.2 contest! What I mean is that I do appreciate the effort put on this contest and do not mean anything in a negative way.
Once again, the purple problem setter.
CODEFORCES is on fire ..!!!
it's kind a contest storm !
Unfortunately, I misread the C problem, I passed 4 problems, but the score is very low, I did not have the chance to have the first time to make 5 problems T.T
It seems that I need more practice.
Look forward to the next contests
What's your approach for E?
......
It is time to crush it!
The Announcement is 8 days before the contest. Lets hope the scoring will be announced early like the announcement.
UPD: It wasn't in the main page
It's before 23 hours :P
GUC D:
3aaa4 GUC
Who is GUC? Where is GUC?
German University in Cairo
lots of math xD
Good luck
Codeforces is smashing , it is going wild , i think today or tomorrow there will be something named "contest overflow"...
Hope it will be a bit harder than the last one
Agree! Hope problem statements are not long or thick, but hard.
Hate geometry :(
More like Mathforces today.
One more task and this would have been a beautiful regular round with two divisions.
Yes, the problemset is so good.
Hackless Round!
Nonetheless, I hacked one solution in my room)
I think there has been some work on making problems more shitty than they were like in problem E
Try this test case
1 0 0 0 0It should output
0.5 0 0.5Actually the circle can be anywhere, but exactly 0.5 away from the origin.Any ideas for pretest 5?
"R, x1, y1, x2, y2 (1 ≤ R ≤ 105, |x1|, |y1|, |x2|, |y2| ≤ 105)"
The test case is invalid.
And mine printed "0 0.5 0.5"
So True! Someone knows what was the preset 4?
It seems that in the fourth pretest we get (x1,y1) = (x2,y2).
Something like 2 4 4 4 3.
anant_k_singh
killer_god Hahaha !!!
Geometry is tough
A lot of problem C gonna hack this contest
Note: Sorry for my bad english.
So, at Problem C the ideea is to find the radius of the biggest circle Which has the laptop point and doesn't exceed the flat Area. This is relative simple The radius is (R+sqrt((x1-x1)^2+(y2-y1)^2))/2; But.. How can I Find the center of this Circle? That is the question. :)
Required radius
The center will be the point at above calculated distance r in the direction of (x1, y1) from (x2, y2).
Let P1 = (x1, y1), P2 = (x2, y2) and
. Then center should be at 
.
Handle the P2 outside apartment and P1 = P2 cases separately.
Find distance from laptop to center of the given circle. That plus the radius will give the diameter of the circle you want. The center of this circle will be at the midpoint of this line, which you can find with a bit of trig or by using ratios
you can use some maths let center of flat to be (0, 0)
phi = atan2(y2, x2)
x3 = -R * cos phi y3 = -R * sin phi
(x2, y2) — (x3, y3) is diameter of circle you need.
how to solve c?
Someone can explain how to do the C problem? How can I maximize the area of the circle? My only thoughts was achieving this by some binary search...
My general ideas all surrounded something like that: if Fafa's laptop is outside or at some flat's end, then the answer is all flat's area. If not, then choose the center whose maximize the area. This is the right way to do?
you have a line which connects fefa and the room center. extend that line. find the point on the line which lies on the circumference call this P. your coordinates -> midpoint of P and fefa. radius is the distance b/w them — 0.000001~.
Even though I got hacked, I think I have the right idea.Let point a be centre and b be point where laptop is. The answer radius is obviously (r+dist(a,b))/2. You can also get distances from the center and the laptop, which are (r+dist(a+b))/2 and (r-dist(a,b))/2 respectively. Then you can apply external form of section formula to get the coordinates of the center.
Here is my approach.
First of all, if Fafa is on the border of the flat or outside of the flat, Fifa can place the access point at the center of the flat, and set the radius exactly equal to R.
If not, we can see that the biggest area will be something like this:
To obtain such an answer, at first we have to find the other vertex of the orange segment (one vertex is Fafa's laptop location). We can calculate that through geometric vectors.
After that, we can obtain the access point's location: it will be the midpoint of the orange segment. The radius will be half the length of that segment.
Well, more simple than i thought. I drew some drafts like yours but could not realize how to find the position of the second vertex. Thanks!
Can the boundary of our circle pass through fafa's location?
Yes. The 2nd sample test confirmed that ;)
With the input
10 5 5 5 15and the output5.0 5.0 10.0, we can see that:Therefore, the access point's boundary can pass through Fafa — and he still gets no coverage at all.
Ok cool,...I submitted and I was afraid about this case..
Same to me. I even had to use plotting program to make sure that it lied on the boundary, though it could be calculated algebraic-ly. :P
That feeling, when you are solved the problem C by binary and ternary search... http://codeforces.net/contest/935/submission/35499682
Fifa and Fafa? Really? What about Fofa? And Fafi? And...
Joke aside, it's usually better to have easy to differ names (e.g. Alice and Bob). Otherwise it can be really hard to follow the problem statement while remembering who is who.
Well, that is why it wasn't required to remember their names. :P
yeah, i get confused by C problem, because they have similar name.
Yeah, I was confused why doesn't he wants his own laptop to get the wifi. Weird fifa dude.
Does anyone know what test 6 D would look like?
wtf pretest 6 don t love me also 7 submission too badd
I have WA6 in D. I have forgotten put some code in else block, so when s1[i] = s2[i] = 0, my solution changed ans twice So i think there is such i that s1[i] = s2[i] = 0
Edit: nvm lol
Hi, how to solve E?
I have a solution if there has no constraint of P & M, that is: Greedily choose '+', but if expression satisfies |E1 — E2| > |E1 + E2| and it's not leftmost expression, choose '-', such that the answer is optimal.
But I have no idea about with constraint of P & M.
Use dynamic programming.
hi[i][j] is the maximum value of the ith expression with j pluses used within it
lo[i][j] is the minimum value of the ith expression with j pluses used within it
Transition states are relatively straightforward, but it is a bit tricky to implement the dp order correctly. Final complexity is O(E2).
thanks a lot!
can someone tell me why my approach for d is wrong https://ide.geeksforgeeks.org/TGNpoGcVTH
Dat test:
3 2
0 1 0
1 2 1
In first position you can write just 2. Then whatever what you write in third position. So real P / Q = 1 / 2 and ans is 5000000004 while your answer is 750000006
ohh god! fuck me!!! just forgot to include if(a[i] < b[i] && a[i] != 0) break;
Not sure if the approach is wrong or not but there is atleast a overflow.
There is no overlow since
oh god
The first what I saw is that in your power function long longs are missing (t*t can overflow).
Or throw his laptop against the wall. Problem solved!
I think the problems are sorted by how shitty they are but then I think about problem C and how awful it was to implement.
C wasn't particularly hard to implement for a geometry problem. There was only one extra case to take into consideration: (x1, y1) = (x2, y2). Other than that, the implementation was relatively clean.
The whole idea of geometry problems are shitty and awful
Apparently, Fafa's laptop can be outside the Flat too. Test case 3 shows this. This is another case I guess. Personally I felt the problem had incomplete information/ is misleading. Why say that Fifa and Fafa share a flat together when Fafa's laptop can be outside the flat?
The problem specifically states The flat is centered at (x1, y1) and has radius R and Fafa's laptop is located at (x2, y2), not necessarily inside the flat. Plus, there is that test case. There was absolutely no ambiguity.
I understood that. All I was saying is it was said Fafa and Fifa share a flat in the problem. Many people misunderstood this as Fafa always stays inside the room.
UPD : It is mentioned in problem that Fafa's laptop is not necessarily inside the flat. I guess I missed it.
I think some drawing would have made C easier to understand :\
Anyway, nice problem and problemset also, thanks :D
Spent half of my time minimizing the 'uncovered area' which not at all required. And like kirjuri said, assumed Fifa and Fafa as Fifa. Problems were good but statements could have been made better.
Wow, I'm impressed. The problems included some interesting Egyptian background, which I enjoyed. The last problem was tricky for me, and I spent much time thinking, fixing the code and analysing special cases. Personally, I had a great time. Thank you very much!
The problems were excellent.
We didn't perform well doesn't imply that the problems were bad.
Problems were of a good quality. Only I didn't like the naming convention of Fifa and Fafa :D
Can someone please tell me what's wrong with this solution to D : link?
in first else if it should be a[i] < b[i] in solve() I think?
Finding centre of the circle after finding the required radius can be done by the sector for external divison in problem C(handling corner cases differently)
For problem D:
P is number of valid changes, Q is the number of all changes. The result is P/Q mod MOD ...
How to calculate P/Q mod MOD ? I thought about modular multiplicative inverse but I couldn't implement it...
What exactly is M ?
M is the mod, which is 1000000007. Since M is a prime, φ(M) = M - 1.
So I should first calculate RES = Q^-1 your way and fast exponentiation and then print P*RES mod MOD ?
Yes, that's correct
But wait,if you do it that way, it means that the answer is going to be just Q^(mod-2) * P and it is not necessarry for those 2 to be co-prime. Then it won't work. For example for sample 3 the answer is 16*25*24*23 / 26*25*24*23 . So we need to find the modular inverse for 26*25*24*23 and multiply it by 16*25*24*23 and output it %(1e9+7). If i do that in the 3 sample i get the wrong answer. We need an ireductible fraction, so how to get it?
After getting P and Q divide them with gcd
How to divide P and Q by GCD if they, while being calculated, will be % mod because during the calculation there will be for sure values bigger then 10^18. So applying gcd so make it ireductible just doesn't make sense.
We don't actually need to divide by gcd because of how mod works.
and that is unique
So what you're saying is that just by calculating the answer randomly and getting P%mod and Q%mod, then calculating Q^(mod-2) and multiplying by P we get the correct answer??
You don't even need to maintain p and q separately, just multiply by the inverse element every time you need a division.
sh** you are so right, thank u very much.
ll realMod(ll num, ll denom, ll MOD){ for(int i = 0; ; i++){ if((num + MOD*i) % denom == 0){ return (num + MOD*i) / denom; } } }
P/Q mod MOD means we're looking at P*x mod MOD where x is the modular inverse of Q mod MOD, which means that Q*x mod MOD = 1. So, Find the modular inverse MI for Q mod MOD. P*=MI; ans=P%MOD;
It doesn't work if you do that for the third sample, we need an ireductible fraction before we do the modular inverse thing, so p and q must be co-prime before applying modular inverse to Q.
Another way to calculate it is to use the Extended Euclidean Algorithm, that is given a and b, find integers x and y such that ax + by = 1. If we set a = Q and b = M, then 1 = Qx + My = Qx (mod M), so x = Q^{-1} (mod M)
Can someone say if this method for problem E would work?
lets say we process expressions in decreasing order of nesting.Dp[i][2] denotes the maximum and minimum value of that expression.So now we can make transition easily to lower nesting .
Sorry if this question is too naive.
Problem C using ratio and proportions
UPDATE (It is Correct)
There is nothing wrong with this solution. It is actually correct. As people below pointed out I didn't check for integer overflow and printed wrong variables. After I fixed that I got AC
SOLUTION : http://codeforces.net/contest/935/submission/35502661
What if dist is 0?
I took care of the 2 other special cases
CASE 1 : dist = 0
CASE 2 : dist > R
Link to Full Code here : https://github.com/DollarAkshay/Competitive-Coding/blob/master/CodeForces/CodeForces_Fifa_and_Fafa.cpp
Looks like overflow at line 50.
Overflow ((x1 — x2) * (x1 — x2)). x1 and x2 both int. So (x1 — x2) * (x1 — x2) will be int. Bu Since |x| <= 10^5 -> (x1 — x2) ^ 2 <= 4 * 10^10 which doesn't fit in int-type.
So my approach is correct but I dint check overflow ? :/
God DAMN it. I will have to check after the contest ends
When dist>R, you printed x1 and x2 instead of x1 and y1.
Классный раунд, спасибо авторам!
Can someone please point out what is wrong with my code for C? http://codeforces.net/contest/935/submission/35496680
Shouldnt this
if((dist+r<=R))be 2*R in the lastifwhich do not have matching else?Edit: it passed with 2*R at both places
Thanks for your reply! But No, I think the condition was right (condition for a circle to be inside another circle), I found the mistake ,it should have been. if((dist+r-R)<=0.000001) It passed with this.
Ah the epsilon. Cool.
Solved the first two problems as fast as I could.Then saw FIFA my eyes lit up :) but it took forever to actually get it AC.
The radius is the same as in the correct answer, why is it WA?
WA because wi-fi would be accessed from point (-5 -10) which is outside appartment.
This is how it looks
Link to Online Graph : https://www.desmos.com/calculator/b7at4hbbxb
Could someone explain how to do D?
Let P(x) be the probability that a[i] = b[i] for i < x and a[x] > b[x]. Then the answer is
because probabilities. To find 
, we observe that 
, so we can just compute numerator and denominator mod M at each step.
https://ide.geeksforgeeks.org/g335Ycicx1 can you tell me what the problem in my solution i just use your idea
Sadly my incorrect F passed systests. I incorrectly thought that the minimum difference would just subtract -1*diff instead of -2*diff during the contest and when the ranges are small I just passed through the whole range to get the best answer.
30
1000 990 980 970 960 950 940 930 920 910 900 890 880 870 869 870 880 890 900 910 920 930 940 950 960 970 980 990 1000 1010
1 1 2 29 1000
This case breaks my solution (it prints 2269 instead of 2268, it should choose the 869). http://codeforces.net/contest/935/submission/35492061 this is the wrong submission. This is a small mistake from me that usually wouldn't happen to anyone but I hope that the tests didn't impact any rating (the implication of this is that there's no big query where it's better to get an i where a[i — 1] > a[i] and a[i + 1] > a[i]).
Can some one please tell me what is wrong with my solution the radius i am getting in the test case 14 is correct but the checker comment reads "wrong answer Too large radius." link
You should output more digits after the decimal point for the x and y values, my guess is that there is some point on your circle that is outside the given circle by more than 1e-6.
just print more digits after the decimal point. e.g
cout << fixed << setprecision(10) << x << endl;Thanks bro after changing it to
cout << fixed << setprecision(9) << x << endlit got accepted but in my previous submission i wrotecout<<setprecision(9)in the beginning. Are these two ways of setting precision to 9 two different things?? BTW Thanks for the help.The
fixedspecifies that you want the specified precision to be applied only after decimal point. without it, it'd just output a total of 9 digits, the first 9 from the left, regardless of whether the digit is after or before the decimal point.Oh now i get it.Thanks
I got confused by Fifa Fafa Fafa Fifa Fafa Fifa Fifa Fafa
Can you please suggest what is wrong with this solution for problem D: https://ide.geeksforgeeks.org/el12hkWIU0 ?
when you did this:
if (!a[i] && !b[i]) r = (m * solve(a, b, i+1) + m*(m-1)/2) % MOD;the denominator should change to
m*mbut at the end you are still dividing by m only.Indeed, thank you!
Hi, I submited a code (35493900) in the contest for problem c and it gave Idleness limit exceeded!!! but after the contest I submited the same code (35503114) and it was accepted!!! I was wondering if you could fix this problem and fix my score !!!!!!!!!!!
Fixed. AC already.
I got the message below after competing in this round. I did not cheat or attempt to cheat during the contest. Furthermore, I worked locally on my own computer. Could you please take a look at this issue? The odds of submitting a very similar code for a div 2 A problem are rather high. Thanks!
Attention!
Your solution 35483271 for the problem 935A significantly coincides with solutions HSNBRG/35477249, wertzu/35483271. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.net/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties.
It's a good idea to tag MikeMirzayanov to get his attention.
Random observation regarding test data in problem F:
solution which says "OK, in case there is local maximum — let's pick it, otherwise let's check all possible moves in O(N) per query" passes easily without any additional tricks or optimizations. 35497796 is an example (obfuscated though, since it was originally an attempt to code correct solution).
http://codeforces.net/blog/entry/57702?#comment-415778 so far it's been at least 2 solutions affected by this :|
In your solution you at least say "when the ranges are small". Mine is simply "screw it, YOLO, let's try them all" :)
On an unrelated note: while my solution to E from the contest failed because I forgot to check if P>100, solution in upsolving passes with wrong check containing < instead of <=. It isn't going to work well for a case with P>100, M=100.
awesome C :)
really?
I think I can get up,but...
A bit late for coach Marcil!
F problem. I think we should add such data.
52 3 1 1 152 5 5 22 3 4 31 4 4 11 3 5 21 1 1 1Can someone please tell me what's wrong with the following approach for problem D? :
For each
i, I find the number of ways that all the letters uptoi - 1are the same, anda[i] > b[i].Then, the number of ways for each index is
p = x * pow(m, unknown[i + 1])where x is the number of possibilities of a[i] > b[i], with different possible conditions, andunknown[i + 1]is the count of erased numbers in either a or b, fromi + 1, to the end.Also, I multiply to p,
pow(m, bothZeroes), where bothZeroes is the number of indices up toi - 1, at whicha[i] = b[i] = 0, because any 1 of the m numbers could be chosen for such indices.But, I looked into this code, and he hasn't multiplied the
pow(m, bothZeroes)part to his answer. What's wrong with my approach, and how come them^bothZeroespart isn't required?Link to solution.
Will be glad if someone could help. Thanks in advance.
Edit : p is not the probability, it's the numerator part.
why fifa and fafa ???? can't you use good names ??? i got confused while reading the statement , fifa.. fafa.... fafa... fifa.... what the hell