Codeforces Round #465 (Div. 2)

7 years ago, # ^ |

← Rev. 2 →

CodeForces Meme

→ Reply

Adhami

7 years ago, # |

← Rev. 2 →

-39

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

→ Reply

Hasan

7 years ago, # ^ |

It's before 23 hours :P

→ Reply

Smara

7 years ago, # |

+37

GUC D:

→ Reply

Mo2men

7 years ago, # ^ |

+16

3aaa4 GUC

→ Reply

NursuItanTolshybek

7 years ago, # ^ |

+12

Who is GUC? Where is GUC?

→ Reply

Mo2men

7 years ago, # ^ |

+16

German University in Cairo

→ Reply

Mr.AAA

7 years ago, # ^ |

lots of math xD

→ Reply

Uzumaki_Narutoo

7 years ago, # |

Good luck

→ Reply

Ahnaf.Shahriar.Asif

7 years ago, # |

+20

Codeforces is smashing , it is going wild , i think today or tomorrow there will be something named "contest overflow"...

→ Reply

DP_I_J

7 years ago, # |

+16

Hope it will be a bit harder than the last one

→ Reply

brdy

7 years ago, # ^ |

-19

Agree! Hope problem statements are not long or thick, but hard.

→ Reply

Elibay

7 years ago, # |

+74

→ Reply

noobied

7 years ago, # |

+44

Hate geometry :(

→ Reply

Linkus

7 years ago, # |

+73

More like Mathforces today.

→ Reply

P_Nyagolov

7 years ago, # |

+81

One more task and this would have been a beautiful regular round with two divisions.

→ Reply

7 years ago, # ^ |

+15

Yes, the problemset is so good.

→ Reply

Ehsan_sShuvo

7 years ago, # |

+27

Hackless Round!

→ Reply

bonzai

7 years ago, # ^ |

Nonetheless, I hacked one solution in my room)

→ Reply

7 years ago, # |

-6

I think there has been some work on making problems more shitty than they were like in problem E

→ Reply

heck

7 years ago, # |

+135

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Try this test case 1 0 0 0 0

It should output 0.5 0 0.5 Actually the circle can be anywhere, but exactly 0.5 away from the origin.

→ Reply

Stochastic

7 years ago, # ^ |

Any ideas for pretest 5?

→ Reply

brdy

7 years ago, # ^ |

← Rev. 3 →

-18

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

→ Reply

JoaquinManuel

7 years ago, # ^ |

So True! Someone knows what was the preset 4?

→ Reply

mikroz

7 years ago, # ^ |

← Rev. 2 →

+10

It seems that in the fourth pretest we get (x1,y1) = (x2,y2).

→ Reply

Vsevolod_Kaplin

7 years ago, # ^ |

Something like 2 4 4 4 3.

→ Reply

killer_god

7 years ago, # ^ |

anant_k_singh

→ Reply

anant_k_singh

7 years ago, # ^ |

killer_god Hahaha !!!

→ Reply

Strategist

7 years ago, # ^ |

← Rev. 2 →

Geometry is tough

→ Reply

Ali_Adelkhah

7 years ago, # |

← Rev. 2 →

A lot of problem C gonna hack this contest

→ Reply

AlexandruOlteanu2017

7 years ago, # |

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

→ Reply

meooow

7 years ago, # ^ |

← Rev. 4 →

Required radius $\text{[math]}$

The center will be the point at above calculated distance r in the direction of (x₁, y₁) from (x₂, y₂).

Let P₁ = (x₁, y₁), P₂ = (x₂, y₂) and $\text{[math]}$ . Then center should be at $\text{[math]}$ .

Handle the P₂ outside apartment and P₁ = P₂ cases separately.

→ Reply

WolfBlue

7 years ago, # ^ |

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

→ Reply

BagishovMikail

7 years ago, # ^ |

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.

→ Reply

pk842

7 years ago, # |

how to solve c?

→ Reply

joaquimnt_

7 years ago, # |

← Rev. 2 →

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?

→ Reply

.st

7 years ago, # ^ |

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

→ Reply

madhav_1999

7 years ago, # ^ |

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.

→ Reply

AkiLotus

7 years ago, # ^ |

+16

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.

→ Reply

joaquimnt_

7 years ago, # ^ |

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!

→ Reply

ruskinmanku

7 years ago, # ^ |

Can the boundary of our circle pass through fafa's location?

→ Reply

AkiLotus

7 years ago, # ^ |

Yes. The 2nd sample test confirmed that ;)

With the input 10 5 5 5 15 and the output 5.0 5.0 10.0, we can see that:

