Hi, everyone!

The authors of Codeforces Round #152 are am-real, max777alex and me.

Special thanks to Gerald who helped us to prepare this round. Also, we want to thank Delinur for english statements. And we'd like to thank Seyaua and sdya for reading and testing problems of this round.

**The round will be held on 25th of november at 19:30 in Moscow time, and it will take place in both divisions.**

**Score distribution div1: 1000 1000 1500 1500 2500**

**Score distribution div2: 500 1000 2000 2000 2500**

Contest is over.

We appologize for ambiguity in the statement of the problem A. It was not clear whether it is possible to touch the goal post when the ball crosses the goal line. However, both ways to understand the problem statement were accepted. These solutions differ by an infinitesimal amount. The only thing that this ambiguity has effected a lot — hacks. All the hacks, which were based on the assumption that such touching is impossible, will be removed. Please, those who have done these hacks inform Gerald Agapov (Gerald).

We also apologize for the interuptions and problems with statements rendering.

Far from unanimous decision of the jury, it was decided to make this round rated. The rating will be recalculated on 26/11/2012 after removing of all relevant hacks.

lets fun :))))

These contest on weekends are better for everyone. Everyone can participate. Good luck :)

open to all users??

Only for Div 1, Div 2 and Unrated users :)

Oh yeah, unfortunately, for only people :/

men. the contest was supposed to be at 12:00 (as i remember), so it is at 30:00 in VN. now it is at

19:30 (22:30 in VN, it means we do it til midnight). Can anyone tell me why the schedule is changed?

There are always some countries where contests start at 1AM, 4AM... While you don't have the ability to create a contest on your own, live with it :)

The main reason is that it is the most convenient time for admins and writers to take care of the contest.

This time it's because Opencup — very popular contest in Russia — will be held tomorrow at 11.00 MSK.

Nope. In Russian branch of discussion I've explained that another popular Russian contest was scheduled for the same time. Many Russian programmers want to have an opportunity to take part in both contests.

ok. i've got it. thanks

`so it is at 30:00 in VN`

how many hours do you have in Vietnam :P ?how many hours do u want?;)

ints 00:55:00 before start :)

Why do people have to post such useless comments? If don't have anything good to write just don't do it.

Dont do it yourself!

Captain Obvious

Keep doing your own work we will do our own!

huge problem statement.. :( (except B).

As a non-native speaker of English. It took me a lot of time to understand the problem.

How terrible the contest is!

terrible system testing too...

The hardest questions came. Almost everyone got zero

The contest is a disaster

wow!!! yeputons did the impossible!!! congratulation yeputons

For some reason I couldn't use scanf("%lf") to read doubles in problem A (div1), neither use printf("%Lf") to print long doubles. Both approaches gave me WA in pretest 1. It didn't count as wrong submissions, but annoyed me a bit.

Also, the sentence "_A goal is scored when the center of the ball crosses the OY axis in the given coordinate system between (0, y1) and (0, y2)._" is not really true, since the ball should not touch the posts (so (0, y1+r) for instance, is not a valid goal).

For some reason, (0, y1+r) is a valid goal. I tried to hack a guy, who had the target there, but the hack wasn't successful :(

Really? I asked about this during the contest and they said me (0, y1+r) is

nota valid goal.Now I think they should make the round unrated if this point is important in some test case.

I dont think its a valid goal, since it will touch the post before crossing (or in the exact moment) in that sense I believe the problem statement is right, I had the same doubt and had to check it.

Well, the answer is a bit subtle. The point itself is not a valid goal, but! if the problem has a solution at all, then the value of xw that hits this goal is within 1e-8 of a valid solution, so it should be accepted :-)

I don't know if it's my misunderstanding for problem A. I think the output for test case "1 99 100 9 90 9", where xb = r, should be "-1". But when I attempted to hack supergobble's solution, the system returned "Unsuccessful hacking attempt — Answer: 8.8902439024". Then, I successfully hacked hlwt's solution with the same test case. @,@

Is x = 11.3333333 in example case 3 correct? the corresponding y is coming to be 5, right ? But 5 = 3 + radius, then why the answer is 11.3333333 ?

Oh got it, 'the 1e-8 allowed error.'

`_/\_`

Oops, I got it.

I totally misunderstood the meaning of goal =.=

For example case 1 4 5 2 2 1 the line that aims at y1+r would definitely touch y2 so the answer should be -1, but your code outputs 1.11111111

I also don't understand problem A. In the test case 4 9 24 10 3 1 the judge says the answer is 4.7368421053, but my calculations show that the ball will pass through the lower goalpost.

