Three drops in a line, back to yellow so quickly ...

Anyway, Codeforces Round #183 will be take place on Sunday, May 12th at 17:00 MSK(21:00 CST). Right after the Google Code Jam Round 1C.

Setters are:

**Yuzhou Gu**Sevenkplus (For Problem B && E)**Yuping Luo**roosephu (For Problem A && D)**Jiatai Huang**CMHJT (Problem C)

Testers are WJMZBMR, havaliza, Velicue && me.

We gratefully acknowledge **Gerald Agapov**(Gerald) for his help in giving advise about the problems, **Delinur** for her help in translating the problems to Russian, and MikeMirzayanov, who has designed such a powerful platform.

We strongly recommend you to take a glance over all five problems, there must be one suitable to your taste.

Oh one more thing, this time, scoring will be **dynamic**, but problems are **sorted by increasing order of their difficulty** as usual.

Good Luck!

Great!! I think it will be a great contest while the setters and testers are very good. Thanks for your soon post :)

Not in midnight in Japan(and other far east Asia and Australia) Great!!!

Codeforces Round #183?

Fixed.

Are you sure in number of this round? Think, it should be 183.

Sorry for such a silly mistake ... /w\

Very early announcement and score distribution (many peoples has like it), great setters and testers — I think it will be very interested.

Haha noone even mentions Div2 A and Div2 B problems :D

As you can guess, DIV 2 A, B is set by me ... /w\ ......）。。。

I think the problemset is easier but much more interesting this time..

Who set the problem for Div.2

Am I right that original statements will be in english?

Of course they're English.

Actually they should be in Chinese..:)

Maybe Chinglish lol~

I think hacking score is too low.

Why this blog was not on home page ?

The first time I can participate in

Hmmm contest time changed? 6AM in California...

Why time is non-standart?

There was a risk of yesterday’s TCO Round 2C being cancelled and moved to 16:00 UTC today. Codeforces’ usual 15:30 UTC would conflict with it. It already happened with round 2A on 31st of March.

Thank

It would be interesting for me(and I think not only for me:)) to know some additional information about the authors of the contest — your hobbies, photoes, interesting stories etc.

xiaodao's photo there >_<

I wondered why comments by xiaodao got so many negative feedback?

A question : is xiaodao (Feihu Tang) boy or girl?

I thought the name is a boy's, but in his(or her) photos shared above it's a girl....

You can see that her name is 唐菲蝴(beautiful butterfly Tang),then everything goes right.

She's really a girl, believe me.

I recommend you all to participate in this event. You would enjoy solving this set of beautiful (and challenging :D) problems. :)

It is the Chinese round. I am really excited to see the problems! :) We had American problems (with USACO cows' background), we also had Japanese problems (rng_58's and the rest). And now is Chinese round. Love it.

=w= unsuccess to reach 1500 last match...=w= so ..hope my friends and i can reach blue again ..T_T

are there any mistakes in sample tests in problem B div 2?

Congrats for making unrated contest.

Who told you?

I hope you joke

Sir, this ain't April the 1st.

The contest was perfectly prepared and tested :D

Why in B in the second sample the answer isn't (29,22,75,78)? In this rectangle distance from the center to the point (x,y) is 0, and in the answer to the sample it's 0.5.

Same here. I don't know why this is incorrect...

The sad part is that a lot of people solve it and I don't even know how to interpret the statement — should the rectangle be the closest to (x;y) or lexicographically minimum..

I spend a lot of time to guess — but i still don't know why... Sent clar, let's wait

I sent one an hour ago. Guess what the answer is? You're right, "no comments" :)

For me, they said, that my answer is not optimal..

Did they explain, why?

I sen't another clar 15 minutes ago, still no answer. UPD: Got an answer : We need first maximize the sub-rectangle, then take the lowest distance.

Damn, missed the word 'maximum'. Thanks, man.

because you should select biggest rectangular possible

Thanks for the answer. I feel like a total loser.. Ah, anyway, this will be a good lesson for my future contests.

From the problem statement . . .Your task is to find a

maximum sub-rectangleon the grid (x1, y1, x2, y2). . . .Missed the round — no mail?

Check spam folder.

Translation please? :o

wow wow clars, be easier)

How to solve Div2 D?

first make a and b coprime try to max the length of x such that x%a=0, then check if y falls in range. if not, max y such that y%b=0

Lots of hacks on A div2 with test "10000", library solution on B div2 on Delphi, unprepared B div1. Nice.

python lol)))

I'll just put it here. http://en.wikipedia.org/wiki/Cyclic_number

I think the limit of n for A div 2 should be 10^3 or 10^5. Most of my room has a O(n^2) solution. Especially a nearly O(n^2*log(n)) succesful in defended 2 attack.

http://en.wikipedia.org/wiki/Cyclic_number

no comments

Because of so many mistakes, I strongly think this round should be unrated.

if so, this will third continuous unrated contest :)

I agree with you.The questions were published so late that we had misunderstanded the problem and wasted much time. BTW, the D is a popular knowledge which you can find it on the Internet.So, I hope this round will be unrated.This is the only way to make it fairly.

