Sereja's blog

Codeforces Round #187
By Sereja, 11 years ago, translation, In English

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 ! :)

tutorial.

  • Vote: I like it
  • +200
  • Vote: I do not like it

Comments Comments (56)
| Write comment?
»
11 years ago, # |
  Vote: I like it -23 Vote: I do not like it

good luck everyone

→ Reply
»
11 years ago, # |
  Vote: I like it -35 Vote: I do not like it

have fun everyone

→ Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -48 Vote: I do not like it

0

→ Reply
»
11 years ago, # |
  Vote: I like it +95 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Seventh and not the last... very impressive!

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

Sereja must be the author of the year

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +60 Vote: I do not like it

    Hey bro, wuold you mnid cehcking yuor seplling?

    → Reply
»
11 years ago, # |
  Vote: I like it +31 Vote: I do not like it

Hope Djo vs Nadal will end before the contest

→ Reply
»
11 years ago, # |
  Vote: I like it -7 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    I'll try my best to stay green :D

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      you don't have to do anything for that

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +20 Vote: I do not like it

Really good and fast system test tonight!

→ Reply
»
11 years ago, # |
  Vote: I like it -12 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 3   Vote: I like it -13 Vote: I do not like it

    I understood the statement's intention finally.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it +2 Vote: I do not like it

        using bottle 1, which is (2,3) he can open bottles 3 and 4, which are both of brand 3. this is because bottle i can open any other bottle j if b[i]==a[j].

        so the bottles 1 and 2 are left unopened. hence answer = 2

        → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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 .

        → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

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

    YOU DON'T SAY!!!

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I am not able to find test case on which my code for Div 2 A was hacked. Could anybody help ??

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 .

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell the intended solution for div2 D ??

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 7   Vote: I like it 0 Vote: I do not like it

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

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

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

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

        3. 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 .

        → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +26 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

hope the tutorial will be published soon.

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

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

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -23 Vote: I do not like it

    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 .

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Can you also explain the following:

      1. How did he submitted his code 7 minutes before you?

      2. 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.

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this solution has been skipped?? http://codeforces.net/contest/315/submission/3837849

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem D was the best in div2

→ Reply
»
11 years ago, # |
  Vote: I like it +23 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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).

    → Reply
»
11 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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'

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 3   Vote: I like it +11 Vote: I do not like it

      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.

      → Reply