Never mind, I'd missed that it was the

centreof the ball that had to pass the line.Actually I got tricked by the same thing (as well as many others, as far as I saw, Neal Wu also fails this test for example). The problem statements (at least the English versions) weren't the clearest ever xD

Additionally confusing was that in real soccer rules the whole ball has to be inside :)

Yes, I was also tricked by the fact that the ball is somehow allowed to touch the lower goalpost after the center has crossed the Y-axis. I assumed the logical aiming point was the centre of the goal.

awesome speed of servers :) that's already rly annoying

Egor96 must banned he have 6 succesful hacks to same person please read his code.

All hacked answers differ by only one line ( if(n==x) print(-1); ) and so the hacked case would simply be x.... lol

Same strategy than for the previous contest. Not very original :/

Same story of lohoped ( with even greater this time: 9)

lohoped is as same as Egor96.

No, You are cheater.

This reply display you are genius or cheater :D

I dont know what type of mocking is this ... after finishin contest 10 minutes later suddenly it shows my B submission hacked .... so is it some ghost or admin self hacked my submission after contest ending ?

If one of my solutions was hacked, will this solution be tested on the final tests? Thank you in advance!

No, but I think that the results aren't final yet. I used testcase: 6 11 H..SSH The correct answer for this testcase is 0 (they can simply go from left to right and back), but your solution and also admins solution answered 1. When I realized this I let admins know and they rejudged these hacks, but there might be other similar testcases. Have any of you experienced similar problems?

Did you get AC though? My program produces 0 as well — could that be a reason I was getting WA all the time?

non-algorithmic problems huge problem statements worst contest ever :|

Do you expect one liners?

Sometimes the problem can't be expressed in lesser words.

Can you try and reduce the length of problem C, without losing any detail?

(and don't forget to add a legend. )

I prefer delete problem C

a problem with geometric O(1) solution

So can you suggest another problem to replace it?

According to the Status page, it seems that the server is doing Final Tests in batches of 20 submissions at the same time, because of that the speed of testing has become faster. Also the "Pending system testing" phase was very short for this contest. Thanks to the sysadmins for the lovely speed optimizations!

looks like Div 1 system test exploded .

Nightmare.

At DIV-1 Problem B. 18 35 HHSSHHSSHHSSHHSSSH Some Accpet Code get 1 as result.

Should be 0

This submission 2650173 of mine outputs 1, but got accepted. I think problem B should be rejudged.

Very tough problem set.. It appeared to me as if I was trying to solve A ,B ,E, E, E .. Add to that the server problems

"25000 700000 1000000 1000000 325000 300000" can hack some Accepted codes for DIV1A.

And what's correct answer? Mine is -1

Nope, the answer is 500000 in fact. It depends on how you define "the center of the ball crosses the OY axis". This is an edge test. When I hacked others, I succeeded if the defender outputted "-1".

My accepted solution outputs 500000. After all, in real life it's a goal :)

I think everyone understood "the center of the ball crosses the OY axis" as "there should be a point in time when the ball's x<0 and it should not have hit any object before reaching this point"

If so, then the judge solution would be wrong if it outputted 50000 for that case. Isn't it?

No I'm Pretty Sure The Answer Is -1 Because In the Middle Of The Way The Distance Of The Ball with the upper Point(y=700000) is exactly 300000 and by the definition of the question : "We assume that the ball touches an object, if the distance from the center of the ball to the object is no greater than the ball radius r." 300000 is not greater than 300000 so it touches the upper point. here is the picture of the situation: http://bayanbox.ir/user/amin.moghaddamv/Untitled.jpg?view

It depends on how you define "the center of the ball crosses the OY axis". If you have crossed the OY axis, it doesn't matter whether the ball touches anything.

actually it doesn't depend on that definition if you look at my picture in the point H the distance between ball and the upper post is exactly 300000.so the ball hit the post BEFORE crossing the OY axis.

Hi, sorry for the off topic question, but what is the name of the software that you used to draw that picture? Thanks :)

