By MikeMirzayanov, 10 years ago, translation,

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

• +111

 10 years ago, # | ← Rev. 2 →   0 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) Если Вы квалифицировались в этом раунде - Вы можете участвовать и во втором квалификационном раунде, и он тоже будет для Вас рейтинговым.
•  10 years ago, # ^ |   0 Посреди рабочего дня можно найти 10 минут, чтоб сдать задачу, которой вполне может хватить, чтобы пройти, а на рейтинг это пагубно повлияет. Кто-то это уже где-то писал
•  10 years ago, # ^ |   0 А что дороже - рейтинг или квалификация Yandex Open?P.S.: Мы тут в английской ветке флудим.
•  10 years ago, # ^ |   +8 It would be nice to have a page about this competition, the rules, the advancers and etc.
•  10 years ago, # ^ |   0
•  10 years ago, # ^ |   0 I meant something more formal with subpages and a rich format.
 10 years ago, # |   +10         "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.
•  10 years ago, # ^ | ← Rev. 3 →   0 Ignore this comment
 10 years ago, # | ← Rev. 2 →   +3 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 "", line 1, in 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.
•  10 years ago, # ^ |   +3 I'll try to investigate this issue
 10 years ago, # |   +46 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.
•  10 years ago, # ^ |   +10 (this is similar to the debate about "IronMan" seeding in TopCoder)
•  10 years ago, # ^ |   +3 Yes, it means newcomers which actually would have belonged to Div1 if they competed at CodeForces before had an advantage.
•  10 years ago, # ^ |   +25 Yep, I thought about it just few minutes before the contest. In future, we will not use division-separation on tournament rounds.
•  10 years ago, # ^ |   0 Will use division separation for the next rounds?
•  10 years ago, # ^ |   0 It will be for typical Codeforces rounds, but not for tournaments.
•  10 years ago, # ^ |   +3
•  10 years ago, # ^ |   +3 why my above comment is not shown? is this a bug?
•  10 years ago, # ^ |   +3
 10 years ago, # |   +15 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 ??
•  10 years ago, # ^ |   +11 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.
•  10 years ago, # ^ |   -9 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.
•  10 years ago, # ^ | ← Rev. 2 →   +12 "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.
•  10 years ago, # ^ |   +5
•  10 years ago, # ^ |   +8 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.
•  10 years ago, # ^ |   0 Same problem. very confusing statements and I think none of the pretests were about the numbers.
•  10 years ago, # ^ |   +3 Hmm, for me, it means something like: if you have "12", you need to remove all-but-one spaces, so it becomes "12". 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 :(
•  10 years ago, # ^ |   +3 Are you sure? I took the statement as "one number will be removed." and my solution hacked by "59". and also I successfully hacked a solution with:"3464574575367357467457536834564683556,...,...,56,456,...,"So the statement was matter.
•  10 years ago, # ^ |   +3 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
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   0 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 :)
 10 years ago, # |   +6 Oops(a < b && t[i] > cutOff) || (a > n && t[i] < cutOff)and I've tested in on many cases :)
 10 years ago, # |   0 HI, can anybody tell me how to solve C?
•  10 years ago, # ^ |   0 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
•  10 years ago, # ^ |   0 i can't guess this statement " then guess that if b > a, then ai sould be >= bielse if a < b ",can you explain me?
•  10 years ago, # ^ |   0 lets try to prove that for 2 numberswe 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
•  10 years ago, # ^ |   +8 S1 / A + S2 / B ->maxS1 + 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 S1if A > Bwe 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..
 10 years ago, # |   0 What about rating? :)
 10 years ago, # |   0 I am not able to reply to petr's post. is it a bug?
•  10 years ago, # ^ |   +37 You don't have required rating to answer Petr, LOL. =)
•  10 years ago, # ^ |   0 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.
•  10 years ago, # ^ |   +13 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).
•  10 years ago, # ^ |   0 For div 1 contestants its easy to hack div 2 coder's code. But its not as easy for div 2 coders.
•  10 years ago, # ^ |   0 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.
 10 years ago, # |   -12 The server was too slow, I can't submit any problem for 50 minutes. Anyway, good problemset.
 10 years ago, # |   0 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?
•  10 years ago, # ^ |   +5 I ran your solution in custom testing and it outputs "1" as mentioned in juding protocol.
•  10 years ago, # ^ |   0 Oops. Sorry, I misunderstood interpretation of test result.Thanks.
 10 years ago, # |   +1 Can anyone help me to figure out why his code for ARuntime error on test 12
•  10 years ago, # ^ |   +1 Try test:abc
•  10 years ago, # ^ |   +1 Thanks a lot, I am too careless
 10 years ago, # | ← Rev. 2 →   +19 Hope to see no more morning-contests :)It's really hard to wake up before 11:00
•  10 years ago, # ^ |   +8 Yeah, had to wake up 6AM to make it (UK time).
•  10 years ago, # ^ |   +17 I did not sleep at all :) The contest started at 1.00am in Cuba.
•  10 years ago, # ^ |   -12 به آریو برزن:شما میباس صبحها بری مدرسه!!!نه اینکه تو خونه بخوابیاز خودم یاد بگیر:D
•  10 years ago, # ^ | ← Rev. 2 →   +7 不是每個人都明白你寫什麼。可能會更好地使用英語進行交流：）
•  10 years ago, # ^ |   +3 Haha...!It'd be nice to have a auto-translate option for comments in non-English. Using Google Translate API maybe.
•  10 years ago, # ^ | ← Rev. 2 →   0 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
•  10 years ago, # ^ |   +5 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:)
•  10 years ago, # ^ |   -8 یو برخودم یڧڬۏڧڬینکه ڧ
•  10 years ago, # ^ |   0 you are cuban pepper))
•  10 years ago, # ^ | ← Rev. 2 →   +2 NO NO NO! He is pepper from KUBAN!!!
•  10 years ago, # ^ | ← Rev. 3 →   0 you're certainly right)
 10 years ago, # | ← Rev. 2 →   0
 10 years ago, # |   +3 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.
•  10 years ago, # ^ | ← Rev. 3 →   +9 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.
•  10 years ago, # ^ | ← Rev. 2 →   0 thank you very much!
•  10 years ago, # ^ | ← Rev. 2 →   0 >> 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 ?
•  10 years ago, # ^ |   +10 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.
•  10 years ago, # ^ |   0 you answer is also clear
 10 years ago, # |   +11 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!
•  10 years ago, # ^ | ← Rev. 2 →   +11 you are in list of registered
•  10 years ago, # ^ | ← Rev. 2 →   +13 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.
•  10 years ago, # ^ |   +8 I just met the same problem. I think it's a trivial bug.
•  10 years ago, # ^ |   0 Watashi...Orz...Orz...Orz...Orz...Orz...I saw you in FZ, and I sat opposite to you, lol......
 10 years ago, # |   0 Really curious about will there be editorials for Yandex Open?
 » 4 years ago, # |   0 Hi, can someone give me some hints for problem D? I have got to ask since there is no editorial available. Thanks in advance.