RAD's blog

Codeforces Beta Round #23
By RAD, 14 years ago, translation, In English
Hi everybody

Today the author of the majority of problems is Dmitry Zhukov, many thanks to him for this. 
Also I want to thank Mike Mirzayanov for choosing problems for the contest and organizing it and Julia Satushina for the translation of the statements.

Good luck!

UPD:
Announcement of Codeforces Beta Round 23
  • Vote: I like it
  • +25
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
registrations closed!! nice! bye... next time! 
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
Can somebody explain why the answer to B is max(0, n-2)? Or suggest a reference I can read about it...
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Find out with tests and you'll see the solution of task B.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    You can do some simple Math proof. Prove that it's impossible to have n or n - 1 people left. With n - 2, we can single out 2 people (these 2 guys dont know each other) and put the rest into a group where each member knows each other and knows the 2 isolated guys. It's each that this arrangement satisfies the conditions of the problem.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      My typo: " It's easy to prove that this arrangement satisfies the conditions of the problem."
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
@:Shuaib: The is a algorithm as following
-First , construct a full graph .
-Then  remove a random Edge from the current graph . Two vertices of this edge have a degree of n-2, and the remaining edges have a  (n-1)-degree.  So we have the answer.
→ Reply
14 years ago, # |
  Vote: I like it +3 Vote: I do not like it
Any idea about Problem C?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    From what I've seen in the solutions, it's enough to consider all subgroups of n contiguous boxes, wrapping around. However, I have no idea why it's correct, maybe it's related with the fact that there is always an answer.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it
    If there is a pair i, j such that a[i] >= a[j] and o[i] >= o[j], we should choose the i-th box and not to choose the j-th box, and then we can solve the problem for (N - 1). Otherwise sort the boxes and get a[1] < a[2] < ... < a[2*N-1] and o[1] > o[2] > ... > o[2*N-1]. Choose boxes 1, 3, 5, ..., 2*N - 1.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      how to prove this method can satisfy the condition in the problem? it's really hard for me to think such a solution....
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it
        When we pick numbers with odd indexes in a sorted sequence, their sum is always more than half the sum of all numbers in the sequence.

        Reasoning =>
        Lets remove A[1], 
        We know that
        A[3] > A[2], A[5] > A[4], ......, A[2*N - 1] > A[2*N - 2]
        We're adding the greater sides from all these inequalities so

        A[3] + A[5] + ... + A[2*N - 1] > A[2] + A[4] + ...... + A[2*N - 2]

        Adding A[1] on the bigger side doesn't hurt :-) So

        A[1] + A[3] + ........... + A[2*N - 1] > A[2] + A[4] + ......... + A[2*N - 1].

        Similarly we can prove the same for the sequence O as well (looking at it in reverse order).
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it

sigh , I was trapped in Problem B for a long time
It seems so hard for me!!!

→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Why this code always gets "Presentation error test 1" ?
I rewrote my solution from C# program, which passed all tests.
→ Reply
14 years ago, # |
  Vote: I like it +5 Vote: I do not like it
In my opinion tasks weren't chosen reasonably. Only 30 people solved more than two. I think that contestants should be classified by number of problems solved rather than the time. First two tasks were ok, but it would  be better if third task was solved by 60-80 people, fourth by 15-30 and  fifth was extremely difficult. In this contest all three tasks were almost at the same level of difficulty.
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Well , I think problems must be difficult like this. The another div 2 - contests  have  easier problems .
    → Reply
14 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Brilliant problems. I love problem C. But couldn't anything have been done so that the solutions that choose randomly n boxes and check if they are good and repeat this until they get a solution aren't accepted?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Consider this data:
    1 0
    1 0
    ... (amount : n - 1)
    0 1
    0 1
    ... (amount : n)
    It can be calculated that the probably of get a possible answer is O(1 / sqrt(N))
    So the random algorithm 's expect time complexity is O(N sqrt(N))
    But we have the O(N logN) algorithm.
    We can make large data  , the random solution will get TLE.
    → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem D seems so hard for me. I just can't solve this one.can you give me some tips?
→ Reply
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Try this link: http://codeforces.me/blog/entry/530
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      I have another solution that got accepted. It is a little bit more connected to algorithms than applying some geometry observations:

      Lets number the midpoints 0, 1 and 2 and assume that 0 is the midpoint of the side that is equal to both of its neighbors. We know that we have a polygon vertex lying on the symetral  of 0, 1. I do binary search for this point A. For each candidate I do symmetry according to 0 and thus get point B. I have made the obvious observation that initially the points on the symetral of 0, 1 give us points B that are further away from 2 than 0, and then they become closer to 2. we are in fact interested in the moment in which the distances to 0 and 2 get equal. This allows us to make binary search.

      After we finish the binary we have two of the vertices of our polygon. What is left is to do 2 more symmetries and check whether the obtained polygon complies to all requirements.

      As a final note - in the beginning we assumed 0 is the center of the mid equal segment but in fact every of the three vertices can be that one. So we need to try all three possibilities to make sure no solution exists.
      → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
That's something wrong with the judge. I've got "Judgement failed".
→ Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
IMHO problem D has some troubles with precision.
After decreasing epsilon (used in vector product checking) from 1e-11 to 1e-9 solution was accepted...
→ Reply