Dynamic scoring usually makes scoring very different from past. Will it influence the rating system?

this is called dynamic scoring

It's dynamic scoring

What a funny round!

Great round, interesting problems. :-)

The problem is nice,but clarifications too disturb.Waiting for next round.

My O(N^2+k^2 a_max log a_max) solution passed system test of problem C with a lot of brunch-cutting... I think it is not intended...

an O(n^2+ans*k^2+a_max ln ans) solution was expected.

Sorry, I mistook the analysis of my order... My solution was your order, thank you.

I think TL is too short because my solution passed in over 1800ms with a lot of brunch-cuttings...

Try to use array instead of vector, it speed up performance of my code dramaticaly in this problem.

Oh, thank you for your advise.

Nice problems. A lot of maths, but It's enjoyable. :)

Intereting problems!

The data for div1 D seems weak. When N=1, it's clear that every base works, so the answer is x-1 if x > 2 and -1 if x = 2. However, some solutions that didn't handle these cases still passed system tests. For example, 3709363 gives 1 on the case "1 2".

What is the solution for problem Div 1 — C (Div 2 — E) (Minimum Modular)?

System testing of Div.2 was very bad.it was finished , but final standing was not ready!

Div.2 A

My code is TLE. ~~~~~ ans=sqrt(0.0+SQ(i)+SQ(j)); if( ceil(ans)==ans ) cnt++; ~~~~~ But I change “(int)ans==ans” ,then get AC....

TvT

Check out mine 3706566. I think problem is in

`ceil()`

and`floor()`

. Got AC replacing`floor(c)`

with`(int)c`

— 3712951. I would like to say :Authors, How about increasing time limit to 4s ?but it's too late. I have already got myWow you have +67.i too used ceil() function and TLE...

It would be better that you check your solution in custom test before submitting....

ORZ failed div.2 A

For Div2 C, now I understand why I could not find any formulas for even values of n..

Weak pretests :(. B-Wa 11 because of mixing up n and m.

Wow constraints were really strict.

My DIV2 A didn't pass because of the c++ floor method which is too slow, compared to a cast. For DIV2 B, why doesn't it work using mktime and difftime from ctime? ...

http://codeforces.ru/contest/304/submission/3706514

Are you still sure that's because of floor()?

Well I did some tests:

Using floor: http://codeforces.com/contest/304/submission/3713082

With a cast: http://codeforces.com/contest/304/submission/3713854

843 ms with cast

1609 ms with floor()

But it doesn't mean that solution with floor can't be accepted

Sure, your solution passed :)

I just noticed you were using VC++ compiler, and me gcc. After some research, it seems that VC++ generate a more optimized code than gcc, so the floor method could be optimized as well: http://stackoverflow.com/questions/3752988/gcc-vs-ms-c-compiler

`mktime() : convert local time to seconds since the Epoch`

`The Unix epoch is the time 00:00:00 UTC on 1 January 1970 (or 1970-01-01T00:00:00Z ISO 8601).`

http://en.wikipedia.org/wiki/Unix_time

my final tests are checked but its showing skipped what does it mean????? http://www.codeforces.com/contest/304/submission/3709339 please clarify it...

Are you sure your solution is your own, not copied from others?

Screencast: http://youtu.be/XWsPoC4p-EY?hd=1

add music))

How to get full test cases for: http://codeforces.com/contest/304/problem/E?

Thanks!

Check the submission of Ents : http://www.codeforces.com/contest/304/submission/3710988

In the submissions large input data are cut.

you can't get large test cases

Having spent about 20 submissions trying to find out the reason of my wrong answer on test 8 in Div1-E, I've managed to receive the following outcome from the judge:

wrong answer 201st numbers differ — expected: '-0.0132824', found: '0.0124727', error = '0.0257551'This doesn't look like a correct probability, does it?

I've got TLE 8 during the contest, but later I optimized my solution a bit and now it's giving the same answer as yours on the 8th test even when I use long doubles.

All tester's program have different solution so you know

the model solution of E is wrong...it has precision problem.

the setter is trying to fix it... but still rng58'solution seems has precision problem too...

actually they all work fine when n=40, but start to differ when it become bigger,when I change the double in model solution to long double,it seems it is the same answer with KADR.

I've asked the author to give me his solution, and the author's solution returned even worse answer (smaller than -10000) for the following case:

int main(void){ int i; cout << 80 << endl; for(i=0;i<80;i++) cout << i << ' ' << i+80 << endl; return 0; }

My solution during the contest (got WA) also contained precision errors for this case. The probabilities were between 0 and 1, but the sum of the probabilities in some row was more than 22 (while it should be 0).

Currently I guess it's impossible to solve this problem precisely under the given constraints.

That is really bad.

I think this round should be unrated to you QAQ.

yes, if his solution is realy correct

Yes, they can.

tourist's solution has no precision problem, but it run in O(n^5),maybe too slow. (it run 1890ms,barely in time:) )

I optimize it and work out an O(n^4 logn) solution,I guess now it is ok:3716717

