Connector's blog

Codeforces Beta Round #64
By Connector, 14 years ago, translation, In English
I'm glad to see you on Codeforces Beta Round # 64.

Today I am the author of the tasks. I'm a student of Tyumen State University.

I want to thank all those who helped me to prepare the round: Nikita Durynin (Austeritas) for the pair ideas for the tasks, Dmitry Bochkarev (Walrus) and Chernenkov Alexey (Laise) for the testing, Artem Rakhov (RAD) for coordinating the activities, Maria Belova for translating and Mike Mirzayanov (MikeMirzayanov) for a great system.

Today you will visit the Walrusland and help the common citizens and government to solve their problems.

Good luck for everybody, let the best man win!

Winner is Petr. Congratulations!

Analysis

Announcement of Codeforces Beta Round 64
  • Vote: I like it
  • +150
  • Vote: I do not like it

Comments Comments (40)
| Write comment?
14 years ago, # |
  Vote: I like it +14 Vote: I do not like it
What if the winner is a woman?
I hope this will be a good contest!
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it
    And I hope we see a woman winning a Codeforces contest.
    That'll be really nice
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
good luck ! :D
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Good rating!
→ Reply
14 years ago, # |
  Vote: I like it +13 Vote: I do not like it
i wonder how log will it be beta rounds?
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Hi, I'm new to the format... Will prolly crash and burn but i hope to better myself gradually. :) Cheers! :)
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
can anyone tell me what is idea behind C ?
→ Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it
    I think, the main is that if a * b = rev(a) * rev(b) then a / rev(a) = b / rev(b).

    UPD: Ой, а вот где у меня и была ошибка :(
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it
      a / rev(a) = rev(b) / b.
      → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      It should be a / rev(a) = rev(b) / b
      For a / rev(a) , you can transform it to its lowest form c / d by dividing numerator and denominator by their gcd and store (c,d) -> a in a map.
      This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)

      That was the main idea and after that there were different approaches. I iterated over all x , from 1 to max_x , and for each x , did a binary search on y to find the minimum y in [1,max_y] that has at least w pairs.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I tried to write exactly this solution, but...

        > This way, for each x, you can find all the numbers y, that can form lucky pair (x,y)
        How? And what did you store in the map?

        It seems it was EPIC FAIL
        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it +5 Vote: I do not like it
          map<pair<int, int>, int>

          pair<int, int> means a fraction first/second. You must divide first and second into gcd.
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I made it, but I still can't understand how the answer is calculated.
            → Reply
      • 14 years ago, # ^ |
        ← Rev. 3   Vote: I like it +4 Vote: I do not like it
        The binary search can be avoided.

        Let's first solve the following related problem:

        Given an ordered array of n elements, return two elements that multiplied are bigger than C. If there is more than one answer return the ones with the smallest product possible.

        The most basic idea is iterating over every pair in O(n^2)

        A more sophisticated algorithm would be to iterate over each element A and do binary search to find an element B which A*B >= C (equivalent to your idea) O(n*logn)

        The fastest approach is to keep two pointers, one starting in position 0 (A) and one starting in position N-1 (B)

        if value(A)*value(B) >= C, B--
        else A++

        O(n)

        It's straight forward the reduction for the original problem.
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it -8 Vote: I do not like it
        How much memory required , O(n*n) where n is number of primes < 10^5 ? 
        → Reply
      • 14 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        > I iterated over all x , from 1 to max_x , and for each x , did a binary search on y to find the minimum y in [1,max_y] that has at least w pairs.
        … using a binary indexed tree.  That was a missing part in my case.

        An alternative way is, as daffes wrote, to do it linearly (starting from (x, y) = (1, maxy), increase x if there are not enough lucky tickets, decrease y otherwise).  I had completely overlooked this approach.
        → Reply
14 years ago, # |
  Vote: I like it +17 Vote: I do not like it
@Problemsetters   - Can anyone frame questions that  Petr can't solve.?.
→ Reply
14 years ago, # |
  Vote: I like it +7 Vote: I do not like it
Is it possible to change display names? I would like to have balakrishnan_v
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why it's posible input like "wordinput....." in problem B. Text Messaging...
Description, i think that limit the end of a WORD with only one ( . , ? , !) or none at all ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Or "....." meaning more text that the input that i can see..
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Yes, “...” means that only part of the input is shown on the page.  I do not think that currently there is a way to show complete test cases when they contain long lines.

      By the way, in this problem, a sentence always ends with one of “.” “?” “!”.  A sentence without these symbols is not allowed.
      → Reply
      • 14 years ago, # ^ |
        ← Rev. 3   Vote: I like it +1 Vote: I do not like it
        Ok, I got accepted now. The solution was right from the beginning, my mistake, I do not put a comment on a break instruction that i use to test some cases, before send to the system.
        A long time lost, searching for an error in the solution, which did not exist
        → Reply
14 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it
Thanks for nice match!
I thought that the trap of A is NICE , and hack system of Codeforces is becoming the better event!

However, I thought that we couldn't understand the boundary condition about size of one message from samples of B.

So I have a simple question to @Problemsetters.
Why did you set such number as sample ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The reason is probably to make hacking more interesting in the same way as Problem A.  The size of one message must be understood from the task description in the case of Problem B, not from examples.  I defer my own judgment whether that was a good decision or not, but the intent is clear.
    → Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
how to arrive at the formula for question 1 ?
and what was the logic behind 4rth question ?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    If you look at first three answers - they are 1, 3, 9. It hints the pattern - 30, 31, 32.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it
      Another way to interpret the formula:
      Given a block Bk, k ≥ 1 with size 2k × 2k, Bk + 1 is built based on four blocks, each of size 2k × 2k. To get the answer you cannot avoid placing something like Bk at the lower left 2k × 2k block. But for Bk + 1 the upper triangle must be filled, so you can see that the upper right 2k × 2k block must have no space left. What about upper left and lower right ones? Well, you can actually see that their upper triangles are also filled, giving you exactly the same initial setting for Bk, so you must have number of spaces for each block exactly the same as that in Bk. So if Bk has Ck spaces, then Bk + 1 has Ck + 1 = 3Ck spaces for k > 1. That gives you the 3k - 1 formula for k > 0. Be careful in handling the case k = 0.
      → Reply
14 years ago, # |
  Vote: I like it +11 Vote: I do not like it
can i get editorials(in english) for the problems somewhere ?
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Can anyone highlight why this is always true "Notice, that any point from the triangle based on first three points will be into the convex hull in the future".

Thanks.
→ Reply
14 years ago, # |
  Vote: I like it +2 Vote: I do not like it
that was good contest
→ Reply