Hello everyone!

Codeforces Round #187 will take place on Friday, June 7th at 19:30 MSK. This is my seventh Codeforces round and I hope not the last.

I'd like to thank Gerald, Furko and Aksenov239 for helping me to prepare the round. Special thanks to Delinur for translation of all problem statements into English.

I strongly recommend you to read ALL the problems.

Gl & hf ! :)

good luck everyone

Thanks!)have fun everyone

Thanks!)0

except it is "use"

it's for fun as they don't use a good one

hopefully it won't be my third consecutive unrated round :D

I hope problem statement to be short & easy to understand like your Post :D

I can't understand the guys like you... The link

lol you are right! a post's acceptance is so random!

Seventh and not the last... very impressive!

Sereja must be the author of the year

Hey bro, wuold you mnid cehcking yuor seplling?

Do you know what's the meaning of my nickname?

Hope Djo vs Nadal will end before the contest

i'll try my best to reach blue!..bless everyone!..Hope everything goes smoothly

I'll try my best to stay green :D

you don't have to do anything for that

Do you really think that the problem statements are written in English?! I can hardly interpret what's written!!!!!

LOL

;

Really good and fast system test tonight!

After seeing others' submissions to div2 A, I figured out the solution immediately while still couldn't connect the solution to the obscure problem statement.

I understood the statement's intention finally.

Need some help here. Would someone explain the test case 4 for div2 A? Thanks.

4

2 3

1 772

3 870

3 668

Correct answer: 2

using bottle 1, which is (2,3) he can open bottles 3 and 4, which are both of brand 3. this is because bottle

ican open anyotherbottlejif b[i]==a[j].so the bottles 1 and 2 are left unopened. hence answer = 2

Thanks for the reply. I got it now.

You can use the 1-st bottle to open bottles of brand 3 (3rd and 4th). The 1st and 2nd bottles can't open. Answer:2 .

May be I weak in English, I can't understand div2 A satement. it seems to me a little confusing what actually the problem statement wanted.

Did someone proofread the problem statements? At least I made many assumptions for solving D1-C and I can't understand D1-A

at allbefore reading the example..."Pay attention to the analysis of the first test case for a better understanding of the statement."

YOU DON'T SAY!!!I am not able to find test case on which my code for Div 2 A was hacked. Could anybody help ??

I am also doubtful.The first line contains integer n (1 ≤ n ≤ 100) — the number of bottles. I am bit confused by this line .. How come the answer for test case

2

1 1

1 1

isn't 2 if there are 2 bottles .

same with me, but correct answer is 0.

this case is wrong

no brother the case is correct though i got also wa for this case but it is perfect case . if just only 1 1 it means there is one bottle which can open the 'brand 1 ' and its brand is also 1 . it means it can open only by itself. but if a.1 1 , b.1 1 this input you can use 'a' bottle to open 'b' bottle and use 'b' bottle to open 'a' bottle so answer is 0. really a awesome case ,isn't it ? :)

then what about this:

two 1s, and 2,3,4. brand 1 could open 1 and 2

I think the answer should be 0 but the author marks 1 as the correct answer.

The problem description is confusing and I think the sample tests are intentionally misleading.

Could you provide a link to your submission which was hacked.

Can anyone tell the intended solution for div2 D ??

you can calculate the max match between a{1...a_size} and c{i...c_size} in advance,record the match times and the c's very last match position . then do b times and count the occurrence of c . finally divide by d is the result . sorry for my bad english.

i don't exactly understand what you mean by "max match".

I think it'd be better if you give some example.

Let a = "abab" and c = "baa"

Can you explain how you operate, choosing suitable values b and d ?

let [a,b] = ["ababab",3] and [c,d] = ["baa",2] .

we preprocess NextMatchPositionOfC[1...c_size] and OccurrenceOfC[1...c_size] .

for a[1...6] = "ababab" , c[1...3] = "baa" , we can get NextMatchPositionOfC[1] = 2 && OccurrenceOfC[1] = 1 . (a' = "baab")

for a[1...6] = "ababab" , c[2...3] = "aa" , we can get NextMatchPositionOfC[2] = 3 && OccurrenceOfC[2] = 1 . (a' = "aaba")

for a[1...6] = "ababab" , c[3...3] = "a" , we can get NextMatchPositionOfC[2] = 2 && OccurrenceOfC[2] = 2 . (a' = "abaab")

then we can set a pointer ic = 1 and do loops for b times.

{

MatchTime += OccurrenceOfC[ic] , ic = NextMatchPositionOfC[ic] .}we can get MatchTime = 1 + 1 + 2 = 4.

finally MatchTime / d = 4 / 2 = 2 is the result .

and i think this problem is just a deformation of http://poj.org/problem?id=1936 .

hope this helpful .

wow system testing and rating updates completed really fast today! :) thanks Sereja!

I read the problem statement the negligence led me Div2 A FST it. Next must not commit such a mistake!

hope the tutorial will be published soon.

I spend much time on C's debug, but I couldn't... And my C failed because of the matter of modulo, my solution output -(1000000007-x) instead of x... So sad...

Anyway, thank you for interesting problems!

Admin , look at both of the submissions . They appear to be almost same .

http://codeforces.com/contest/315/submission/3841333

http://codeforces.com/contest/315/submission/3841920

I would like to clarify that I code a lot of times on windows and use Ideone for the purpose . So,its very possible that the code is manipulated not by one but a lot of people and since in this case the time remaining was very less , I forgot to make it a private. It won't happen from next time I will take care of that .

Can you also explain the following:

How did he submitted his code 7 minutes before you?

How come that, while you did not use any marco for your previous submissions, for problem C you suddenly start using marcos in a style that is very similar to the coding style of aman181993's? From the submission history one can see that aman181993 started using F(i,a,n), FD(i,a,n) all the way back from May 19.

Why this solution has been skipped??http://codeforces.com/contest/315/submission/3837849Please, retest it again :'(

Problem D was the best in div2

It seems that both AC solution of Div 1 — E is O(n^2). It should not have been the expected solution.

It is expected solution. Its O(N^2), but to solve this task you should make many optimization that makes O(N^2) --> O(N^2 / big const, near 32).

When writing English version of announcement, please link to codeforces.com for the tutorial -- codeforces.ru automatically changes language to Russian, which is somewhat annoying. But anyway, good round!

Can anybody tell me how to solve the pro.E of div1

Where can I find a discussion forum for this topic? I wanted to see the solutions for this Codeforces Division Match. :)

My submission for div1 — D ( 4401712 ) passed lots of test case where it should not:

ok found '85784037.0000000', expected '85784036.5000000', error '0.0000000'

The relative error here is less than 1e-6.

The correct relative error is 0.5. My program always output an integer where it should not.

Edit: Seems like I had some confusion between relative & absolute error. But using relative error in this problem doesn't make sense to me. The answer is always N or N+0.5 (where N = integer). Allowing relative error < 1e-6 may allow incorrect submission to pass. E.g. If I used different algorithm for small N, my wrong solution would have passed.