Why not

that problem C was really weird

Welp, at least not an EPIC fail like last time!

Perhaps le0n is more like a cat irl.

I appreciate you telling me that in a comprehensive manner. Thank you BaoCoder613

We're both mad man then, let's do it.

Situation is tensed in Belarus

maybe that's why

F*ck me, I was stupid. In fact if I got it right, that could be implemented much more simple even, not requiring a Fenwick tree.

Thank you.

oh man... thanks. Too late to notice my naive-ness

i did'nt undersatnd why it gives WA when we use sqrt((x2-x1)^2 + (y2-y1)^2))...

but it got accepted when i removed sqrt

I tried but couldn't implement it properly (WA on 2), you can see my submission.

this is a bit over complicated

This is great, thanks!

Thanks!

Actually I was about to give up after seeing thousands of people got accepted in C, before trying to ignore my despair about that and continue.

nop i am not, if you will take a quick look at people in the leaderboard , you will find a staggering lot CMs, IMs skipping D1,D2 and going for E. While there a HELL LOT and yeah i mean a LOTTT of pupils and specialists solving D1 who are not alt accounts, and guess whats the common factor? They started submitting D1 after 1:35 hr and then submitted D2 wihtin a span of 1-5 mins .

i mean i agree to that i dont know fenwicks :) , but 2.6k people with a lot of pupils and specialists like come on most of them dont know fenwick.

I have seen a lot of shitty very obvious cheaters from IIT KGP on this contest too. Like on one hand there is a demon like Dominater069 and then there are these cheaters from a same , and I believe prestigious college, I mean I even don't care that much about my rating but the thing is this mass cheating thing is just getting sader and sader :)

E was waaaaay more intuitive for me than C.

In C I thought we shoud take colinear vector and for each point check if distance from intersection to circle center is less than distance to start point.

E has a simple stack solution (you can check my sub: 275826831)

In a way, I can see their sentiment on E < C. E actually required less "thinking" to come up with the idea, like the solution is straight-up simulating the given process in a careful way — at least the catch is partially within what's given. For C, it's more covert.

I think the hard part is to convince yourself that this works and not the implementation difficulty...

My way of convincing is that if you can't go to the end point through a straight line and instead you bump into a circle, you can't go to the end point through a curve without bumping as well

Bob can only win if he manage to delete the same element which is deleted by Alice in each operation, and this is only possible when b == a or b == reverse(a).

Lets say that we have a = {1,2,3} and b = {2,3,1}. In this case if alice chooses to remove 3 bob will have to remove a number that is not 3, since his 3 is not on the edge of the array. Now alice can just remove everything except for what bob removed on his first move like this:

a = {1,2} b = {2,3} // At this point alice can just not remove the 1. If she doesnt remove it bob wont have it and she will win.
a = {1} b = {2}

What we noticed is that bob will always want to remove the same number as alice since if he doesn't he looses. Knowing this bob will win if he at all points has the same numbers that he can remove as alice. So we will just check if a = b or if REVERSE(a) = b since in that case they still have the same options every turn.

int n;
		cin >> n;
		vector<point> l(n);
		for (int i = 0; i < n; i++) {
			cin >> l[i].x >> l[i].y;
		}
		point start;
		cin >> start.x >> start.y;
		point finish;
		cin >> finish.x >> finish.y;
		
		double ans = true;
		for (int i = 0; i < n; i++) {
			if (dist(finish - start) >= dist(l[i] - finish)) {
				ans = false;
			}
			
 
		}

Can't prove it. Just guessed it is something simple considering how many people solved it. Distance solution was kinda reasonable so I tried it.

I did some haphazard proof on pen and paper that first it's always optimal to take a straight line between start and end points. Then I started doing some perpendicular distance stuff and then I checked using Pythagoras theorem and found that if a circle will intersect the straight path at some time "t" before you reach that same point, then it will for sure also intersect the end point before you reach it. Hence you can just check if any circle reaches the end point before you do. Honestly it's kind of a half-assed thought process that I just went with intuitively so I didn't really have a formal proof.

Assume you walk the straight line from A to B. Then for each circle with origin C, you can calculate the earliest time a when the circle touches the line AB, which is just the closest point from AB to C:

          C
          |
         a|
          |
  A-------+----+--B

At time c > a, the circle covers some length 2b of the segment:

          C
        / | \
     c / a|  \ c
      /   |   \
  A--+----+----+--B
        b    b

The Pythagorean theorem says a² + b² = c², and a is constant, so if c grows at a rate of 1/s, then b must grow at a rate greater than 1/s, which means that even if you are ahead of the circle, it will eventually catch up to you, unless you reach the destination (B) before the circle does. That's why it suffices to check that the distance AB < distance BC for all circle origins C.

This also shows that there is no point in following a curved path (which seems plausible initially), because if distance AB < distance BC then you can just walk the straight path, and if distance AB ≥ distance BC you cannot reach B before the circle does, so there is no solution.

What I was doing wrong was running into the wrong memory location, and instead of giving a Runtime error, it just gave a WA :/

Most submitted without proving. Just so happens that the first naive check works because of a clever observation

3 hour contest and it's C. If you get stuck, you start guessing.

I started doing the perpendicular distance thing but then luckily I realized if a circle reaches that perpendicular distance point on the line before you (or any point on the line in fact), then it will for sure reach the end point before you as well (I did it using Pythagoras theorem and some inequality). So I scrapped everything and just checked distance from end point

bro you are dominater

i guessed and solved in almost 50 mins, we are not the same