Yandex.Algorithm 2011 - Qualification 1
By MikeMirzayanov, 15 years ago, translation, In English

Hello.

This round will start Yandex.Algorithm 2011. The problems of the round were prepared by me, of course, with the help of the Codeforces team and Yandex.

I hope you enjoy the problems and their solution will start a successful performance at the tournament.

As you have already noticed — the system operates in a somewhat truncated form. We decided to run it in safe mode and turn off some functionality at the time of the contest. After the round everything will be back.

I recall that the top 500 participants will receive a ticket to the first online round of the Yandex.Algorithm. However, if you do not get to qualify at this time, do not despair — you can participate in the second qualification, which will be held on May 6 at 15:00 (UTC).

I wish you have a fun,
MikeMirzayanov

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

Comments Comments (76)
| Write comment?
15 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

Round FAQ:
1) Round will be rated (affects rating).
2) Rules are Codeforces standard rules. Please read them carefully!
3) Also be sure you are registered for the contest! Find yourself here.
4) If you passed this qualification - you can participate 2nd qual. and it also affects your rating.

===

FAQ Раунда:
1) Раунд рейтинговый.
2) Правила: стандартные правила Codeforces, прочитайте их внимательно!
3) Проверьте свою регистрацию на соревнование! Найдите себя здесь.
4) Если Вы квалифицировались в этом раунде - Вы можете участвовать и во втором квалификационном раунде, и он тоже будет для Вас рейтинговым.
→ Reply
15 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it
        "The registration will be opened during the whole contest."

This was written in the email which was sent to me about this round, but I see that the registration is closed.
→ Reply
15 years ago, hide # |
← Rev. 2  
Vote: I like it +3 Vote: I do not like it

During the last minute of the contest, I tried to hack with a Python generator submitted as a file named "tt". Had no time to name it nicely.

I've got the following error.
-----
Traceback (most recent call last):

  File "<string>", line 1, in <module>

IOError: [Errno 2] No such file or directory: 'tt.py'
-----
So, the server tried to open "tt.py" when the file was named just "tt".

I believe it's not the intended behaviour. Will it be corrected?

UPD: The test is incorrect anyway, so it won't affect the results.
→ Reply
15 years ago, hide # |
 
Vote: I like it +46 Vote: I do not like it
Thanks for the contest!

There's one thing that confuses me: were contestants still separated by division? If yes, it looks unfair because tournament advancement may be easier if you're in div 2.
→ Reply
15 years ago, hide # |
 
Vote: I like it +15 Vote: I do not like it
What is the problem with u guys(codeforces or ....).Why problem statement is so confusing.What does it mean ?

"if two consecutive numbers were separated by spaces only (one or more), then exactly one of them should be left" 

