Лиса Ciel возвращается!
Все приглашаются поучаствовать в Codeforces Round #290, который начинается в обычное время в ближайший понедельник.
Это мой четвёртый раунд на Codeforces, можете ознакомиться с моими предыдущими раундами: #190, #228, #270.
Последний Div1-раунд (#286) оказался очень непростым, поэтому мы решили уменьшить сложность раунда (например, Div1-E превратилась в Div1-D). Надеюсь, это позволит большому количеству людей насладиться всеми задачами раунда: в этот раз ни одна задача не требует продвинутых знаний наподобие линейной алгебры или преобразования Фурье.
Главным персонажем раунда будет Лиса Ciel и её жизнь: она учится программировать, играет, путешествует, принимает ужин, а также делает многое другое.
Как и на раунде #228, топ-20 участников, присутствующих на зимних сборах в Петрозаводске, будут награждены футболочками Codeforces. Футболку может получить любой участник сборов, член жюри, тренер, организатор или любой другой человек, так или иначе присутствующий на сборах.
Как обычно, спасибо Zlobober за ценные советы и помощь в подготовке моего раунда, и MikeMirzayanov за платформы Codeforces и Polygon.
Удачи!
Update1: Score Distribution is ... Div2: Standard (500 — 1000 — 1500 — 2000 — 2500), Div1: a bit unusual ... (500 — 1000 — 1500 — 2250 — 2250)
Update2: Editorial: http://codeforces.me/blog/entry/16173
Update3: Congratulation to our winners:
Div1:
They are all people who solved 5 tasks!
Div2:
Nice! I love your contests! Always I think that a little easier problems are better.The best programmers will certainly be in their place,and other competitiors will get more fun.
i'm not in Petrozavodsk training camp, but i want t-shirts too :)
ooops sorry, i just kidding.
"advanced knowledge like linear space" :P
hmm, i always thought that Bredor was the author of Round #228. ;)
Look at his head carefully in his profile photo :)
Doesn't using the current Div1-E as Div1-D make it harder, not easier? The D task will be hard as E task, and E task will be even harder!
It means the previous D will be the current E.
actually, minimario's translation was correct. It seems that the author has his wording wrong.
Maybe you are right, I'm not good at grammar. Then how to express it properly?
I parsed it as "the upcoming Div1-E was initially supposed to be Div1-D". But the points is this round is going to be easier than the last Div1 round, at least according to the author.
The contest is from China. The time is 19:00 in Russia it means 00:30 in China! an it will last for two hours that is 2:30 AM! Will you be awake that time? :D
Anyway, Thank you for the contest... It's my 100th contest and I'm really scared because my rating change in your last contests was : -54 , -74 , -127 :D
UPDATE : This time my rating change was -106 :|
cgy4ever...
Afaik, cgy4ever is from China, but not in China.
It start at 8:30 am here (California), I hope I can get up at that time.
We all get used to competing programming contests at late night, since almost all contests of Topcoder, Codeforces, Hackercup and GCJ are hosted on bedtime in China (UTC+8). So I'm sure cgy4ever would be awake if he were in China (But he is in US now, Chinese topcoders always get up late :P).
.
next one -213
last time your rating change was -127,this time -106, so that's an improvement by +21 !!!
Didn't provide much help to Fox Ciel in last round . Will try to impress Fox Ciel atleast this time
Thank you for making this contest :)
YES
A CGY4EVER ROUND
!!!
finally a Div 1 + Div 2 round after 4 continuous Div 2 only rounds :)
Congratulations on advancing to the onsites of Facebook Hackercup cgy4ever.
Thanks!!
Now I've advanced to nearly all big onsite finals at least once: GCJ(2011), TCO(2013,2014), Yandex(2014, but can't participate due to visa issue), FHC(2015) and ICPC(2015).
~~~~~~~~
you did it once before, i believe you can :)
twice :P
I did it!!
Посмотрел предыдущие раунды, я в них не участвовал, но тем не менее имя лисы Ciel кажется знакомым..
UPD: Ошибка, оказывается я участвовал в 270 раунде, но при открытии ссылки на него из анонса — открылась страница, на которой меня разлогинило, поэтому и не нашел себя в участниках раунда.
Да на топкодере миллионы задач с Ciel
Я слишком плохо знаю английский, а с гугл переводчиком я участвую только в официальных соревнованиях facebook и google.
I've registered but I might not be able to participate. Will my rating be affected if I never even open the contest page? (like on TopCoder).
Your rating is not affected if you don't make any submission. (You can open the problems and decide to leave if you don't want to submit without any rating change.)
I wish good rating for all
But that will never happen :(
I Love my rating :
1616 :))
then you shouldn't participate in this contest or your rating will change :)
Maybe it change to 1717:)
17 — it's not good number. Need 3232 or 88 =)
need 228 :D
I see, you decided to make this rating. It is more easier than make 1616 or 1488.
Maybe his/her rating change will be 0 :)
Shame on you :(
Why ?
Why? because Shakespear died on that year?
Dixtosa Giovanni Battista Agucchi died in 1632 :p
No, He died on 1623 :)
hoping to taste div1 after the competition
Its good that its two division contest, otherwise merging it results in some weird rating change like #270 and GoodBye 2014 because too many top coders registered for this round.
My first contest, wish me luck.
My first Div1 contest, wish me luck.
Get ready to rumble!
Good luck
Wow, over 6000 registrants in total. Can CodeForces handle it?
Apparently no. I cannot open the first problem.
Why I can't hack other code?
Make sure you locked your solution for that task first.
And make sure you are in the same room with that person.
He's only submitted problem A. And I really can't think of a bug someone would have in coding such a problem. :) I think he asked why nobody has made mistake in implementing A. :D
That feeling when you hacked tourist :))
Liar!
No it was mkirsche that hacked tourist, Ximera was just pointing it out. I was also confused at first.
That alone made this a successful contest as far as I'm concerned. :D
Oh! TAT! In my room,only I locked the code!And I was waiting a coder locked his code then I will hack him! But when I found a coder has locked his code,he used java and I can't hack him.I am so sad! Maybe I should average up and I can go to the div1....
You can hack any solution, not only those that are locked. (Of course, hacking an unlocked solution means the owner can still get to fix it.)
what was the hacking case in div-1 A
2 bacrr bac
it should be impossible
thnx missed it completely ....and got hacked :(
I handled this case, still got WA in test 12 :(
same :(
Then try test 3 a ba bb. You may have counted one inequality twice.
I did that as well. Still WA in test 12. :(
same :( :(
Try this 5 page ping pile care array
ans is not impossible
Have you guys figure out test 12 yet? I cannot see the whole dataset.
Possibly it is
But I am not sure if it is a valid test case
I suppose something like 2 abcx abc
What's test 12 for Div1-A?! I can't see full test. It's a huge test and shows "...". I try all of the special test cases mentioned in this post but my code still shows "Impossible" instead of "abcdefghijklmnopqrstuvwxyz" (the answer for the test 12). Here's my submission: 9688819
Как ломали DIV1 А? Подскажите.
2 ab a
impossible
Спасибо. Плохой тест. (((((((((
2 aa a
So what's the solution for D?
It seems that we need to ignore nodes contained in a cycle, and do a DP on the resulting forest. I had a O(N4) DP for solving a single tree, but I'm afraid it would TL (especially with recursion). Then I thought that to count the number of eliminations of size k, we need to count the number of subtrees of size treesize - k, which results in a O(N3) DP, but that totally ignores the order of elimination. Is there a O(N3) solution after all?
To solve a tree of size S I used this algorithm: for each node, find the number of ways to remove K nodes such that the node is not removed (if K < S) or is removed last (if K = S). Then an ending subtree of size N is counted N times (once by each of its member nodes), so we adjust for overcounting by dividing by N.
O(N4) with 3 seconds TL (and nothing else that could have the same complexity) and only in one small loop? Plus with O(N3) memory? I'm pretty sure it would work if you don't do something utterly stupid.
For some reason I still have the impression (from sometimes before) that anything more than 108 is slow. Time to forget that and move on :)
Depends on what it is. Processor instructions: no. Actually 4 times (common with DP) less simple C++ instructions: no. Insertions in a map of constant size: probably yes.
It's better to risk it and find out in such a case.
We should exclude not only cycles but some other vertices too, for example if cycle is conected to another cycle etc.
We have rooted trees (connected to some bad vertex), and unrooted trees... and well I in both cases we can compute the answer using dp in N^3. Then we can join answers for trees using binomial coefficients in O(TN) where T is number of trees.
But I didnt have enough time to debug my solution, so maybe it's wrong.
What I meant was that we should exclude nodes that are part of some cycle. That includes your case :)
Yeah, I think you were doing it the right way.
Как решать В?
За минут 40 до конца я понял, что нужно выбрать набор чисел, у которых НОД равен 1. Развить это до адекватного решения не смог.
Я понял это по третьему примеру за 5 минут. Пытался придумать умное целый час, забил, написал тупой перебор. Претесты прошло. Финалы зайдет или нет не знаю, но gcd быстро убывающая функция
У меня тоже перебор претесты прошел, но перебор 300^8 (я сделал вывод о том, что больше 8 чисел нам никогда не надо будет выбирать, хотя на самом деле 9 или 10 еще может быть). И перебор этот я писал за 12 минут до конца, просто чтобы хотя бы хоть что-то сдать и вдруг повезёт.
Я сразу понял, по одной очень известной теореме о НОД, что наименьше число, представимое в виде линейной комбинации чисел и есть НОД.
Если ты можешь на каком-то наборе получить 1 в виде линейной комбинации, то из этого следует, что НОД этих чисел равен 1. А если можешь получить 1 — то можешь получить всё, что угодно.
Потом понял, что задача на динамику, но так и не дошло, какая именно динамика-то :(
В связи с этим, фраза "в этот раз ни одна задача не требует продвинутых знаний наподобие линейной алгебры" выглядит как издевательство.
"Последний Div1-раунд (#286) оказался очень непростым, поэтому мы решили уменьшить сложность раунда (например, Div1-E превратилась в Div1-D)." Я долго думал над этой фразой, и понял, что здесь что-то не так с логикой, если более сложная задача стала ближе к началу, то значит контест усложнился? Но почему же тогда пишут, что решено сложность уменьшить :(
Ты еще не C не видел. Там поток. В начальной школе проходят.
я сделал дп на мапе dp[N][достижимые_gcd] = минимальная_стоимость, но очень сомневаюсь, что такое пройдет.
Пройдет. Возможных состояний — не более ND, где D = 29 — максимальное количество делителей числа. Переходов из каждого состояния О(N), по одному для каждого числа. Можно также было ускорить, храня только уникальные делители (D = 9)
UPD: Оценка на D неверна, см. ниже
Спасибо =) Можете доказать, почему состояний не более ND?
Рассмотрим любое конкретное число. Все возможные достижимые из него состояния будут его НОД с некоторым подмножеством чисел. Любой такод НОД будет его делителем. Всего чисел N. Отсюда оценка ND. Правда, я неверно определил D:
D не равно 29, D порядка O(X1 / 3), потому что такая типичная оценка на количество делителей числа (X ≤ 109).
Если рассматривать только простые множители числа в первой степени, то можно гарантировать, что их не более 9 (2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23), а значит возможных комбинаций делителей не более 29
Откуда такая оценка?
Интуитивно понятно, что в целом достижимых состояний будет мало, но ведь у одного числа делителей может быть намного больше, чем 29.
Да, ошибся, см. комментарий выше
Я сдал так.
Переберем последнюю взятую карточку. Заметим, что количество различных простых в l[i] <= 10. Для каждого из них нам надо выбрать карточку, которая не делится на него. Посчитаем динамику dp[k][mask] — минимальная стоимость, если мы взяли что-то из первых k и при этом "убили" простые, помеченные в mask. Переходы очевидные: или мы не берем очередную маску, или берем и убиваем соответствующие простые в маске. Итого n * n * 2^10 — примерно 9e7
Но при этом усложнить Div1-A до Div1-B, а про Div1-B я вообще молчу...
great contest i'm waiting for your next contest thank you
Last minute, CF was down! I couldn't submit my
Asolution :( Actually I solvedAbut I was waiting for solving another problem too, after I submittedBand Got Pretest Passed, I wanted to submitAtoo. Which is now undone thanks to codeforces :Di wrote a submission for b, but haven't ten more secs to submit(
my last round i submitted C 2 minutes before the end.) nevertheless, i need more time to get div1 membership :/
what was the solution for div1 b or div2 d? I tried pd with a knapsack, but the numbers were to big i think for that. Are there some tricks for big numbers? or is there another approach?
A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n. Since we want that to apply to all n, then the GCD should be equal to 1. The solution is DP with state (i, GCD) (last used card and current GCD of cards). We can use a map to store the states since the number of different possible GCDs is quite small.
that was also my idea, but forgot the fact that the number of GCD is small. thanks!
How to prove that the number of different GCDs is quite small?
Because it should be the divisor of some number ai and ai ≤ 109. Numbers in that range can't have many divisors (less than 100 I believe). EDIT: Ooops, my guess was wrong, thanks for correction Andrei1998!
In fact, 735134400 has 1344 divisors, so a safe guess would be 1500.
"linear diophantine equation" is probably an overkill ;-)
Basic number theory: Given x and y, their smallest positive integer linear combination spc(x, y) is given by sx + ty = spc(x, y) = gcd(x, y). You just need to find the minimal cost subset such that spc(a1, a2, ..., ak) = gcd(a1, a2, ..., ak) = 1.
Note that gcd converges quickly as the subset size increases, assume that integers in the subset are distinct.
Overkill or not, it's how that type of equations is called. Then again, anyone who has done a bit of number theory knows what a diophantine (I imagine the name doesn't sound horribly different in other languages) equation is, not to mention linear.
"A linear diophantine equation: a * x + b * y + ... = n has a solution if and only if GCD(a, b, ...) divides n"
Is there a proof for this?
I can't find one right now, but this might help (see generalizations):
http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity
Left side can be divided by GCD(a, b, ...), so should right.
Yes, you are right, the gcds are too big to do dp with them, but the right thing to do there is to note that the number of useful gcds is small enough (my calculation ended up being ~60000 different gcd's), so you can map them to 1-60000 and then do dp.
thanks! unfortunately, i'm not used to mapping and tried some tricks with big numbers, but they didn't work...
i definitely have to learn how to map
Best message ever :v (And definitely, I didn't submit that -_- )
thanks for A. sweatest shit I ever eaten...
WOW you have eaten shit ???
-YES FROM YR MOTHERS BUTT
Сum on!
Have you paid for Visual Studio ? :-)
Yep, obviously, and for uTorrent too
and Sublime :D
It's freely available to students (under some usage restrictions). Say, if you have ISIC card (or another proof of enrollment), you are eligible for DreamSpark program which includes a lot of Microsoft software free of charge (not for commercial usage, of course).
Div1 A
What's the answer for:
?
All the names are distinct.
There is no equal strings.
names should be unique
Didn't the specs say that the words are different?
Sorry, didn't notice that. I thought it will fail. Whew.
This problem can be solved by graph cycle detection, right? I didn't have time to finish the code.
Cycle detection -> impossible
Else, topsort
i thought the same :) .
Это у всех сайт очень тупил? Первые 5 минут он не работал, когда начал работать уже поздавали А. И так весь контест 5 минут работает, 5 минут нет. И последние минуты тоже не работал.
Да и вообще сайт нестабильно работает в последние дни, не только во время контеста. У меня такой режим "5 минут работает, 5 нет" почти постоянно.
Upd. После консультации с MikeMirzayanov, диагностики и опроса других пользователей пришел к выводу, что проблема на стороне провайдера в отеле на сборах в ПЗ, а не на стороне сервера СF.
How to solve Division1 C? Task looks like a Euler path, but I don't know how to solve it.
Although i have not participated in the contest but i think this problem can be solved using topological sort this way . Please correct me if i am wrong some where ..
We can take each pair of string and find the first miss match then we put a directed edge from one character to the other (offcourse miss match pair is taken) then find whether there is a cycle or not in the graph . if there is a cycle then it is impossible otherwise find the topological sorting .
He asked for Div1-C, not Div2.
No, a set of cycles.
You can notice that any two neighbours need to have different parities, so you have a bipartite graph describing possible neighbourings; you want to match each vertex of each partition to exactly two other vertices.
ai >= 2. Yep, only even lenght, I miss this restrict. Thx
Is it correct to find one bipartite matching then remove the edges of this matching from the original graph and find a second matching? I wrote the solution and it passed the sys.tests, but I couldn't prove it's correct.
It's not correct. Try test:
6
10 2 26 5 3 9
or its permutations. System tests are weak.
UPD: The following proof that we need two perfect matchings is correct, but finding two perfect matchings sequentially does not always work.
"=>"
Each breakdown of graph into cycles can be divided into 2 sets of edges, "left-to-right" and "right-to-left". Each node from left and right part has exactly one edge of each type incident to it. Therefore, each of such sets of edges forms a perfect matching.
"<="
For a pair of two edge-disjoint perfect matchings we get a set of edges such that each node has exactly two incident edges. Since the degree of each node is even, there exists an euler tour in each connected component. Each connected component has exactly K nodes and K edges, therefor the tour is also hamiltonian. Since each node has at least two edges, each component has > 3 nodes.
A flow solution finds this order: 1 5 3 4 2 6
Ah, I see. So the idea about two perfect matchings is correct, but finding them sequentially does not always work.
The answer exists:
9 10 3 26 5 2
For D1-A, what is the correct answer for this case?
According to this sentence:
But it was always true that after some modification of the order of letters in alphabet, the order of authors becomes lexicographical!
Should the answer be
Impossible? Since you cannot do any modification to make them lexicographical...I think this problem is ambiguous on this case. Could the author clarify?
Edit: well my solution outputs
abc...zon this case. However, my friend's outputsImpossible, because he was struggling to resubmit his hacked solution on this multiple times without success, to the point that he thought the wording of this sentence was actually the tricky case.Identity modification :).
some modification usually means no modification too.
No the answer is just the normal alphabet. I think this is pretty clear.
Aren't they already lexicographically sorted? Edit: Oh, I see what you mean.
Did somebody made mistake of writing "Impossible" as "impossible"? :P
would that pass the pretests?
Of course, no.
Obviously not, as the answer for one of samples is 'Impossible' :)
Me!
I accidentally wrote impossibru though
i made mistake of writing "YES" instead "Yes" :)
How is Div1 B solved?
Thanks a lot for the nice C problem :) It is clear experienced coders must have seen it before but I was happy once I figured out the max flow solution. Then, I ran out of time because I didn't know how to restore the flow, and had to spend some time debugging >.<
Very nice problems cgy4ever, thank you :)!
Thanks for this round. Though my rating will decrease I learnt a lot . Hope you will be setting problems frequently .
Did anyone else wrote randomized algo for Div1 E? (・_・ヾ If my solution pass, I would probably look like (☉_☉')
Edit: It failed (˘_˘٥)
DamianS got his random solution accepted.
What a bloodbath on div1 A! I missed the opportunity of being hacked.
Я специально обработал этот случай, бугуртил, читая в семпле "аккуратнее, не прозевайте ВОТ ЭТОТ САМЫЙ случай", и что я сделал?
My code (codeforces.com/contest/512/submission/9686628) got accepted but it writes "Impossible" with this simple input: 2 a a :))
Because all strings are different :)
2 a a is wrong test: "All names are different."
Thank you for such a wonderful contest!!
Finally in top 5! Congratulations to winners and big thanks to those who created this nice contest for us.
Best contest since I am on codeforces :) Thank you :)
Codeforces was working perfectly during last 10 minutes. I've read so many codes, challenged so many people during that time! To help u guess how many, i say that factorial of this number is 1
so 0 or 1 ?
Contests -> Click at place.
0
Great contest with good problems,I just didn't know about 'topological sort' before the contest,and learn it during the contest ;)
Very nice problems. And finally I can become international grandmaster, really excited!
My short sad story:
I had A and B and it was like 15 minutes to the end. I didn't have any good idea for C/D/E so I wrote some simple greedy-random solution to E but I wasn't able to submit it during last 2 minutes. And now my code from contest passed all tests: link to solution
Ofc. AC with this solution would be a bit unfair but still I'm just sad... 155-th place vs. ~24-th place :(
Why is this Div 1 B solution failing the system test cases. Please Help. http://codeforces.me/contest/512/submission/9690331
So easy question... Cause answer was wrong :|
Are you sure it's okay to modify the container which you are currently iterating over? I guess that could be the source of the bug.
I used unordered maps. So I guess it shouldn't modify the container which i am currently iterating over.
Iterators are invalidated when you insert into unordered_map: http://en.cppreference.com/w/cpp/container/unordered_map/operator_at. Try to replace by std::map.
My goodness :D ... I chose to use unordered_maps other than maps at the last moment... God has been very kind to me :D ....Thanks anyway for finding the bug :D
Won't there be a rating change for this round?
Still Pending
still same :)
My rating increased by ranking 266 ?!?!
Whoa, and here I was regretting not realizing C was a flow problem sooner and complaining about how terrible my performance was...
Though I wasn't fast enough to solve it during the contest, problem C was really nice. A very good contest overall!
Actually your rank was 266 and your rating increased by 90! :P
Exactly. I wasn't expecting that! After the contest finished, I could have sworn I was going back to purple...
Lucky you!
Слабые тесты в задаче B первого дивизиона! Моя программа, получившая вердикт "Полное решение" даёт неправильный ответ на тесте: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1 числа l[i] сконструированы так : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. Поэтому наименьший набор l[i], имеющий наибольший общий делитель равный 1 содержит все 9 чисел l[i]. Поэтому правильный ответ на данный тест 9. Однако моя программа, зачтённая на codeforces даёт ответ 8 (не та программа, которая прошла претесты во время соревнования, а которая была отслана после окончания соревнования).
Что не так с моим комментарием?
You wrote that comment in Russian, but posted it as English. Many people who use English version of CF see your comment and can't understand.
Thank you.
Weak tests in problem B of Div.1! My program that got AC gives wrong answer on test: 9 9699690 111546435 74364290 44618574 31870410 20281170 17160990 13123110 11741730 1 1 1 1 1 1 1 1 1. Numbers l[i] are constructed so : 2*3*5*7*11*13*17*19, 3*5*7*11*13*17*19*23, 2*5*7*11*13*17*19*23, 2*3*7*11*13*17*19*23, 2*3*5*11*13*17*19*23, 2*3*5*7*13*17*19*23, 2*3*5*7*11*17*19*23, 2*3*5*7*11*13*19*23, 2*3*5*7*11*13*17*23. So the least set of l[i], that has gsd equal to 1 contains all 9 l[i]. So the correct answer to the test is 9. But my AC program answers 8. This is my comment.
Эх подстава в div1 B, одинаковые прыжки с разной ценой..
Nice problem set :)
DIV 1 C --> Awesomeness!! Thanks cgy4ever!! :D
How this contest can be rated since I did not connected to codeforces at least an hour ? Is that just happened to me or everyone ? I can not send my solution to B because of the network problems and now I got -80 :( I WANT MY RATING BACK !!!
Just to you. Codeforces wasn't running so smooth, but rest of people were able to send their codes and get the verdicts.
Russian page has no links to editorial nor winners of Div1 / Div2. If anyone can fix it then do it please.
Added them in Russian version, but in English since I don't speak Russian.
Take a look at this solution of div.2 D/div.1 B please. Where is bug? (WA on 24th test)
Here. for (int i = 0; i < N; ++i) { cin >> c[i]; dp[l[i]] = c[i]; } Nobody guaruanteed that l[i] is not in map already. You will just lose too much information if l[i] overlaps with another one.
Sure! Thanks for help.
А вдруг это была реклама раунда, в следствии чего 6067 участников: div1 — 1728, div2 — 4339. Почти столько же, сколько участвовало в Goob Bye 2014.