It always took me infinite amount of time to draw pictures for complicated geometry problem :(

It looks like Geogebra

Check out Asymptote, it's very nice.

It is Geogebra

and what answer of this test? My solution get 500000.0000000

(10^6)^4 is lager than every unsigned long long number. I don't know whether high-precision is a must. I have to compare two number which may as large as 10^24 in my solution.

Here's my ACCEPT very short code. yw -= r; yb = 2*yw — yb; y1 += r; double d2 = (double)(- xb * y2 + xb * y1) * (- xb * y2 + xb * y1) / (xb * xb + (yb — y1) * (yb — y1)); if(d2/r/r>=1-1e-11) printf("%.11f\n",(double)(xb * yw — xb * y1) / (yb — y1)); else cout<<-1<<endl;

What is going on??

Very slow judging. :(

also Rating update speed is slow :(

and in both division

Hard contest but without question which nobody solve it. :D

Div 2. Problem C. Can someone explain why for second test 1 4 6 2 2 1 xw = 0.75 is not correct answer?

Cause in your case ball will hit the goalstop. "We assume that the ball touches an object, if the distance from the center of the ball to the object is no greater than the ball radius r."

Can you show where I make mistake? But I do not pay attention to how the ball bounces off the wall. It depends somehow on its radius?

0.75 / pos = (2 — 0.75) / (yw — yb);

pos = 2.4; pos >= y1 + r && pos <= y2 — r;

Hm... Your ball will intersect Oy below y1. How you are calculating pos?

I considering the similarity of two triangles. That to fractions is tangents for angle of reflection. I consider the ball as a point in the reflection? Is that ok?

you should consider the ball touch the OY axis(above the y2 or below the y1).

BJIAJL got 9 Successful hacking attempt of theRed, I think it's not normal things. One of the Submission is 2648987

In a proble B, i lost that than n==3 answer isn't corect...

if(n<=2){ cout<<-1; return 0; } for(i=0;i<n-3;i++){ k*=10; m*=10; m=m%210; //cout<<m; } cout<<1; for(i=1;i<n-3;i++){ cout<<0; } k=210-m; if(k<100){ cout<<0; } if(k<10){ cout<<0; }

cout<<k; system("pause");

Is it just me, or was problem D not available in English until the end of the contest? I think I would have found it a lot easier than some of the others.

Problem B was also not available for like 15 min in the middle of the contest. The web page said: Unable to parse markup [type=CF_TEX] That was annoying.

I had the same problem. I could not open for 20 minutes problem D(about the houses and shops) — Unable to parse markup [type=CF_TEX]. I nearly solved it during the contest(I needed 5-10 minutes more). Maybe I could have solved it, if I could have managed to open it earlier.

How soon will the rating updated?

DIV2 C Why is 4 9 30 3 3 1 result -1.

Because you touch the right rod (the ball flies in ~0.136 of it) (I am sorry for my English)

What is rod?

goalpost, sorry. Right goalpost

Goal wide is 5. Ball wide is 2. Why ball can't get to the goal?

Think of it like playing real football. The center of the ball passing through doesn't mean anything. If any part of the ball touches the goalpost, it will bounce off (thus not counting as a goal). So it must always be at least 'r' away from either goalpost, otherwise, it will bounce off.

Goal wide is 5. Ball wide is 2. r+2r+r=1+2+1=4 4 is less then 5. Can you explain better?

Refer to the diagram. The ball has to be at least 'r' units away from the 'Y2' goalpost AT ALL TIMES.

I mean "red" distance.

My submission in Div2 — A is still judging ! 5 minutes above it judged "Accepted" , now I refresh the standing page and it say "running on test 57 — final test" . Anyone please tell me why ?

In the link to the submission, it say "Accepted". http://codeforces.com/contest/248/submission/2642358

But in the result page it say "running on test 57" and the standing is not updated correctly.

may be the system goes wrong .

Very unusual contest

terrible

let me think of an adjective, mmmmm ...., ha Excruciating!

BALListic contest!

I think this round should be unrated, because of technical issues, rejudges and very unbalanced problemset

God.I get a high rank that I never get before .So I hope this round should be rated.After all,it is ok.

Same as you

Yep, I know that there're people like you. So, I think, it'll be okay, if this round will be rated. I only want to know what other contestants think about this.

P.S. Congratulations!

hello Admin,

My submission for Problem B (Chilly Willy) with submission id 2648986 has been judged "wrong answer on test 11". For test 11, n = 3 and correct answer is 210. My code is giving the correct answer 210 for n = 3, on my local machine. But judgement protocol shows my o/p is 119 for n=3. Could you please help me to understand this. Thank you

The output must be divisible (mod must be equal to 0) by 2, 3, 5 and 7 at same time.

YES I agree. That is why answer for n=3 should be 210. My code is giving correct answer 210 on my machine with same code as i submitted during the contest. But judgement protocol shows o/p for n=3 is 119. :(

I think the problem is the precision of pow(). pow(10,2) returns 99 in CF system, though pow(10,2) returns 100 in your local machine. (99+20 = 119 = 7*17, then your method return 119) This is because the pow() function is only for float and double, not integer.

Thank You for your explanation :)

:)

please someone help me how to avoid this problem my submission

try:

cout << fixed << sol << endl;

cout.setf(ios::fixed);

I think you'd better to use

`printf("%.13lf", sol);`

One of the quirks of printf is that "%lf" is not always defined — "%f" is supposed to be for both float and double (float is promoted), while "%Lf" is for long double. All of this, of course, can be avoided by using cout :)

But there's more problems with

`cout`

than with`printf`

C style printf is a better way to controll the fomat.

cout.setf(ios::fixed);

cout.precision(13);

cout<<sol<<endl;

I got this problem too... this is suck... 11.3333 vs 11.3333333333 ( diff = 0.00003 ) is ok but 4.66667 vs 4.6666666667 is not ( diff= 0.00001 ).

Actually, I think this is mostly judge problem. Getting WA with correct answer is totally unfair.

When checking the correctness of the answer, all comparisons are made with the permissible absolute error, equal to 10^(-8).

Absolute error? Really? You do realize that if the answer has 6 digits before the decimal point (as in this case) and 8 after, that's 14 digits, which is

exactlyon the edge of the 64-bit floating point precision (assuming the standard 52-bits for the mantissa).Damn it. My eggs get pained while waiting for the rated result. God.It is 3:30 am now,get to the bed and have a sleep.

Final standings keep changing. Why call it Final standings? :)

I think final standings is not correct. For example, Div.1 winner yeputons submitted two wrong solutions on problem A, but it doesn't affect his score. Why is it?

Get Wrong Answer on pretest 1 will not affect the score

Thank you, I didn't know this.

That's because he got WA on

firstpretest. You don't get penalty if you fail on the 1st test case!Why answer for test 7 is 4.5? What i'm getting wrong? https://www.dropbox.com/s/qjm3mcvpbq2mqwr/IMAG0050.jpg (sorry for darkness)

Submission is here http://codeforces.ru/contest/249/submission/2651233

Though I haven't analyzed your code, but I expect that the failure in test 7 may happen in the case you consider the ball as a point when it is reflected on the wall.

Thanks, I solved.

I'm not shure, if I understand the rating process wright, but I read, that it depends an your estimated ranking (namely the list, of registered people before the contest) und your real ranking. I was around 600th place before the contest in Div1. In this competition(due to missunderstood statements and small mistakes) I did not even solve a single problem, but most of the others also don't. So I got around place 100 -> does that mean, that my rating would increase, without solving a problem... (If it is so, it would be rather strange)

1) Expected place is calculated using only participated people, so it's about 340, as far as I remember