what does it mean =>
---- It means one number will be removed.
---- It means one space will be removed.
---- It means all spaces except one space will be removed. 
During contest i submitted with the second explanation above & i got Pretest passed.
Now if i get WA for this reason is it my problem ??
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +11 Vote: I do not like it
    I took it as one number will be removed. I was confused whether which number to remove.
    I bet on the left one and got WA . I was dumb enough to not able to think one space will be removed. Though i still don't know what is the correct one from your three choice.
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it -9 Vote: I do not like it
      It is quit normal for anyone to be confused.
      If codeforce can't translate problem statement into English so what is the meaning to set a contest in english version.
      → Reply
      • 15 years ago, hide # ^ |
        ← Rev. 2  
        Vote: I like it +12 Vote: I do not like it

        "Polycarp wants to add and remove spaces in the string s to ensure the following:"

        It is written in the statement. I was also thinking a while about this point, but the statement is ok.
        → Reply
        • 15 years ago, hide # ^ |
           
          Vote: I like it +5 Vote: I do not like it
          → Reply
          • 15 years ago, hide # ^ |
             
            Vote: I like it +8 Vote: I do not like it
            I can not copy paste it here but there is my clarification and the answer:
            Please broadcast a message about the spaces as if two numbers are separated only by spaces ... exactly one of them should be left - this may refer to numbers.
            Answer:
            1. "Polycarp wants to add and remove spaces in the string ... "
            You are not allowed to do anything else (remove numbers etc.), only add and remove spaces.

            2. In every sample test removing numbers doesn't work.

            3. There were no other such questions.
            → Reply
            • 15 years ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it
              Same problem. very confusing statements and I think none of the pretests were about the numbers.
              → Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +3 Vote: I do not like it
    Hmm, for me, it means something like: if you have "1<space><space>2", you need to remove all-but-one spaces, so it becomes "1<space>2". I try to challenge other by this case, but it is an invalid case. Now, my conclusion is: we don't need to understand that sentence in order to solve this problem :(
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it +3 Vote: I do not like it
      Are you sure? I took the statement as "one number will be removed." and my solution hacked by "5<space><space><space>9". and also I successfully hacked a solution with:
      "3464574575367357<space>4674575368345646835<space>56,...,...,56,456,...,"
      So the statement was matter.



      → Reply
      • 15 years ago, hide # ^ |
         
        Vote: I like it +3 Vote: I do not like it
        How come :( yeah I'm pretty sure that I tried to challenge other by that case, and I couldn't as it show: invalid case... That's why I thought that numbers should be separated by "," or "..." and stop making other challenge. Grrrr I should have many successful challenges
        → Reply
        • 15 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it
          Check your hack, you will see this message: "FAIL Expected EOLN (stdin)"
          You didn't press "Enter" key. The input should end with end of line character. At first I had same problem.

          → Reply
          • 15 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it
            I think I pressed "Enter" (this time I'm not so sure), and there was no explanation except "invalid case". Anyway, it's ok for me :)
            → Reply
15 years ago, hide # |
 
Vote: I like it +6 Vote: I do not like it
Oops

(a < b && t[i] > cutOff) || (a > n && t[i] < cutOff)

and I've tested in on many cases :)
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
HI, can anybody tell me how to solve C?
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it
    we have to Max
    ( a1 + a2 + ... + aa ) / a + ( b1 + b2 + ... + bb ) / b

    to common divisor
    ( b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) ) / a*b <= cnst

    b * ( a1 + a2 + ... + aa ) + a * ( b1 + b2 + ... + bb ) --> max

    then guess that if b > a, then ai sould be >= bi
    else if a < b

    if a == b we must output 1 1 ... 1 1 2 2 ... 2 2
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      i can't guess this statement " then guess that if b > a, then ai sould be >= bi
      else if a < b ",can you explain me?
      → Reply
      • 15 years ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it
        lets try to prove that for 2 numbers
        we have a, b and numbers x and y (let x > y)

        ax + by - ay - bx = (a-b)(x-y)
        x - y > 0, so if a > b and a - b > 0, ax + by - ay - bx  > 0

        and finally ax + by > ay + bx
        → Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    S1 / A + S2 / B ->max

    S1 + S2 = total sum of all a[i]

    if A = B then output 1 1 1 ... 2 2 2

    if A > B we need to maximize S2, else S1

    if A > B

    we need to sort array of marks, S1 = a[1] + a[2] + ...+ a[A], S2 = a[A + 1] + ... a[A + 2] + ... +a[n]

    we can count how many marks 1 we must to include in S1, how many marks 2  we must to include in S1.. 


    → Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
What about rating? :)
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
I am not able to reply to petr's post. is it a bug?
→ Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +37 Vote: I do not like it
    You don't have required rating to answer Petr, LOL. =)
    → Reply
    • 15 years ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it
      Lol. Actually I am able to post it but after publishing it is shown as a blank comment.
      My comment was:
       As top  500 will be selected from overall ranking table. then how is it easier for div 2 users ?
      Or you are just considering the fact that hacking is easier in a Div 2 room ?
      Correct me if I am wrong.
      → Reply
      • 15 years ago, hide # ^ |
         
        Vote: I like it +13 Vote: I do not like it
        Yes, I was referring to the fact that hacking is usually much easier in a div 2 room (if the same contestant were to hack there).
        → Reply
        • 15 years ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it
          For div 1 contestants its easy to hack div 2 coder's code. But its not as easy for div 2 coders.
          → Reply
          • 15 years ago, hide # ^ |
             
            Vote: I like it 0 Vote: I do not like it
            If I'm a new but experienced contestant (or I created new account), I can get much-much points from hacking.

            But I thought it was obvious.
            → Reply
