Yandex.Algorithm 2011 - Qualification 1
By MikeMirzayanov, 14 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?
14 years ago, # |
← 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
  • 14 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Посреди рабочего дня можно найти 10 минут, чтоб сдать задачу, которой вполне может хватить, чтобы пройти, а на рейтинг это пагубно повлияет. Кто-то это уже где-то писал
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      А что дороже - рейтинг или квалификация Yandex Open?

      P.S.: Мы тут в английской ветке флудим.
      → Reply
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    It would be nice to have a page about this competition, the rules, the advancers and etc.
    → Reply
14 years ago, # |
  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
14 years ago, # |
← 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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    (this is similar to the debate about "IronMan" seeding in TopCoder)
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    Yes, it means newcomers which actually would have belonged to Div1 if they competed at CodeForces before had an advantage.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +25 Vote: I do not like it
    Yep, I thought about it just few minutes before the contest. In future, we will not use division-separation on tournament rounds.
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    → Reply
  • 14 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    → Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      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
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
        ← 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
        • 14 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          → Reply
          • 14 years ago, # ^ |
              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
            • 14 years ago, # ^ |
                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
  • 14 years ago, # ^ |
      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
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
          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
        • 14 years ago, # ^ |
            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
          • 14 years ago, # ^ |
              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
14 years ago, # |
  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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
HI, can anybody tell me how to solve C?
→ Reply
  • 14 years ago, # ^ |
      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
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
          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
  • 14 years ago, # ^ |
      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
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
What about rating? :)
→ Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it +37 Vote: I do not like it
    You don't have required rating to answer Petr, LOL. =)
    → Reply
    • 14 years ago, # ^ |
        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
      • 14 years ago, # ^ |
          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
        • 14 years ago, # ^ |
            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
          • 14 years ago, # ^ |
              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
14 years ago, # |
  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
14 years ago, # |
  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
  • 14 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it
    I ran your solution in custom testing and it outputs "1" as mentioned in juding protocol.
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oops. Sorry, I misunderstood interpretation of test result.
      Thanks.

      → Reply
14 years ago, # |
  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
14 years ago, # |
← 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
  • 14 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it
    Yeah, had to wake up 6AM to make it (UK time).
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it
      I did not sleep at all :) The contest started at 1.00am in Cuba.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it -12 Vote: I do not like it
        به آریو برزن:
        شما میباس صبحها بری مدرسه!!!
        نه اینکه تو خونه بخوابی
        از خودم یاد بگیر:D
        → Reply
        • 14 years ago, # ^ |
          ← Rev. 2   Vote: I like it +7 Vote: I do not like it

          不是每個人都明白你寫什麼。可能會更好地使用英語進行交流：）
          → Reply
          • 14 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it
            Haha...!
            It'd be nice to have a auto-translate option for comments in non-English. Using Google Translate API maybe.
            → Reply
          • 14 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            Come on guys. stop writing in Persian and Chinese. This is not nice really. Imagine what happens if everyone wants to write comment in his own native language? Do you enjoy that really?


            @Sajad: Call me Amir :) , I don't go to school. It's a waste of time :D

            → Reply
            • 14 years ago, # ^ |
                Vote: I like it +5 Vote: I do not like it
              Don't panic there:) the Chinese above is something like this:

              "Not everybody understands what you are saying here. If using English, maybe we could understand each other better this way."

              So you see, just a little in-joke for Chinese speaking people:)
              → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        you are cuban pepper))
        → Reply
14 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it


→ Reply
14 years ago, # |
  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
  • 14 years ago, # ^ |
    ← 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
    • 14 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      thank you very much!
      → Reply
    • 14 years ago, # ^ |
      ← 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
  • 14 years ago, # ^ |
      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
14 years ago, # |
  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
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    you are in list of registered
    → Reply
  • 14 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    Thanks very much, RiaD-WaW!
    Well, Actually I found my name in registrant list, but it didn't show register completed information in contest list. Maybe it's a bug, I think. 
    → Reply
    • 14 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it
      I just met the same problem. I think it's a trivial bug.
      → Reply
      • 14 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        Watashi...Orz...Orz...Orz...Orz...Orz...
        I saw you in FZ, and I sat opposite to you, lol......
        → Reply
14 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Really curious about will there be editorials for Yandex Open?
→ Reply
»
7 years ago, # |
  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