In attempt to make my Java version go through the time limit (without use of

`if (l[i] <= L && r[i] >= R)`

elimination) I gradually optimized it and after succeeding I also found out that Gena's (with or without your great asymptotics improvement) solution can still be noticeably optimized. :)Initial version: http://codeforces.ru/contest/303/submission/3716717

With two code optimizations: http://codeforces.ru/contest/303/submission/3718523

Yes, you are right. The author's solution is wrong for that tetscase. But all the pretests were right.

So, now we are discussing how to solve this problem with precision and make the results of the round as fair as possible.

Thanks for the notification!

I have seen you solution, it is a good idea but it actually run in O(n^5),maybe there's some test can make it TLE （the inner running time is (the number of segment contain givn sub-segment)^4. I have optimize it a bit and now it run in O(n^4 logn). check it 3716717 here. Now I think this problem is solved.

It seems that my solution's running time doesn't depend on the actual test case as long as

l_{i}≠l_{j},r_{i}≠r_{j}andl_{i}<r_{j}for alliandj. A gap of 110 ms is not big enough, though :)Your optimization is nice, thanks! Now the problem is really solved.

I checked WJMZBMR's n^4logn code and i believe that it has precision problem too, though it pass all the test datas.

Besides, I guess it may require O(n^5) to get the right answer, and so i suggest either enlarge the time limit or reduce the size of n ;)

We discuss for a long time with a setter this problem. So we change the solution to a correct one. All the solutions that passed pretests at the contest failes on the system test as expected. So, this problem doesn't affect on the participants, because the pretests were right.

My appologize for this situation. And great thanks to tourist for the notice!

Can you write tutorial for this problem?

It seems I solved 303C - Minimum Modular with brute force 3712393 which, I think, is O(5000*10^6) in the worst case.

Is there any testdata which challenges the program or I calculate the complexity wrong?

Your solution is not brute, cause you calced values s and use them as optimization. Your solution is very close to right solution.

Can anyone provide a proof of Div I Problem A? I just noticed the pattern for n <= 10 and just submitted that hoping it would work.

EDIT : The proof I have post is wrong. See the comment below.

Please correct me if I am wrong, but I am not getting the proof.

When you say even-odd pairs, does that mean all the evens come from A and all the odds from B. But, we can still get n/2 odd by mixture of ( E,O) And (O,E). Precisely n/4 (E,O) and n/4 (O,E). And same applies for getting n/2 evens. In essence this points that we can still gets the even-odd configuration.

You are right. Sorry for having post a wrong proof.

No problem at all. Actually, this is way I was trying to prove that any configuration possible not for even n.

I just got proved that if n is even and if it is not divisible by 4 then there is no configuration with the above reasoning.

If you get the proof using the above logic please let me know.

If , then or just , where

S= 0 + 1 + ... +n- 1 =n(n- 1) / 2. So, there must be . But whennis even, .Where S=0+1+2+3+...n-1=n(n-1)/2

Thank you, fixed.

there must S = 0 mod n. But when n is even, S != 0 mod n. I do not understand the above statement. Could you please elaborate more. Thanks

When n is even, S = n * (n — 1) / 2 let n / 2 = p which is smaller than n S = p * (n — 1) Clearly, S in this case is not divisible by n.

this is fine, i got the logic, but how to get the sequence as all sequences are not valid. your formula just tell if a valid sequence is possible or not.

for N is even output -1 for N is odd the two permutations like this: 0 1 2 3 4 ... n-1

For this very fast solution to problem A in div2, could someone explain the math behind it? Thanks.

Check the wikipedia article, it also contains a proof

How to solve div2 E-Minimum Modular? Thanks in advance.

means "

a_{i}-a_{j}is not divisible by m. So calculate the differences of all pair of integers.We check that "if we choose m to modulo, we can do the array satisfies conditions?" for all integer m until we find m from (n-k).

Answer≤ 10^{6}+ 1 because if we choose 10^6+1 for m, obviously it satisfies condition.When we search about m, all we have to do are research about multiple of m and get the array of "Which pair of integers are same modulo m". If the size of array exceed 10(), give up search.

In this solution, the order is O(N^2+a_max log a_max+k^2 a_max) because O(1/1+1/2+1/3+...1/a_max)=O(a_max log a_max).

Similar solution of mine in Java (3754545) gets TLE. I think time limit is very tight for java solutions. Any thought?

Replacing ArrayLists to Arrays makes it much faster. I got AC. Lesson learned.

Thanks.

When will the editorial be published? I really want to know how to solve Div1E...

The editorial has been published, but It is doesn't have solutions for Div1 D and E http://codeforces.com/blog/entry/7641

Thank you so much! I'm going to continue to think about Div1E.

I think intended solution of Div I E is incorrect(or problem description is incorrect):

I have test some AC code for this case: 3 1 10 1 10 1 10

I think the correct answer is 0.25 0.5 0.25 0.25 0.5 0.25 0.25 0.5 0.25 but seems AC code's answer is 0.3333333 0.33333333 0.333333333 0.3333333 0.33333333 0.333333333 0.3333333 0.33333333 0.333333333

obviously for each person rank 2's probability is higher than 1 or 3,be cause there are two kind cases for p2: p1<p2p2>p3