2) Your place is divided from 100 to 340, so you place seems to be used as 220

BTW, as far as I remember there is fix now: if people with score <= 0 can't get rating icrease, but I'm not sure. There were discussions here, you can try to find it

Test #11 : 2 9 10 4 6 3 Why answer is 2.6666666667 < 3 ???

The answer must lie in the range 0 < x < xb = 4. What is the problem?

The broblem is answer < r

Hmm.. I found no problem. The answer is not limited by r.

As of problem A, how can there be an answer with x < r?

In the statement, we have:

"...so the gate of Robo-Wallace's rivals may be not in the middle of the left WALL"

In a case where we aim to x , when x < r, the ball would bounce off the left wall first , am I correct?

No, you are. The situation you and Zero_sharp are discussing may be below.

I decided to simplify the task this way: yw-=r; y1+=r; After this all we need is to calculate position of the center of the ball. Then via school geometry you solve easy proportion. And the last calculation is to check a distance between left straight of the trajectory and y2. If the distance is lower than r then return the solution. Else return "-1". If somebody needs more detiles, I can draw some picture or watch the code.

the rating change should be reflected asap

Can jst ne1 clear my doubt on the compiler's absolutely different processing than the Ideone online compiler because my code worked correctly there and not here.... and yes i know my code would have any way produced wrong output further but it did nt even work on the 2nd preset of the div 2 problem B.....

The CF system doesn't support "%lld" specification. Please use "%I64d", instead. BTW, the pow() function may return unexpected value. For the integer problem, you shouldn't use the function for float and double (, like pow()).

pow(10, 4) returns 9999. Please make sure with custom test.The

`pow()`

function operates on floating point arguments and may return imprecise results. You should implement an integer power function yourself. Also, Codeforces officially recommends to use the non-standard`%I64d`

/`%I64u`

