rateng ke chenj haba?

Unfortunately almost nobody noticed your profile picture is about tinkoff before you say that :D

On April 23, 19:35 MSK will be held _rated_ Tinkoff Challenge – Elimination Round.

Nope

for you no

As I know, the prefix "Codeforces Round" will only be added to the mirror version of a championship or a competition that didn't be held on Codeforces officially. However, Tinkoff challenge is held officially on Codeforces and that why they don't add the prefix.

I thought the same thing, usually there are div1/div2 mirrors for things like this.

Does it matter ?

It means this guy :)

Oleg Tinkov

I am his big fan :D

why not?

YES, it is said in the article.

It is interesting to see your reaction for each of the 2 possible answers. Let's model the situation and you get the following comment from the author:

1. Yes, there will be a geometry problem.
   How would you react to that?

2. No, there won't be any of that kind.
   How would you react to that?

i bet no

You've jinxed it...

:C

UPD. Scoring: 500 1000 1500 2000 2500 3000 3500

GCJ Round 2 begins? what is this? Google Code Jam?

There is an answer in russian branch (you've studied russian, am I right? :)) from one of the event organizers: "I also want to write GCJ, so we will end until R2 begins"

Why not*

It's codeforces' usual

FA Cup Semi-final: Arsenal vs Man City match perhaps :p

Better delay the round rather than have long waiting queues during the round =)

Send the code, so maybe we can find the error in it. I got pretest passed for first on C, but I know I'll fail system test, and I couldn't get another pretest pass from 3 more submissions. I got RE4 for the submission I think was good :P

I can only hope, the system test will be weak.

Something like point can have speed vector of zero length

This thing just ruined my contest. Didn't even think about it before I read your comment :(

laughed too hard on this one

I did ternary search to get when will a mouse be inside, then binary search in both directions to get the total interval each mouse will be inside

Use binary search for the time. You can check if after some time the mice has went out already of the trap, is inside it, or hasn't gone to it yet.

First, you can see that a mouse will be in one segment of time (tEnter; tLeave) (or it won't be in the trap all the time, then the answer is -1). To find these segments, we can find intersections with the lines that make a rectangle.

Then, we make the events such as {mouse x came to trap at time t} {mouse x came out of trap at time t}. Sort them and process consecutively. If we found the "came to trap" process, we increment the amount of mice, otherwise decrement. If we found in some point of time that there're n mice, we just output this period of time.

Let's pick a single mouse. Assume for simplicity that v_x > 0 then the mouse will be in the right x area if x₁ < r_x + tv_x < x₂ which is equivalent to requiring that (simple algebra). You can do something similar for v_x < 0 and when v_x = 0 you either pick the empty interval or all of [0, ∞) depending on whether x₁ < r_x < x₂ or not. When you do the same thing for y and intersect these two intervals, you'll get the time during which this mouse is in the trap.

Do this for all mice, intersect all of these intervals and pick the smallest non-negative value it contains.

I didn't hack with it because didn't have time, but

1 99999 99999 100000 100000 -100000 -100000 1 1

seems a pretty good hack case to me.

I hacked with this simple test:

1 1 1 3 3 0 1 1 0 (answer: -1)

The idea is the mouse runs along the border of the rectangle, but is never strictly inside it.

Let's wait for system testing and see how it goes :)

I implemented solution in such a way that it feels risky even with long double :)

Upd. You got WA due to using eps, not because of double. For me using double still works: 26638771 (I have no idea if it is actually OK to write it this way).

WHATT?? NOOOO! :(

Yes, the approach is correct, probably there is an error in the implementation.

the hacking page was stable for me the whole contest.

It also might be browser related. The same thing was happening to me in chrome but I swapped to Microsoft Edge for a sec and the page loaded. Not sure if coincidence or not since I didn't try again.

I encounter the same trouble after hacking one submission.

B also.

What was the Hack case for C ?

Why?

At the end of the day I'm really happy with this problem because I discovered something which was surprising for me.

I represented an empty interval as a pair (-1.0, -1.0). I mantained an interval of possible trap closing timestamps. I forgot to check at the end if it was empty. So sometimes I print -1.0000000000 instead of -1. It still passes, of course :D.

It was hilarious, really :D.

Anyway, I agree that it was messy.

Welcome to div2 :)

Yes, B is hard for a B. and C is too long.

I agree with you !

The sample cases on the tasks B and D weren't good also. In B, there were only cases with n=m. In D, there was no case with -1.

It's always good to give a case with -1 in samples (except the case when finding the test with -1 i stricky and requires good thinking skills).

I had this following dp[current_city][min_city][max_city][k]. At each state you can only visit another city x if min_city < x < max_city.

used the same :)

Tried the same but didn't notice that edges are directed :(

Yes, my recurrence is very similar.

solve(pos, left, right, done) where pos is current position, done are number of banks already gifted, and left and right is allowed range, initally 0 and n-1 respectively.

Then for the recurrence,

Iterate all i in range(ll,rr): solve(i,left,pos-1,done+1), if i is on left of pos solve(i,pos+1,right,done+1) if i is on the right

same

you can use Dynamic Programming Your state is (int start,int end,int current,int taken) indicating left boundary , right boundary , current position and number of visited offices note that the state can be redefined to save some memory i hope it's efficient enough to pass xD

dp[l][r][last][k] = min cost when you can move in l,r and last city is last and we visited k banks. But it is slow. So we can notice that l or r will be equal to last, and we can remove r so it will pass.

I thought I was overthinking to use dfs in a B

Some people including me used only integer arithmetics in C. And you don't even have to do binary search.

I think the goal of the problem was to require integers (or understand float numbers well).

the answer is?

coordinates must be non-negative

My program gives 1.

Can I downvote please if my solution passes it?

I think the answer should be -1. The first mouse enters the trap as the second mouse leaves, but they are both never strictly in the trap. Correct me if I'm wrong.

should the answer be -1?

Mine passes but I still couldn't get past pretest 4 :(

I did the same.

i did the same, though i wonder if i will get ac

I've been looking at your solution, it's quite clear. How do you handle strictly inside condition? I could not see anything for that.

It's a common term and you could have asked about it.

Hmm, you also had Wrong answer on pretest 7, didn't you? =)

think about the case which a mouse in the rectangle at the beginning?

The mouse should be "strictly inside" the rectangle and not on the border.

That's right, according to the formal statement, the only possible right answers are 0 (if the mice are already strictly inside at moment 0) and -1 (since there is no "minimum number strictly greater than a given number"). So, the statement formally contradicts the first example. Which is bad (Captain Obvious here).

I remember the same exact issue handled gracefully in a statement here at Codeforces in the past, but don't remember the exact problem. If someone does remember (past coordinators perhaps?), please give a link!

So the answer is always 0 or -1?

So basically the time that at least some accepted solution outputs (for example, my solution in the upsolving) is the time, when at least one of the mice is on the border of the rectangle, and that's, strictly speaking, OK, because absolute error is infinitely small. But, if there is no such moment (for example, mice "meet" strictly on the border), the answer is -1, which is logical, but feels weird for some reason.

The important thing is:

I sorted the array too but mine passed

Here is my submission

Java's sort isn't guaranteed O(n*logn), it can be O(n^2) sometimes. You should shuffle the array randomly before sorting.