15 years ago, hide # |
 
Vote: I like it -12 Vote: I do not like it
The server was too slow, I can't submit any problem for 50 minutes. Anyway, good problemset.
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
My solution of problem B (#427173) had WA on test 8.
But, it returned correct answer on custom test with input of test 8.
Why did such a thing happen?
→ Reply
15 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it
Can anyone help me to figure out why his code for A
Runtime error on test 12

→ Reply
15 years ago, hide # |
← Rev. 2  
Vote: I like it +19 Vote: I do not like it

Hope to see no more morning-contests :)
It's really hard to wake up before 11:00
→ Reply
15 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it


→ Reply
15 years ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

can anyone tell me how to solve the problem E.

although it has tag of tree and dp, but i think it is not a tree, how can we to solve it with tree dp.

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

    1). Lets choose some person and walk to its' friend, to a friend of a friend and so on. Obviously, at some point we will receive a cycle. So, generally, our graph ( nodes=people, edges=friendship) is divided into cycles with som "tails" whom which you can go into the cycle by edges. 

    2). Let's traverse every edge. Cycle remains cycle and from some nodes on a cycle we now can go to some other nodes, possibly from one node to few different nodes. So actually our figure is a cycle with oriented trees that "hang" on the nodes of cycle.

    3).For each tree compute the following DP: 

    F(i,0) = maximum number of pairs we can choose from subtree of i we we don't use i in any pair.
    F(i,1) = the same if we match i with some of its descendants.

    Obviously, F(i,0)=sum(max(F(Child i,0), F(Child i,1))) for each child of i.
    Obivously, F(i,1)=max(F(i,0)-max(F(Child i,0), F(Child i,1))+F(Child i,0)+1) for each child of i. (We loop through all children of i and try to pair i with that child).

    4). Now we have two options: to match last node of a cycle with first one, and not to match. In both cases we then delete our edge from last to first node and we get a chain. We perform almost the same DP on this chain:

    G(i,0) = F(i,0)+max(G(i-1,0),G(i-1,1)) - we don't match i-th node with anything.
    G(i,1) = max(F(i,1)+max(G(i-1,0),G(i-1,1)), F(i,0)+1+G(i-1,0))
    For G(i,1) we have to options: we either match our node with some node in its subtree (first value in max) or match it with previous node in cycle and add F(i,0).

    In case if we match 1-st and last node, G(0,0)=-infinity, G(0,1)=1+F(0,0) and the answer is in G(n-1,0), because n-1-th vertex can not be matched with previous node as it is already matched with the first one.
    In case if we don't, G(0,0)=F(0,0), G(0,1)=F(0,1) and answer is max(G(n-1,0), G(n-1,1)).

    Also, to make it easier, I wrote about DP that just returns maximum number of pairs but I hope it is obvious how to turn in to DP that returns maximum number of pairs|maximum number of boy-girl pairs.

    Hope this helps!

    PS. Solution below is better because it is easier and uses only one DP instead of two.
    → Reply
    • 15 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      thank you very much!
      → Reply
    • 15 years ago, hide # ^ |
      ← Rev. 2  
      Vote: I like it 0 Vote: I do not like it

      >> S. Solution below is better because it is easier and uses only one DP instead of two. 

      In such case your approach has to be more general than approach formulated below. 
      If no, than your approach should be just more complicated and doesn't solve more general class of such problems ? Can you clear it ?
      → Reply
  • 15 years ago, hide # ^ |
     
    Vote: I like it +10 Vote: I do not like it

    Each connected component in the graph has exactly one cycle. Pick any edge from the cycle and remove it from the graph, now we should consider two cases: a picked edge is in the answer and it isn’t there.  Both cases can be easily solved with dp on tree.

    → Reply
15 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it
Hi!
I don't know why I can't register Qualification 2.

It said that I had already qualified into the competition, and let me choose whether I want to register as OUT OF COMPETITION participant. I choosed "Yes", but it didn't work, I still can't register this competition.

Anyone can explain this and help me? Thanks a lot!
→ Reply
15 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it
Really curious about will there be editorials for Yandex Open?
→ Reply
»
8 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Hi, can someone give me some hints for problem D? I have got to ask since there is no editorial available. Thanks in advance.

→ Reply