instead of`%lld`

/`%llu`

.In Div2.C(Div1.A)problem,I got Wrong Answer on test case 8. My answer was 4.375000・・・. I can't understand "wrong answer Participant's ball hits left wall before goal". Please teach me what's wrong...

You needed to check a distance between left straight of the trajectory and y2. If the distance is lower than r then return the solution. Else return "-1".

Little update

Editorial for C problem (Robo-Footballer) div2 ?

Rating has already updated!

link to editorial (English preferred) when it's published, please?

My rank in this contest is 514 : http://codeforces.com/contest/248/standings/page/6 . But in my profile page, it says 750 , and my rating go down for 51 points.

Admins, why you don't respond to this?

Could someone please tell me how to solve Problem B? I understand the binary search bit, but how do you find the minimum possible time for a fixed k?

No editorial this time?

You can find it in russian, unfortunately google translates it pretty bad this time (sometimes it's more readable than others).

http://codeforces.ru/blog/entry/5979

I don't think anybody got the Robo Footballer problem right. I just tested several people's accepted code and none of them worked.

Example 1: 5 24 25 6 9 4

A correct answer is xw = 3.00000. None of the programs get this right. They all answered -1. The problem is that if you aim at 3.0000, the ball never gets near goal post 2. However, using the reflection method, which most people seem to have used, it falsely says that the path hits goal post 2.

Example 2: 1400 2499 2500 1200 900 500

Once you've fixed your code to handle the first example, then you have to make it recognize that example 2 has answer -1.

Unless you're careful, your program will think that xw = 100 is a solution. But it's not, because when you aim at that, you'll hit goal post 1 before the reflection.

A completely correct solution has to partition the path into two segments -- before and after the reflection -- and then make sure that both segments are free of collisions with the goal posts. To find xw, you have to intersect the ranges of xw that are collision free in both of the parts of the path.

--- Danny Sleator sleator@cs.cmu.edu

I think another possible approach would be reflecting on yw , get the max angle where the top part goes in, then reflect on yw-2*r, get the min angle where the bottom part goes in, and if min<=max return the average.

How the

%^* is this possible !?!?!?! Problem D — Wrong answer on test 95 Expected answer 130, found 131 -.- .....Looks like correct solution needed this: if(wynik!=132) { cout<<wynik-1<<endl; } else { cout<<"130"<<endl; }

xD

no editorials ?

Can someone explain how to solve the problem Chilly Willy please ?

Let's look at numeric strings of length <= 3.

The smallest number that fulfils this criteria and is divisible by 2, 3, 5 and 7 is lcm(2, 3, 5, 7) = 210. Hence, we can conclude that the answer for n <= 2 is -1 and the answer for n = 3 is 210.

Now let's analyse the case where n > 3.

From here, I assume that the answer string that we are generating is indexed from 0.The smallest numeric string of length n > 3 without leading zeros is 100... (i.e. A single 1 followed by n-1 zeros).

Basic math tells us that any number that is divisible by

both2 and 5 must end with 0. So character n-1 (the last character) must be 0.That leaves us to check divisibility by 3 and 7. We can easily do so by long division and keeping track of the remainder. This works in O(n).

Up till now our answer string is 1 {n -2 zeros} 0. Since lcm(2, 3, 5, 7) = 210, we know that in every 210 consecutive numbers, there is at least 1 number that is divisible by all four divisors.

With this in mind, we can use 2 for-loops to manipulate characters n-2 and n-3 in our answer string.

Let's look at the sample run of this algorithm for n = 5.

Our answer string is initially "10000".

Notice that we will run the 2 for-loops at most 21 times because we "add" 10 to our answer on each iteration. That means we don't iterate through all 210 consecutive numbers. Rather, we just have to check numbers in steps of 10 because the answer has to be divisible by 2 and 5.

Hence, overall time complexity is O(21 * 2 * n) which fits well within the time limit for this problem.

In case you have problems with the implementation, here is my solution (which uses this approach).

Wow. I finally understood this today. Be greedy and find the smallest number of length n that satisfies the condition. The last digit is fixed.

We want a number that's divisible by 3 and 7 since 2 and 5 are already guaranteed. This means we will check at most 21 numbers. (By the Chinese Remainder Theorem)

Thanks a lot, Lance !

You are most welcome! Actually, I think that you can pass the time limit for this problem even if you check divisibility by 2, 3, 5 and 7 since you just need to check at most 210 numbers (using the greedy strategy).

I was just being a little picky by introducing that optimization. In fact, you can even do much faster than my optimized implementation.