Приглашаю Вас поучаствовать в рейтинговом Codeforces Round #518. Дата и время проведения раунда: среда, 24 октября 2018 г. в 19:35. Раунд был перенесен с 23 октября на 24 в связи с проведением в это же время ICPC Indian Online Qualifier.
Это первое соревнование, предложенное мной. Надеюсь, что оно вам понравится.
На раунде будет 6 задач для второго дивизиона и 5 задач для первого (3 задачи общие). Контест будет длиться 2 часа.
Задачи для вас составляли Алексей kristevalex Кристев и Алексей Um_nik Данилюк. Также большое спасибо:
Николаю KAN Калинину и Ильдару 300iq Гайнуллинину за помощь в подготовке задач; Ивану isaf27 Сафонову и Олегу Merkurev Меркурьеву за тестирование раунда; Михаилу MikeMirzayanov Мирзаянову за платформы Codeforces и Polygon.
Хочется выразить отдельную благодарность Um_nik за помощь на протяжении всего процесса подготовки раунда, а также терпимость к моим глупым вопросам.
Как вы заметили, этот раунд проводится в честь компании Mail.Ru, значительно поддержавшей Codeforces по случаю 8-летия платформы. Вот несколько слов от MikeMirzayanov:
Большое спасибо Mail.Ru за поддержку Codeforces! Мы являемся партнёрами уже много лет, и было особенно приятно получить поздравления от старых друзей. Мне кажется, Mail.Ru — чемпион мира среди компаний по организации различных интересных соревнований для любителей программирования. Вот список (уверен, неполный) активностей Mail.Ru, которые могут быть интересны аудитории Codeforces:
- Mail.Ru Cup — новое соревнование по спортивному программированию (совместно с Codeforces!), открытое как для студентов, так и для профессиональных разработчиков;
- Технокубок — олимпиада по программированию для учеников 8-11 классов из России и стран СНГ (совместно с Codeforces!);
- Russian AI Cup (RAIC) — открытое соревнование по программированию искусственного интеллекта игровых стратегий (совместно с Codeforces!);
- Mini AI Cups (Mini AIC) — мини-клон чемпионата Russian AI Cup, площадка соревнований по искусственному интеллекту, связанных с написанием ботов для игр;
- Machine Learning Boot Camp (ML Boot Camp) — онлайн-чемпионат по машинному обучению и анализу данных;
- HighLoad Cup (HLC) — соревнование разработчиков высоконагруженных систем.
Кроме этого Mail.Ru запустило большое количество образовательных инициатив, я сам неоднократно смотрел записи лекций на YouTube с занятий Техносферы и других проектов.
Еще раз спасибо за поздравление. Надеюсь на долгосрочное и плодотворное сотрудничество!
Разбалловка будет объявлена ближе к началу контеста. Желаю высокого рейтинга и жду вас на соревновании!
Я буду на Codeforces Discord server в течение некоторого времени после раунда для обсуждения задач.
UPD: разбалловка div1: 500 1000 1750 2250 2500 div2: 500 1250 1500 2250 2750 3500
UPD2: опубликован разбор.
Codeforces is the best platform :) We are proud to work together!
I've noticed that 300iq is still unchanged to his real form. The legend will be mad.
If Um_nik didn't told you to stop creating problems, then I guess it will be a great round.
Nice joke, don't know why it is not heavily upvoted.
Participate and find out for yourself :)
I think that kristevalex really is a talented problemsetter. Of course he need more experience both in preparing and solving problems but his ideas are sometimes brilliant. Or maybe that was one time and will never happen again. Who knows.
Dude that doesn't even have anything to do with this round's setter, seems your so salty have to put your issues on random blogposts ._.
First Member of the Codeforces Triumvirate (circa 2018 AD).
Second Member of the Codeforces Triumvirate (circa 2018 AD).
Third Member of the Codeforces Triumvirate (circa 2018 AD).
Is it rated?
...
6 consecutive hidden comments, ridiculous.
UPD: 7 comments.
FST forces!
The time page gives 404 error, please fix it.
hhey is it rated or i dont partisipate
Yes, as it written in announcment: 'rated Codeforces Round #518'.
Why so many downvotes?
even who's downvoting doesn't know why
I don't mind my comment to be harmonious with the others (since it doesn't mean that I was wrong to comment).
The time link still gives 404 Error.
I can know when the contest will begin from the timer of Codeforces, but I want to be sure, because the difference between our country's time and previous blogs' time was zero, and now it is one hour and a half.
It starts 16:35 UTC
Thank you very much :D
Seriously, another problem with a bad statement, time to leave.
Totally agree you cannot use a word to define it's self "Let's call the set of rooks ... with rooks from this set" , it like saying a ball is a round-shaped ball, it doesn't make sense.
While I agree that the line (and problem statement as a whole) could have been phrased better, I'd also like to point out that what is being defined here is 'connected', so using 'set of rooks' in the definition isn't leading to circular definitions.
Yeah, I kept on staring this line without any clue for quite some time. Glad that I was not the only one.
Am I the only one who found problem statement of Div.2 A to be tremendously hard to understand?
can anyone please tell the solution for div 2 A
Notice that minimal answer multiplied by M need to have L+K coins. So ans*M=L+K, or ans=(L+K)/M. It can happen that (L+K)%M!=0 and in that case you need to increment ans by 1, or otherwise ans*M will have less than L+K coins. Lastly, if ans*M exceeds N, then answer is impossible (-1), otherwise output ans.
That is what i did but it didnt pass pretest 7:( This is clean. Please see to it http://codeforces.net/contest/1068/submission/44810290
I performed another check. If ans*M > n or L < N-K, the answer is -1.
Kept getting WA.
I think C had good problem statement. Maybe you didn't read it carefully, I don't know.. Maybe I'm one of the lucky ones.
You're not alone, I got pretests cleared after 3 WAs and I'm still not sure I understood it correctly.
This contest is plain garbage.
Contest was really nice. If you found contest easy try D,E,F, if tough then A,B were really easy. I liked 2A. In 2B, we just have to count the number of divisors of b.
nice contest
Excellent explanation. https://www.imageupload.co.uk/image/TAkQ
Problem A Div.1 Sample is useless.
after weak pretest, weak systest, we have weak sample now XD
just joking )
Hack for D1B?
I hacked 1 solution with:
Maybe some solutions could get hacked by changing k from 2 to 3.
what is the answer?
edit: the answer is NO for both k = 2 and k = 3
GreenGrape, your rounds are perfect
E: link. Nice problem!
I used the same :D
So, how to solve it based on this fact? My thought was like consider every edge separately, use something like tree dynamic programming to compute the probability for it to be the matching edge. But I'm not quite sure if this would work.
There is a greedy algorithm to find maximum matching in a tree. So, I have DP[n][2] — vertex and "Would this vertex be already matched in greedy algorithm?". When I consider some unmatched vertex with its unmatched child — I must match them (like I would do in greedy algorithm). Each DP[v][i] is a pair of integers — how many subsets of edges in this subtree would lead to this state and what is the sum of results in these situations.
Aha!Got it,thx. Just a slightly change of the algorithm of finding the maximum matching in a tree.
You can use standard dp. dpv, 0 is max matching in subtree if we didn't take v, dpv, 1 is max matching if we took v. Every time we connect v and u which were not taken, we should add edge (v, u) to matching.
Tree DP is right. Count the number of max. matchings and the sum of their sizes, where the top of a subtree can be unmatched / has to be matched. When processing a vertex's sons, you can use an intermediate state "has this vertex been matched with some son?". There are some annoying long formulas, but that's basically it.
I alone do not understand this part of the condition of problem C: "Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal."? After all, this means that the rook can make a move only in the next cell, where there is another rook (which does not correspond to test 1). Or how then to understand it?
Thought I had something for C, but I guess I was wrong! Kept getting WA pretest 3. Anyone want to share solution?
How to solve A?
i change long long to double long and i get ac
My solution is dp[i][number on position i][is a[i — 1] >= a[i]], to calculate it use prefix sums.
I think for Div2C, you have to construct a zig-zag like pattern. Messed up my implementation though!
let dpi, j, 0 / 1 denote for the first i elements, with the last value j, and the last dimension stands for is it needed that the next element is greater than/equal to the last element. Naively doing it would result in O(2002 × n), With prefix sum optimization, it can be reduced to O(200 × n).
nice , i think we can do it without the third state.
Div1A/Div2D is DP[10^5][200][2] , but I can't implement it ).
Same here
Div2A statement is bad :(
Very bad.
Very Very bad.
When Um_nik criticize misof for TCO and then, interestingly, leads a contest which consists of extremely bad statements... Just saying...
Really activates my almonds.
hahaha what does that even
wait wtf is a homemade coconut? I never knew food science was advanced enough that we were doing this
lmao dude have you even used a crafting table before?
I see what you did there. You are trying to paint me as a man of no culture (because I don't play minecraft)
Unfortunately, I'm always munching on cultured vegetables. Goes well with my alkalized water.
Can you really talk about culture when you aren't drinking 1000 liters of milk in 3 gulps though
Dairy is bad. Instead I drink coconut kefir (from my own lab grown coconut) with some activated almonds
Pete Evans describes "activating almonds" as putting them in water for 12 hours.
I guess normal almonds haven't even achieved their final form
I'd say "extremely bad" are a kind words for it.
90% of questions we get were caused by participants not able to read statements and understand basic mathematical constructions.
Instead, it would be better for a legend to reconsider his self-esteem.
It would be good, but not instead. I can't really do anything about people who either don't know mathematical notation or don't spend time reading statements.
Um_nik Hope you already know that, reading statements and understanding them are not same. And I think it's not you who will decide whether the statements were good or bad to understand. It's us, the contestants will do.
Do you think contestants complain about problems in every contest? No. If something really went wrong, they complain about it.
And only then you should say "I can't really do anything", when you know people hates you, so they started complaining about problems.
Problem A had poor statement as well as weak pretests. :(
Yeahh, right, maybe not able to guess what you hid in there. GUESSINGFORCES it was, how you like it ??
No matter the quality of problems, I agree with Um_nik that there are so many stupid questions asked. It happens every contest, even if people don't complain later in the comments.
How to solve div2E?
I didn't solve it, but here is my idea
Cut all the vertexes with degree 1, repeat it until one is left : the root Then simply check if all vertex's child degree is not less than 3
*Is it right?
This is what passed pretests for me:
A k-hedgehog has ≥ 3k leaves. Since n ≤ 105 this bounds k by 11 or so.
Now, perform k steps. At each step, remove all leaves from the graph, and decrease the degree of their parent by 1. Make sure that any non-leaf node either sees no change in degree, or their degree changes by >= 3. After this, update the graph so that you get a new set of leaf nodes, and do this again. After k steps, you should be left with exactly 1 node at the end. Any other case is a "No".
Div1C solution is just a cross:
After contest, I solved it after drawing some examples on paper and noticing the symmetry the hedgehog type of tree has, which turned out to be solution 2 from editorial.
My solution:
The natural solution I saw to the problem was to identify the "center" of the tree (which, must exist if it is a hedgehog) and then, from there do DFS/BFS to check if the given tree satisfies the properties given in the statement. The problem is, we need to identify the center quickly. How do we do that? If the tree is a hedgehog, every longest path must pass through the center node, which is number k, zero indexed (one can notice this by carefully reading how the hedgehog type of tree is created). So we find a longest path, and check if the length of it is > k. If it is not, then it is not a hedgehog. Else, we take the center node of the path and run BFS/DFS to check the properties, which are:
If all these are satisfied, we print "Yes", else, the given tree is not a hedgehog.
Does having two rows of white squares (0, 0), (2, 0), (4, 0), etc and then (0, 3), (2, 3), (4, 3), etc work???
Shit. I just found an asymptotically sufficient assignment for div1C:
Also, Um_nik, if div1E reduces to div1A-B after an easy to find observation, it shouldn't be in an online contest!
Easy to find you mean online? I didn't succeed, but I'm not good at googling. I'm sorry for that, you are right about problem being only about this observation.
"adjacency matrix" rank tree: gives SE as the second link, the first answer mentions something 2x size of matching
"adjacency matrix" rank tree matching: gives the answer for a tree directly, generalising this to a forest is easy
Not completely easy to find, but easy enough.
My story: I looked at the scoreboard immediately after submitting B, saw that someone solved it already and decided to work with the assumption that the solution is online. I read the statement, decided that if something is online, then it's the rank of an adjacency matrix, found something (including the first link), read the statement again and realised — I missed that the input is a tree, made the two queries, mentally checked that the first sample fits, so I haven't found something irrelevant, and started thinking about a solution.
The descriptions were not clear at least for me. Didn't like this contest.. AWFUL
Deleted
How did you generalise that? It's just 1 row + 2 knights.
problem C statement was really bad .. ofcourse so many solved it but you should consider not everyone has shakespear english level and give the beginners who hasn't read alot alot of problems a chance to solve it
I was going to try it but i was like if i need so much time to understand it then when I'm going to think how to solve it
Not your fault. I've read Shakespeare in school, it was easier than C.
Any idea why this submission would get WA on test 3 while this one passes pretests?
Edit: found the mistake.
Being in #1 for almost all the time, then got punished by a hack on 2A :D At that moment, I realised the statements were bad enough for me to deny reading them in the 10 last minutes :D
Btw, anyone can provide me a hack for 2A? :D
Could be overflow, numbers go up to 10^18
Not with mine. My solution consists of at most 1 addition, and no multiplication, the other operations possible were division only...
My hacked solution: 44781223 (not sure if accessible now)
10 6 3 4
many programmers checked only if m>n or (l+k)>n, then print -1 else printed ans=(l+k)/m + bool((l+k)%m), they never checked if ans*m is exceeding n or not and hence got hacked.
Figured. Thanks! :D
Both statement and pretest for Problem A were too poor. I will also fail system test! :(
Pretest 3 of div1A?
I don’t know what is test 3.
But you can try this one.
3
-1 -1 -1
Answer should be 40000
Thanks, my solution does work for that test though :(
Is DearMargaret going to have a bad rating change for first time?
maybe he wants to show something after dotorya, this blog.
How to solve Div2.C ? I'm really confused by the statement, thus cant solve it ://
Same here, examples didn't make sense for me.
for every edge x1-x2 put rook of color x1 to (x1, y) and of color x2 to (x2, y). make 'y' value unique for every edge and check condition that all colors should be on chessboard
There could be n * (n — 1) / 2 edges, which is 100 * 99 / 2 = 4950 for 100 colors. Your solutions places 2 rooks for every edge, resulting in 9900 rooks on the board. This is a violation of: "Total number of rooks must not exceed 5000."
There is accepted solutions with this algorithm. Could anyone please explain where my thoughts are wrong? Are they?
m <= min(1000, n*(n-1)/2)
Thank you, so this was a 'how do I read correctly' kind of problem... |-)
Am I the only one who passed the pretests of problem A Div.1 using a Top Down approach?
deleted
I did, but I had to resubmit at the end of the contest to reduce memory usage :( Recursion uses memory too, so having array size within the limits is not enough.
I tried this test in Custom Invocation and got MLE:
-1 200 -1 200 ....Does anyone have a correct solution for Div. 2 F/ Div. 1 C? I found something that gave
but I couldn't improve it further.
Nigga read the comments.
Sorry, I had missed your comment, thanks!
How to solve Div1C:
How do you generalize the answer from this? It's just 5 guys chilling in a row with 2 in front of them
In one column you have a knight at y=0, in the next one at y=0 and y=3 and that pattern repeats. It seemed quite obvious to me.
EDIT : Didn't see that the editorial is already published.
EDIT: Most probably, it fails because I am assuming the CHT implementation to be min-oriented but it actually is max-oriented.
Idk, seems reasonable to me. But I also observed that the optimal i for each t would be the same, i.e. we just spam some i until one upgrade is available. So no need to use CHT here.
EDIT: Same as jtnydv25 and realized the editorial doesn't do what I did :s
Do you mean for each t > 1? (otherwise the statement is definitely wrong), and how do you prove it even for t > 1 ?
Wow, right when I tried to write my proof I realized it was completely wrong :o
How it was not caught in the pretests is beyond my knowledge though.
Anw there goes my red xD was fun bragging around
Please someone tell me, why do I get TLE in this: http://codeforces.net/contest/1068/submission/44804608 This is Div2B
Please tell me, it won't take a minute for you to read my code.
Integer overflow. Remember, n ≤ 1010.
i*i becomes a negative value when it overflows, so your for is basically infinite
Div1C
Is this the way to place the knights?
Dear kristevalex and Um_nik, please stop making problems.
What's wrong with vintage_Vlad_Makeev? Was he hacked or just rofl?
maybe he tries to do the same thing as .o.
English statements are not too good, especially problem Div2C. Still, it was a fun competition, thanks for the effort.
The problems were nice, but the contest was bad. Here are the reasons:
All of that are valid points, thanks.
Output of C provides almost no information. I don't think there is any mistake here. Out of 3 people who said "easy to generalize" only 1 guy actually did it.
which observations does B need? it was obvious from the picture how to solve it
div1 B test case "1 1" is not in the pretest...
Why was Div2B given a max score of 1250 instead of the usual 1000? Did you think Div2B was closer to Div2C than Div2A? I read Div2B 4 times because of your decision to give it 1250 points. Guess I should have done that for Div2A instead as it had such a good corner case. I read similar complaints about Div1A and Div1B as well. Points distribution was not good.
After this round, i am demotivated for sure.
code_hard123 bro you are back!
if http://codeforces.net/contest/1068/submission/44797756 is AC. why http://codeforces.net/contest/1068/submission/44800937 is WR?
Participant's output -501767591So it seems that you have overflow. Checking the code you declared
int bs()instead ofll bs(). I didn't test it but it seems that is the problem.Started after 10 minutes, misunderstood B, got WA, then solved A, panicked with B, pretests passed E, panicked with B again then finally understood(felt so stupid at that time), couldn't submit C with 2 seconds in hand! :(
Watched the status board with heart in my mouth whether E will pass the system test or not. It passed :D Submitted C after contest, AC in one go. -_-
Mixed feelings, A very eventful contest indeed!
Very nice problem !
And I finally got the Expert Title during this contest!
I wait for this blue name for a YEAR and I finally got that!
Congrats bro!
Thanks.
And wish you can get the Expert Title in the next competition!
I finally made it! Its feels so good :)
Является ли раунд рейтинговым для 2 дивизиона?
Интересно, а в задаче Bdiv1 тесты 120+, принесшие большую часть реджектов -- это добавленные взломы?
Unfortunately the system tests on today's Div 1 problem D were quite weak. I wrote up an explanation here: https://codeforces.net/blog/entry/62692. Make sure to take a look if you are trying to solve problem D in practice mode (or just interested in the problem).