Fafa's laptop is right on the boundary (its distance to the center is 10, which is equal to the flat's radius).
The flat's circle and the correct access point's circle are equivalent.

Therefore, the access point's boundary can pass through Fafa — and he still gets no coverage at all.

→ Reply

ruskinmanku

7 years ago, # ^ |

Ok cool,...I submitted and I was afraid about this case..

→ Reply

AkiLotus

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

Rotcod

7 years ago, # ^ |

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

→ Reply

kirjuri

7 years ago, # |

+122

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.

→ Reply

ilovekidneystone

7 years ago, # ^ |

Well, that is why it wasn't required to remember their names. :P

→ Reply

..vince

7 years ago, # ^ |

yeah, i get confused by C problem, because they have similar name.

→ Reply

7 years ago, # ^ |

Yeah, I was confused why doesn't he wants his own laptop to get the wifi. Weird fifa dude.

→ Reply

Thaid

7 years ago, # |

Does anyone know what test 6 D would look like?

→ Reply

Notali.haidar

7 years ago, # ^ |

wtf pretest 6 don t love me also 7 submission too badd

→ Reply

BagishovMikail

7 years ago, # ^ |

← Rev. 2 →

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

→ Reply

tfg

7 years ago, # ^ |

← Rev. 2 →

Edit: nvm lol

→ Reply

fateyan

7 years ago, # |

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.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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(E²).

→ Reply

fateyan

7 years ago, # ^ |

thanks a lot!

→ Reply

newbie_forever_at_cp

7 years ago, # |

can someone tell me why my approach for d is wrong https://ide.geeksforgeeks.org/TGNpoGcVTH

→ Reply

7 years ago, # ^ |

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

→ Reply

newbie_forever_at_cp

7 years ago, # ^ |

← Rev. 2 →

-6

ohh god! fuck me!!! just forgot to include if(a[i] < b[i] && a[i] != 0) break;

→ Reply

7 years ago, # ^ |

Not sure if the approach is wrong or not but there is atleast a overflow.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

There is no overlow since

#define int long long

→ Reply

7 years ago, # ^ |

+10

oh god

→ Reply

Thaid

7 years ago, # ^ |

The first what I saw is that in your power function long longs are missing (t*t can overflow).

→ Reply

Gigibyte

7 years ago, # |

+76

→ Reply

joaquimnt_

7 years ago, # ^ |

+19

Or throw his laptop against the wall. Problem solved!

→ Reply

7 years ago, # |

-72

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.

→ Reply

7 years ago, # ^ |

+31

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.

→ Reply

7 years ago, # ^ |

-68

The whole idea of geometry problems are shitty and awful

→ Reply

rajiv

7 years ago, # ^ |

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?

→ Reply

WolfBlue

7 years ago, # ^ |

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.

→ Reply

rajiv

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

C137

7 years ago, # |

+12

I think some drawing would have made C easier to understand :\

Anyway, nice problem and problemset also, thanks :D

→ Reply

dush1729

7 years ago, # |

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.

→ Reply

KrK

7 years ago, # |

+87

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!

→ Reply

7 years ago, # |

-126

→ Reply

Omar_Morsi

7 years ago, # ^ |

+67

The problems were excellent.

We didn't perform well doesn't imply that the problems were bad.

→ Reply

7 years ago, # ^ |

Problems were of a good quality. Only I didn't like the naming convention of Fifa and Fafa :D

→ Reply

rahulkhairwar

7 years ago, # |

Can someone please tell me what's wrong with this solution to D : link?

→ Reply

kingside

7 years ago, # ^ |

in first else if it should be a[i] < b[i] in solve() I think?

→ Reply

kingside

7 years ago, # |

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)

→ Reply

7 years ago, # |

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

→ Reply

7 years ago, # ^ |

← Rev. 3 →

+11

$\text{[math]}$

→ Reply

7 years ago, # ^ |

What exactly is M ?

→ Reply

7 years ago, # ^ |

← Rev. 3 →

M is the mod, which is 1000000007. Since M is a prime, φ(M) = M - 1.

→ Reply

7 years ago, # ^ |

So I should first calculate RES = Q^-1 your way and fast exponentiation and then print P*RES mod MOD ?

→ Reply

7 years ago, # ^ |

Yes, that's correct

→ Reply

7 years ago, # ^ |

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?

→ Reply

7 years ago, # ^ |

After getting P and Q divide them with gcd

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

← Rev. 3 →

We don't actually need to divide by gcd because of how mod works.

$\text{[math]}$

and that is unique

→ Reply

7 years ago, # ^ |

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

→ Reply

dalex

