Привет, Codeforces!
30 марта 2016 года в 19:05 MSK (время московское) состоится очередной раунд Codeforces #346 для участников из второго дивизиона. Традиционно, участники из первого дивизиона приглашаются поучаствовать в соревновании вне конкурса. Этот раунд будет необычным: будет предложено 7 задач и 2,5 часа на их решение. Надеюсь, что все найдут для себя интересные задачи. Обратите внимание на необычное время начала раунда!
Задачи для вас готовили я (IlyaLos), Эдвард Давтян (Edvard), Данил Сагунов (danilka.pro), Роман Глазов (Roms) и Владимир Петров (vovuh). Хотелось бы сказать большое спасибо Глебу Евстропову (GlebsHP) за помощь в подготовке задач, Марии Беловой (Delinur) за перевод условий на английский и Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon, а так же за помощь в подготовке контеста и идеи нескольких задач.
Разбалловка будет объявлена позднее.
UPD Разбалловка: 500-1000-1000-1250-1500-2000-2500
UPD2 Соревнование завершено! Всем спасибо! Разбор
Необычное время, необычная длительность, необычное количество задач... Может, стоит поправить "...очередной раунд Codeforces..." на "... необычный раунд Codeforces..."?
Expecting a good round :)
all newbie people need that :'(
A regular Codeforces round after a long time :).
Well, sort of regular.
A usual round at unusual time!
Just learnt coding about two weeks ago and this is my first round. Wish me luck!
For someone like you I don't think you need luck
non egyptians will not understand xD
Great way to learn. Best of luck.
9 months ago I was in your position, and now I'm here (further than I expected). Good luck!
I started 6 months ago and still a pupil, any advice?
maybe this topic can help you: http://mirror.codeforces.com/blog/entry/17842
This contest has rating or doesn't it?
Not again the same question.... Tired of same question everytime
k0sk
That's my boy, well done. Dude, wish me luck next contest.
i think that is fake xD
You never know! XD Maybe he's a natural genius so he managed to come third after 2 weeks of coding! XD
Thanks for your support everyone. :) ♥
Why create fake and then leave them ? It is obvious that if you learnt coding two weeks ago you wouldn't be able to solve G...
He's very smart. Smarter than everyone. I think he's even on par with Kim Jong Un.
What the hell, man!
When will you bring your army to take tourist's rating?
جرا ايه يا عرص؟ طلعت ال٦٧ يا حيلتها؟ ما تجيب جيشك وتيجي تنفخهم
يلا ياد روح العب بعيد، الحاجات دي انا اللي بخترعها
Ok seriously cut it out.
ROFL... https://en.wikipedia.org/wiki/Abdel_Fattah_el-Sisi
Жду с нетерпением этот раунд! Спасибо всем тем кто стараются ради нас и проводят такие раунды!
Hope to advance to Div1 this time!
Best of luck :)
Thank you mate. I made it! :p
Great ... congratulation :)
Just wondering : If there are 7 problems then why not make a Div.1 Round too?
No, because tourist now has a 4000+ of rating. I respect that!
tourist's rating won't decrease if they make a Div 1 round :P
Kinda related, I wonder if it would be difficult to allow for div1 users the option to register to div2-only rounds as ranked competitors. If I'm not mistaken, it's not allowed because div1 users might run out of problems to solve, but if they wanted to register as ranked competitors into div2-only rounds, they'd have to accept that possibility, yet could still get the fun of competing in a ranked round. Many div1 competitors usually can't solve any problems past the first 3 anyway (I know I can't).
It would be nice. We can just have separate rankings, which means some may loose rating even though they solve all problems (but too slow).
Div1 competitors will quickly solve problems and will begin constantly hack others. Poor chance for div2 competitors to hack somebody (and learn how to hack).
Probably because the F and G problems in this round would be way too easy as Div1 D and E.
Is someone going to answer his question!?
I can try. Because the problems are too easy for Div 1?
Let's hope this be a nice round for everyone :D
Good luck everyone
Good luck everyone
It's been a long time since a totally normal rated Codeforces Round. :(
Except this one has 7 problems and 2.5 hours and is only rated for Div.2.
Интересно будет увидеть разбалловку для 7-ми задач
Здравствуйте. На Codeforces я всего 10-11 дней,по-этому не знаком с понятием разбалловка — объясните пожалуйста.
Разбалловка это информация в которой указано сколько баллов будет предложено учаснику за решение конкретной задачи.
When Soni says something, you repeat it!
When Soni does something, you do it!
When Soni has something, you don't have it!
And that's so because Soni is a cool guy!
a div1 guy with fake acc
Soni>Div1!
Why 7 problems for div.2???
maybe for easy problems :-"
I guess maybe they found those problems were too easy for div.1. So, 7 problems for div.2. lol Okay,frankly, maybe just for fun.
I wonder if there's something that could tell me my expected ranking to get a +rating. Even 5 minutes before the contest would be great. Don't know if that's even possible though.
you expected rank can't be computed before the contest is finished, because it depends on the people who make at least one submission
Try the NBHEXT extension for Chrome. It is not completely accurate because systest, but you get a rough estimate.
I think that it consistently gives lower ratings because it interprets newcomers as having "0" rating instead of "1500" rating.
Yup, and it also occassionally shows a 0 difference for Legendary Grandmasters when it obviously shouldn't be 0. But like I said, rough estimate.
Can I request a 10 minute delay? The bus is slow : O
5 min? hah
if I don't mistake it has extra registration...
Funny. When using CHelper, you can see "April Fools Day Contest 2016" before today's round. Did that one already happen?
I guess it's because it was added to the contest list earlier?
UPD Разбалловка: 500-1000-1000-1250-1500-2000-2500
Is something changed regarding contest registration. Though I registered, it's still asking for registration while submission.
http://i.imgur.com/35uAN1W.jpg
--- [Edit] Now option to register re-appeared, and can submit after re-registration.
.
Всем здравствуйте. Я пишу с планшета, написал 3-ю задачу, заблокировал, при попытке просмотреть код других участников для взлома, пишет "Content on this page requires a newer version of Adobe Flash Player" и появляется ссылка на флэш плеер, перехожу по ней, там пишут, что эта программа не предназначена для моего устройства. Что мне с этим делать? Заранее спасибо за ответ
Why is problem A blocked? I want to resubmit my solution.
I am not put in a room for hacking, so I cannot hack. Is this a bug?
EDIT: I also registered late, so I don't know if this is the problem?
Какая-то магия происходит. Пытался взломать двух человек. Переписал их код себе. У меня выдаёт неправильный ответ. Взламываю и получаю Неудачная попытка взлома ...
Чаще всего правильных ответов много.
I don't want to see all human defeated by AlphaGo, but this will happen if AlphaGo passes all system tests
His submissions look suspicious though. He got B and C accepted in the same minute, and it only took him 8 minutes to solve G.
By the way, I think that the problem statements are pretty formal and the next challenge for the DeepMind team could be trying to compete in the programming contests.
Correct me, please, if I am wrong and there is something about artificial neural networks that doesn't allow them to compete here.
Are you joking? Sometimes I can't figure out what the hell the authors want from me by myself, and you want to make computer understand that?
Well, aren't computers better at solving CAPTCHAs than humans already? But I agree that it seems very unlikely to happen
You know that can't be an argument :)
Sometimes we cannot recognize faces on the pictures, but Google can (despite the millions of years of evolution that crystallized our ability to recognize human faces).
I wanna see AlphaGo vs tourist face-off assuming AlphaGo is AI and not a team/user.
If AlphaGo is an AI I will eat my hat.
За 10 секунд до конца я не успел отправить решение, так как меня разлогинило.
Interesting contest, what was the solution to F?
Loop through all the cells. If k is evenly divisible by the number in the cell, and cellnum*m*n is greater than k, then do a BFS across adjacent cells that are greater than or equal to cellnum. If we have processed k/cellnum nodes, immediately print YES, print a matrix such that any cell examined in this BFS is given number cellnum and all other cells are 0, and then return. If the loop completes without finding anything, print NO.
Won't this time out, if all the cell numbers are divisible by k and none have required adjacent cells greater than its value?
You are correct... for example, the 1000x1000 checkerboard pattern of 3 and 7 with a 1 on the bottom right and k=3000000 times out horribly with the wording I gave. I should add, then, that I kept track of which cells I had visited in BFS's for a given factor, so I wouldn't do duplicate work (i.e., a full BFS every time I ran across the number 3). With this addition, it doesn't time out in practice because the number of distinct factors of k such that you will need to examine a sizable subset of the matrix is exceedingly small.
Mine didn't. I used the same approach. But I used some heuristics to reduce the time (eg. I consider only those values in the arr[][] such that k/arr[i][j] <= n*m). Please refer to 17055152.
Thanks, that did help.
If you want O(nlogn), you can use DSU on components to store the number in each component and a priority queue to process cells by descending height so that you dont have to process any large amount of area twice.
Please someone explain problem 5. I think it is somewhat related to cycle finding or some trick to be used using dfs/bfs.
Answer can not exceed the number of connected components. So define answer=number of connected components. If there is a cycle in a connected component then decrease answer.
Thank you. Now seems it was to easy and seeing many people solve it.
Consider each connected component separately.
If the connected component is a tree, the answer is 1. This is because there are only V - 1 edges — not enough edges for all vertices. It is not more, we can root the tree and direct all edges from parent to child. Only the root will have no incoming edges.
If the connected component has cycles, the answer is 0. To see this, take an arbitrary cycle and direct the edges in it the obvious way. Now you can throw out some edges (and direct them randomly) to get a tree for every vertex in the cycle. Direct all those trees from parent to child and you'll see that all vertices have incoming edges.
So, for each connected component, check if it is a tree, and if it is, add one to the answer.
Alternate (greedy) solution:
at the end, the answer is the number of nodes without any "inward" edges (http://mirror.codeforces.com/contest/659/submission/17054791)
Consider a connected component If it has a cycle it is possible to assign directions to edges such that no vertex has zero incoming edges
If it has no cycles there will be exactly one such vertex
So just count connected components which do not have cycles
if you don't want to find cycles, then just count the number of edges in each connected component, you can do it by summing up the degrees of all nodes in that component then divide it by 2. if the number of edges is equal to number of nodes minus 1 then it's tree and there's no cycle, otherwise there's a cycle
Hacking test of B?
5 2 Ivanov 1 763
Andreev 2 800
Petrov 1 800
Sidorov 1 800
Semenov 2 503
4 2 Ivanov 1 800 Andreev 2 763 Petrov 1 800 Semenov 2 503
some people wrote if (list[i][0] == list[i][2]) printf("?"); else print answer, which is wrong (should be list[i][1] == list[i][2])
Задачки прикольные, кажутся сложными, а потом понимаешь, что всё просто
Почему мне не удалось взломать эту посылку? там из priority_queue достаётся 2 элемента, и 2ой сравнивается с верхним в оставшейся очереди, но эта очередь может быть пуста. как сломать это при условии, что очередь пуста?
Он проверяет размер очереди
Problem B Hack
3 1
dushyant 1 20
sumit 1 16
snigdh 1 16
Answer --> ?
PS — My submission will fail. :(
Look to the solutions of problems B and C user AlphaGo , they sent in 10:48 and 10:51, and had so different style code, i think it wrote by different people
why geometry why :'(
I kept trying to solve D for two hours. Did you solve it? . I couldn't get my algorithm right for finding whether a line segment will properly cut any segment of the polygon when extended in the direction given.
All of the left turns are dangerous, while right — not. If we know this, we can solve the problem with no geom using some conditions.
It is never stated that she is travelling clockwise. If she goes counter-clockwise, then a right turn is dangerous, and left is not.
Edit: I retract my statement, I didn't realise that the staring positions was always the bottom left
if she starts at the bottom left and the first move is to go north, there's no way the water will be on the left side (since you end up at the starting position, see http://mirror.codeforces.com/contest/659/submission/17049036).
Yes, I realise that now, I never saw that part
Checking whether the direction is clockwise is actually really easy. Consider the following equation:
The direction is clockwise if and only if the sign is negative.
EDIT: Friggin' Codeforces Latex
the answer is the number of left turns (you can get that by cross product)
My approach to D was to keep a counter for the dangerous turns if the water is on the left and if the water is on the right. While iterating through all the points, use the previous point, current point and next point to determine whether she is turning left or right. If you are turning left, the it would be dangerous for the water to be on your right, so increment the right counter. If you are turning right, the it would be dangerous for the water to be on your left, so increment the left counter. Then when you are done iterating through every point, just output whichever counter is smallest.
Starting point is at the left-bottom most point, there is no way the water can be in the left.
Ah, I didn't see that. I made more work for myself than I needed.
My solution is simply (N-4)/2. Consider 90 degree and 270 degree angles.
After some minutes of thinking how to solve it in a nice way, I give up and seek for pre-written geometry library that do the job for me (I hope there's no bug inside tho).
For those who solve it without a generic written code, how do you guys managed to write decently? (e.g. without using lots of if)
Which library did you use?
Actually it's not a library, just a codebook containing the function Point_Inside_Polygon which is exactly what question asked :)
I forget why the function work tho
I tried this: http://www.geeksforgeeks.org/how-to-check-if-a-given-point-lies-inside-a-polygon/
It malfunctioned. I kept modifying it. Something kept breaking :(
I used the built in Java function that does that, but fiddled with it a little as the function sometimes seems to be buggy if the point is directly on the side of a polygon.
http://mirror.codeforces.com/contest/659/submission/17053372
I used 4 ifs (in fact 8 so that the conditions are more clear), is that a lot?
You can solve it with just basic things like calculate area of polygon & CCW
Turns out area isn't even needed because you start at the bottom left...
As it has been said the answer is (N-4)/2 since when you have more than 4 edges on the polygon all the left turns will have one corresponding right turn. I am amazed how almost none of us didn't figure that out, going instead for a longer solution...
Hahaha almost thought of convex hulls and stuff until I realized "hey could I find a pattern". and I noticed it was something like linear (clearly it must) and then I remembered of 90 and 270 degrees.
Basically if we have an n-gon composed of 90 degrees and 270 degrees suppose there are a 90 degrees and b 270 degrees. Total angle is 180(n-2). Then 90a+270b=180n-360... a+b=n. Solving we get b=(n-4)/2.
Yay
You can do it without calculating the area or point-in-polygon queries, by just checking 4 conditions regarding the previous and next directions of movement, for each corner point. Please refer 17044429.
Collect all if's in one place and use enums: 17046342
chameleon
https://en.wikipedia.org/wiki/AlphaGo
By seeing submission gap between B and C, probably a team.
What if he thought to first solve both problems and then submit?
Maybe he had a stupid bug in B, submitted C, corrected B and this resulted in both submissions the same minute :)
What if he's an AI?
And his codes have different styles because he searches and combines codes from a huge database of solved problems.
6 минут не хватило, чтобы разобраться, где ошибка в G =( Главное формулы правильные вывел, но забыл в коде в одном месте умножение поставить...
Please suggest an approach to solve F and G.
Thank you.
F is already explained, as regards G I did dp:
dp[i][0] — the number of ways where you remove something from position i and the remaining height is not greater than h[i+1]
dp[i][1] — the number of ways where you remove something from position i and the remaining height is greater than h[i+1]
Obviously if h[i] <= h[i+1] then dp[i][1] = 0;
Hope that helps.
Edit: If not, here is the submission implementing that logic: http://mirror.codeforces.com/contest/659/submission/17059428
I think it can be solved in a greedy manner, using DSUs. Start processing the cells in decreasing order of their values. When you process a particular cell, check its neighbouring 4 cells. The cells among those 4 which have their values >= value of current cell, are combined with the current one using DSU. After each combination, check whether that set has the required number of cells (if value of the cell is v, the set should have at least k/v elements). The moment this occurs, you have found the answer. Assign exactly k/v cells of this set to v, and assign all remaining cells in the grid to 0.
Hack you back.
Lol, payback. There should be an achievement for a thing like this.
Haha, there actually is! I've earned that, see: http://cfa.yuldashev.net/profile/ehsanoo It's called Peresvet & Temir-murza.
There is "Speck in your brother's eye", however I don't know if it counts only failed systests or also hack back.
http://cfa.yuldashev.net/achievement/5
That's so me in past contests, lock one problem, read others' solutions and realize mistakes in mine...
Would binary search in F pass the time limit?
Nice and balanced problem set, perfectly suits for div2 difficulty in my opinion. But, Problem statements were not easy to understand (at least for me).
Wasted my whole time on a silly mistake with B, could have easily solved 4 problems :( :( :(
Codeforces team: Please check FlappyBird's submissions.
http://mirror.codeforces.com/contest/659/room/112
Seems like he wasn't codding alone.
Any ideas how to solve C? I did simple greedy algo but it failed on tc #10.
Greedy was okay.. Can you post your code ?
You just made 100100 sized array to mark used toys, but that can be from 1 to 1e9. Your update will fail if used toy is greater than 100100.
Your code->
На последних минутах придумал решение для F.
Как думаете, такое решение зайдет?
Не нужно ничего раскладывать. Все гораздо проще.
Достаточно лишь отсортировать значения в ячейках по невозрастанию и пройтись по ним поддерживая СНМ.
Каждый раз, когда добавили чиселку x, проверяем, если k делится на x и размер текущей компоненты не меньше k / x, то выводим ответ (обойдя компоненты дфсом, чтобы получить необходимое количество клеточек).
Если не получилось найти ответ — выводим NO.
Собсна, все.
What is approach to solve question D ?
(n-4)/2
Are you serious!? Does that actually work?!?
Edit: Ah, I see now! First there is the 4 turns which MUST be made to get back to the start, so subtract them. Then every variation other than those 4 turns require 2 turns to go straight again (1 safe turn and 1 dangerous turn), hence the division by two.
Can you provide some explanation for this?
very rough idea
rectangle-> 4sides,0turnings,take a side possible modification gives 2 turns for 4 more extra points
...and here I thought I was being clever with my vector solution counting the left turns.
not my idea some in my room did this , i tried to hack but was not able to get any test case
Me too, I also counted left turns)
Lol and here was I dangling with geometric algorithms and what not :P
Мне кажется, или я стал слишком часто попадать в одну комнату с кем-нибудь из своих друзей... За последний месяц раза 3-4 это случилось, причем 2 из них — подряд и с одним и тем же другом.
Before that contest finished, I was 1200 and now I have two failed problem and I am 3200. Ohhhhhh noooooo.
Anyone else not realize that you couldn't add to piles in problem F? I had the solution but made that dumb mistake ugh.
Or not. TLE lol
Can someone tell me some hacking tests for 'A'. A guy I know made 11 successful hacking attempts :D
Possible mistake can be giving output a negative number, because of improper modulo operation.
Mine failed at this->
10 6 -100
answer should be 6.
my code outputs -4.
Please enable upsolving !
It starts when system testing is done, which is going on and will complete soon.
Seems enabled now.
I hate that kind of simple but tricky problems like A!
How is this even working?? Problem D. answer is n/2 — 2 ; http://mirror.codeforces.com/contest/659/submission/17055800
n/2 — 2 is the exact same as (n-4)/2, to which there are multiple explanations in the above comments. One of them should help you out.
The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3".
The difficulty of C, D, E problems weren't even of Div2 level.. The contest should be renamed to "DIV 3". 1000+ people solved C,D,E
I liked problem E!
But A and B were?
Can you please explain how you solved problem E?
If you are given a tree, then the answer will be 1. Let's say you root the tree from a certain vertex, then we can draw directed edges from parent of all vertexes to them (And none of them will be seperate). Except the root (which has no parent) .. So in a tree we will always have answer 1.
But, if we add one more edge to the tree. We can satisfy the earlier separated node (i.e root). So, if we have a cycle in the tree. It would have answer 0.
So finally see all the connected components that doesn't have a cycle (count all the connected components that are actually trees). This could be done easily with a DFS.
Please someone explain this solution ( http://mirror.codeforces.com/contest/659/submission/17054528 ) for problem D.
Yes they will. In the comments above.
Its really an absurd verdict.
I first submitted a solution in problem E which got WA in pretest 9, then i get a new idea which gets AC, but i do not understand why my first idea was wrong!!
I gets the in degree for each node and greedlly subtract the highest m value of them (one by one using priority queue ) and the answer is the number of zero in degree after that, and this is the code 17050130
why this is wrong?! what i missed here?!
Your code fails in a test like this
Thanks Mr.president :D :V
When will the ratings be updated? Has anyone's been updated yet?
Can anyone help me please ? Why I am getting WA at Test 15 for Problem B ???
http://mirror.codeforces.com/contest/659/submission/17059710
you are checking an extra condition, which is wrong and not required. I have submitted modified code of yours to get AC. Refer this -> http://mirror.codeforces.com/contest/659/submission/17060205
Thank You ... But Why this Happens so? do you please Explain ??
When only 2 candidates belong to some region and have same top score, you were giving output of "?". Which is wrong.
As top scorers are the winners of that region.
Is AlphaGo not a single coder?
The coding style of the submissions by this account are different. For examples, solutions on C and F used:
while others don't.
And solutions on E and F used:
while others don't.
We can find that the coding styles of different codes are not similar.
On the other hand, AlphaGo used only 3 seconds to submit B after C. Should this kind of accounts be banned?
OK this account is fake, but there is no proof so he can't be banned.
If it doesn't get banned, this may create a precedent for others to cheat.
Looks like PPFishIsADoge is not a single coder too.
Yeah, I looked upon his submissons a moment ago and the coding style is different.
Also there seem to be 2 very distinct templates being used.
Can someone tell me why I am getting TLE in my solution for B , I am trying to find bug around 2 hours : 17055144 ?
Thanks in advance.
link
your sort function is not good. if (compare(a, b) == true) then (compare(b, a)) should be false.
Thanks! It is silly mistake :)
Hi.
Your comparator must return 0 for (a, a).
Ac.
Thanks for help :)
First time to solve A-B-C-D-E during the contest time and guess what!! my rate decreased :(
Please let us open the problemset now
This is my first round to get an AC problem, nice problems (y)
btw this is also my first comment in CF xD
Can someone tell me what is wrong with my B solution? 17044686
You need to check that
a[i].size() == 2before asking values, otherwise yourif (a[i][0].score == a[i][1].score)will result in undefined behaviour in C++.
Thanks!
Before and After system test
thanks dude! 17057269
No problem buddy :]
Can I ask why?
...why?
I had a problem with the 53 test case of the B problem. My output is correct, and the author of the problem didn't estipulate any order of the names of the selected member of the team...
I got wrong answer, and the checker message was "wrong answer Jury solution is better than the participant [region=143]" ... I just don't understand the reason that i've received WA...
Before checking [1] == [2] you must ensure that there is at least 3 participant, otherwise equality checking result would be undefined
Can anyone explain this solution to E. for me? 17042676 by AlphaGo
I think I get that the array fa represents the "root" of each node's connected component. What are tot and TOT?
tot: vetexes count TOT: edges count if TOT==tot, there is a circle
Thank you! Do you know what purpose this line serves? tot[u] = TOT[u] = 0
Edit: I just tried running the submission, exactly copied, but with that line removed. It still passed all tests. So it looks like that line is unnecessary.
As the tutorial said, we can make a boolean array in problem c; but i failed to do it at c++, because array size of 1e9 was too great, can anyone tell me how to achieve that, thank you
Using sets. Learn STL as soon as possible. Because it's very useful and easy.
The editorial also specified to maintain a boolean array of max 2*10**5 and from the input numbers mark only those that are less then 2*10**5.