7 years ago, # ^ |

You don't even need to maintain p and q separately, just multiply by the inverse element every time you need a division.

→ Reply

7 years ago, # ^ |

sh** you are so right, thank u very much.

→ Reply

michaelw12

7 years ago, # ^ |

ll realMod(ll num, ll denom, ll MOD){ for(int i = 0; ; i++){ if((num + MOD*i) % denom == 0){ return (num + MOD*i) / denom; } } }

→ Reply

nazmulasha

7 years ago, # ^ |

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;

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

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)

→ Reply

rachitiitr

7 years ago, # |

+155

→ Reply

Vivek1998299

7 years ago, # |

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.

→ Reply

7 years ago, # |

← Rev. 7 →

+19

Problem C using ratio and proportions

Question

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

→ Reply

Vivek1998299

7 years ago, # ^ |

What if dist is 0?

→ Reply

7 years ago, # ^ |

← Rev. 3 →

I took care of the 2 other special cases

CASE 1 : dist = 0

r = R / 2
xap = x1 + r
yap = y1
print(xap, yap, r)

CASE 2 : dist > R

print(x1, y1, R)

Link to Full Code here : https://github.com/DollarAkshay/Competitive-Coding/blob/master/CodeForces/CodeForces_Fifa_and_Fafa.cpp

→ Reply

7 years ago, # ^ |

Looks like overflow at line 50.

→ Reply

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

So my approach is correct but I dint check overflow ? :/

God DAMN it. I will have to check after the contest ends

→ Reply

FieryPhoenix

7 years ago, # ^ |

+16

When dist>R, you printed x1 and x2 instead of x1 and y1.

→ Reply

7 years ago, # ^ |

+26

→ Reply

SarthakGoel

7 years ago, # |

Can someone please point out what is wrong with my code for C? http://codeforces.me/contest/935/submission/35496680

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Shouldnt this if((dist+r<=R)) be 2*R in the last if which do not have matching else?

Edit: it passed with 2*R at both places

→ Reply

SarthakGoel

7 years ago, # ^ |

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.

→ Reply

7 years ago, # ^ |

Ah the epsilon. Cool.

→ Reply

fastboot

7 years ago, # |

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.

→ Reply

Rudy1444

7 years ago, # |

The radius is the same as in the correct answer, why is it WA?

→ Reply

7 years ago, # ^ |

WA because wi-fi would be accessed from point (-5 -10) which is outside appartment.

→ Reply

7 years ago, # ^ |

This is how it looks

Link to Online Graph : https://www.desmos.com/calculator/b7at4hbbxb

→ Reply

silxi

7 years ago, # |

Could someone explain how to do D?

→ Reply

7 years ago, # ^ |

← Rev. 2 →

Let P(x) be the probability that a[i] = b[i] for i < x and a[x] > b[x]. Then the answer is $\text{[math]}$ because probabilities. To find $\text{[math]}$ , we observe that $\text{[math]}$ , so we can just compute numerator and denominator mod M at each step.

→ Reply

Notali.haidar

7 years ago, # ^ |

https://ide.geeksforgeeks.org/g335Ycicx1 can you tell me what the problem in my solution i just use your idea

→ Reply

tfg

7 years ago, # |

+15

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.

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.me/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]).

→ Reply

Udit_Maniyar

7 years ago, # |

← Rev. 2 →

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

→ Reply

7 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

7 years ago, # ^ |

just print more digits after the decimal point. e.gcout << fixed << setprecision(10) << x << endl;

→ Reply

Udit_Maniyar

7 years ago, # ^ |

Thanks bro after changing it to cout << fixed << setprecision(9) << x << endl it got accepted but in my previous submission i wrote cout<<setprecision(9) in the beginning. Are these two ways of setting precision to 9 two different things?? BTW Thanks for the help.

→ Reply

7 years ago, # ^ |

← Rev. 2 →

The fixed specifies 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.

→ Reply

Udit_Maniyar

7 years ago, # ^ |

Oh now i get it.Thanks

→ Reply

DonMichaelCorleone

7 years ago, # |

I got confused by Fifa Fafa Fafa Fifa Fafa Fifa Fifa Fafa

→ Reply

mikroz

7 years ago, # |

Can you please suggest what is wrong with this solution for problem D: https://ide.geeksforgeeks.org/el12hkWIU0 ?

→ Reply

7 years ago, # ^ |

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*m but at the end you are still dividing by m only.

→ Reply

mikroz

7 years ago, # ^ |

Indeed, thank you!

→ Reply

patak

7 years ago, # |

← Rev. 3 →

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

→ Reply