И снова привет, Codeforces!
Я рад пригласить вас на Codeforces Round 580, который состоится в 18.08.2019 16:45 (Московское время). Раунд будет рейтинговым для обоих дивизионов.
Все задачи в этом раунде придуманы и подготовлены мной, antontrygubO_o. Я постарался сделать их идейными и очень надеюсь, что они вам понравятся!
Спасибо arsijo за отличное координирование раунда, 244mhq, gepardo, danya.smelskiy, reeWorld, Xellos, Mediocrity, I_love_tigersugar, KAN за тестирование и ценные замечания, а также Михаилу MikeMirzayanov Мирзаянову за отличные платформы Codeforces и Polygon.
В каждом дивизионе будет предложено 6 задач и 2 часа 10 минут на их решение. Как всегда, настоятельно рекомендую прочитать условия всех задач.
Всем удачи и высокого рейтинга!
UPD1:
Разбалловка Div $$$2$$$ раунда: 500 — 1000 — 1500 — 1750 — 2250 — 3000
Разбалловка Div $$$1$$$ раунда: 500 — 750 — 1250 — 2000 — 2500 — 3000
UPD2: Разбор
UPD3 Поздравления победителям!
Div 1:
1. TLE
2. Um_nik
3. mnbvmar
4. Benq
5. Rewinding
Div 2:
1. kkkkk11
2. sucuk
3. ujrepacul
4. zzffxx
5. VahitGuetta
What are my chances of becoming a legendary newbie candidate after this contest?
0.5
What chance that problem on a heavy cycle flow centroid decomposition on bitsets will appear in the contest?
If you decide to submit some of that, it will definitely appear in the contest.
See.. This is the type of question that drives an innocent ass Titan down the path of Thanos
What to do a Sunday evening, take a walk with friends or write a contest from antontrygubO_o? Of course I will write a contest from antontrygubO_o)
This Sunday life -
17:30 IST — Participate in ABC.
19:05 IST — Participate in CF Round.
21:30 IST — Participate in Cook Off.
Very busy indeed :) What's an ABC btw?
https://atcoder.jp/contests/abc138
Oh okay! Thanks, will do...
00:00IST rip
I have a quiz of algorithms the next day. :(
*Goldman Sachs
Больше никаких доминошек? :)
When you are waiting for the contest on codeforces and suddenly codeforces announced there will be a contest :)
IQ тест
Кстати, а почему в английском версии нет этого слова?
Unfortunately, the Atcoder Beginner Contest 138 conflicts with this for 5 minutes. Is it possible to shorten the ABC or shift this contest by 10 minutes? (Mentioning chokudai for the ABC)
We decided to do the following:
The contest will be shifted by 10 minutes.
The contest length will be 2 hours and 10 minutes.
Therefore, there are 5 minutes between ABC and CF and other 5 minutes between CF and Cook-Off.
Thanks! I know it's hard scheduling with contests on different platforms. I appreciate all the hard work you and the CF team do!
Thank you for your kindness.
That's ABC 138, not 038.
Thanks haha, fixed the text.
Usually I keep my vote after the contest is over, but for this one I will give you my up-vote now just for the lovely image <3
Good luck to all of you!
Btw,wish I can become a candidate master.
What I need is only +1 rating.
I think I can achieve that:D
。。。
Why not? You can have a try!!
You will not get it
hello,
do not discouraging any others from candidate masters,, this person has a greatest chance at a candidate master,
generally a rule if u wish other persons to get a highest ratings as possible,, then u will also be high rating,
wish u high rating, u can do it, rajeshwar~
No he will lose -100 delta in this Contest
losing -100 deltaa, is that what you say,,
yes that is, u have the lost -100 delta, but that is mean in it that he will gain! 100 delta,,
this is type of thinking u must have, not about the "he will fail" because if u think he will fail u might also have a fail,,,,,
therefore, you must wish a high rating, like i wish u and all other contestants to this round,,,,
wish u high rating,,
rajeshwar~
there's no need of arguing with those people who are always expecting others to lose rating and stuff.
And also wish RedLycoris's rating can be greater than mine!
wish zrmpaul become international grand pupil
Those people who says things like "you won't" and stuff are really annoying, RedLycoris may become purple if he has a try. And also it's really mean of them to say such words.
[Deleted]
It has been deleted by the managers.
66666!
Just imagine having a zero change. This will be legendary!
http://codeforces.me/contests/with/halohalo
That's not what I meant. He needs just +1 to get purple, but getting a zero in such a situation is very rare. I personally have a contest with zero rating change, you can see that.
congrats...give me some good luck also for becoming an expert...
Good job!
Hope I can become a master after this contest even if the probability is so small.
[deleted]
Spiderman: Wherever I go, I see Iron Man. Me: Wherever I go, I see tourist.
BestMotivation.
LOL Motivation :3
So who's Mysterio?
Админ, где мемы
Div 1 orz
First div 1 Round for me and hope the result won't be bad:)
Me too! I hope that I won't be Expert again after this contest. Good Luck!
GLHF
Every time I see a Division 1 contest I get excited about it and participate in it and end up in Division 2. But that does not stop me from participating again. :)
Every time I see a Division 1 contest, I get excited about it, participate in it and end up in Division 2. But that does not stop me from participating in Division 1 again. :)
I wish to have the same spirit for a long time :)
thank you so much <3
Wow, I didn't know you created rounds too! Will participate using your vscode extension for sure
Participants attending the contest at 23:45PM https://i.imgur.com/KxJ7aAI.gif
It says image not found for me.
updated
i hope i can do well, good luck for all
three consecutive contest for me today :)
I find it really hard to focus for that long. I've tried doing two contests in a day before and that didn't end well; this is just crazy :o
i once did 2 consecutive before, and my performance in second was better than usual . So i am gonna try three tonight XD
I am late to comment this time.
Well!This contest started early (relative to most other contest). I think I will have better energy to solve the problems in this contest.
That 10 minutes can be lifesaver :)
I hope the problem statements are short and clear.
Programming Final tomorrow! ^_^ Probably my last contest:)))
I hope the problem statements are short and clear.
Guys check this out: https://codeforces.me/blog/entry/68888
a good blog's id in Chinese!
GOOD LUCK
Participating in a contest after nearly 50 days. Hope this goes well!!!
Huge waiting times! please look into it.
Long queue time anyone?
Another $$$Queueforces$$$ Round!! :(
К сожалению, после дополнительной регистрации не могу сдать ни одну задачу. При попытке посылки задачи (любой) всплывает сообщение "Ранее вы отсылали абсолютно такой же код".
P.S. Хочется чтобы в таком случае для меня контест не учитывался в рейтинге
Ну фактически же ни одной посылки не совершилось? Тогда априори не будет никаких изменений в рейтинге.
Хм, не знал про эту особенность.
Если так то здорово, спасибо!
Two consecutive Queueforces. :(
I can't submit any answer. When I'm trying to submit, the web page say "You have submitted exactly the same code before". How can I solve this problem?
try writing a comment and then submit
It doesn't work. It is not allowing me to submit even my first attempt. It is always showing "You have submitted exactly the same code before", but there is no submission in queue.
try changing the name of a variable
Guys, when would good tests appear?)
yes, A contest with good problems on algorithm and datastructure with less/NO guess work or pattern finding stuff...
Could this round unrated or semi-rated?
I tried to solve div1C,and I succeed
But then，the problem changed,and I got WA on test 1
????
Actually it is a problem, but not a really serious one which can make the round semi-rated.
It is solved after 6 minutes the contest starts.
and not many people was doing C that time.
By the way, actually it doesn't waste much time. Isn't it? :P
Speedforces I miss the days when C was an interesting problem
Absolutely love the feeling when I have to wait for 3 minutes in queue just to receive the verdict, wrong answer on test 1
I think it's fixed now.
I am waiting for Julia to be supported to compete in these rounds.
Mathforces?
OMG...that didn't went well. How can everybody solve C and I do not see how?
I think because there exists cheating cases in rounds and this problem was like find pattern and get AC. Can anyone prove it with math or etc?
I wrote a brute force that worked in n*((2*n)!), and found a pattern (Only used cases n<=5).
How to solve D?
The idea is the same as
IOI 2019 Day 1 Split
First, we solve for star graph. Choose a constant $$$C$$$ in the range [N/3, N/2], then assign edge weights 1, 2, ..., C and (C+1), 2(C+1), ..., (N-1-C)(C+1).
How to solve for general graph? Root the tree at centroid. We claim that there exist a subset of children of the centroid so that their subtree sizes sum up to [N/3, 2N/3]. If one of the direct child of centroid has subtree size >= N/3, we're done. Otherwise, keep adding subtrees until the sum is >= N/3. Since each subtree size < N/3, total sum does not exist 2N/3.
Now, we use the same idea as star graph within these two sets and we're done.
Hey guys, how did you solve Div 2 D?
Let's ignore all vertexes with $$$a_i = 0$$$ because they never be in any cycle. So if there left more than something (I don't know exactly how many, choosed 500) that answer is 3. If there less vertexes then you can run $$$n$$$ bfs'es to find shortest cycle.
Why downvotes? It's pretty correct solution.
Yeah, I solved it this way — by limiting number of vertices (and I think 120 is enough).
Maybe the downvotes are from people who had the idea to limit the number of edges (like in the editorial) and think this is wrong.
The approach is simple compute for each bit i from 0 to 64, which all numbers have the i th bit set. Then if any of bit i have less than 2 numbers with that bit set, it will not affect and will not result to any connection. Otherwise if any of bit i have more than 2 elements, then the answer will be 3 always(take any 3 elements among those).
The case rises when we have bits with 2 entries. So maximum edges resulting from these bits will be 64. Considering these edges we can use out edge removal approach explained here :Find minimum weight cycle in an undirected graph
If no cycle then answer will be -1.
i copy pasted the code, still got WA in test 5 XD
Link to my solution
[Delete]
How to solve Div2 D?
If I used a vector to store the connected nodes I would get MLE.
And after that I got TLE by searching in O(n) for the connected nodes :/
https://codeforces.me/contest/1206/submission/59044914
Can anybody please share his / her approach?
If there exist three number with common bit you got the answer. Else build the graph which contains only few edges. Find shortest cycle in it.
How do you know which edges to include?
Which have a common bit in them. And bits are just 18*log(10)/log(2).
Nice zeroes in D.
Zero, nice body
is div 2 D based on that there will be max 18 edges ?
max 60
how ? i think for every bit there can be only one edge .
if 3 or more nodes have a bit in common then it answer will be 3, right ?
right, but there's like max 60 bits in 1e18
oh right, sorry my bad
can someone please tell me why my solution for E got WA?
I tried on my terminal and it works fine I guess. Can someone please find the mistake?
Welcome to Speedforces!!
I think, question Div2-C has some patterns about numbers but I could not solve it :( Could you guys tell me, if you've already solved it?
$$$a_i = a_{n+i} \pm 1$$$
Thank you so much
Think about it as a window of length n. In one turn a number enter and a number leaves. Alternate the difference = number enter — number leaves between 1 and -1, you can find then when the condition will be impossible.
The queue is dead, long live the queue!
The queue is feeble during the contest. And now it's gone. R.I.P
Интерактивка без предупреждений незаконно.
Для того чтобы уметь решать интерактивку, практически никаких предварительных специальных знаний не требуется (тем более, инструкция о вводе-выводе есть в самом задании).
Почему заранее не объявляют, что есть задачи на дп, графы, деревья отрезков и проч.?
Can anyone figure out what is the meaning of n odd in div2 E?
if n is even, then the problem is much easier! (try to think about it)
Oh tks. I figure it out.
Please ignore
Why is this true? Don't both corner squares still have the same parity?
Ah, you're right. I am misremembering stuff (I got pretests passed in last 10 seconds so adrenaline rush). My solution relies on the fact that there exists a 3x3 square in following pattern:
which is not necessarily true in even case, but true in odd case. Maybe that is author solution?
Div 2 D there these two pieces of code should be accepted :(
Wrong. If there just 500 zeroes then answer is -1.
Mathforces，Guessforces（
Thank you so much for this contest! Although have not done my best but really enjoyed it. Love problem E!
An outstanding round! Enojyed all the problems, especially D. My screencast will appear here as soon as it's processed.
Thanks :D
Editorial is published!
Really intriguing contest.
With the fact that I will get -108 rating for this contest, I still give it my up-vote
Why something like "Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices." was accounced in B? It's clear that it has nothing to do with making statement clear since it is crystal clear in this matter, it's just a hint to the solution about supposedly popular bug.
Oh really? I did not even pay attention to it lol
Откуда так много + за раунд ? Нельзя называть раунд идейным, если все задачи на одну тему. Лично от меня — уважение antontrygubO_o.
На какую тему все задачи?
Конструктив + слабые претесы
Не согласен, что претесты слабые.
Ну давай посмотрим на решения див 1Б . Большое количество человек написало ДФС и получило ва 74 ( Хотя ДФС в корне неверное решение )
Если только по одной из 8 задач упало ~15% решений, это не значит, что претесты во всех задачах слабые.
А что это значит?
Это значит, что претесты, в целом, хорошие.
Ну я как бы не математик, чтобы округлять в большую сторону ( по мне тесты слабые, путь это и в одной задаче)
Div2 D, E very good problems! Thanks for this round!
Thanks for extending this contest by 10 mins than usual. Finally, in last 30 seconds D1C got AC and I became master after a long wait :)
Same shit bro!
For those of you who get WA on test 14 for problem D on Div 2. You probably add some edges more than once.
Realized it after 6 wrong submissions :(
For problem D of Division 2, I would like to point out to everyone the existence of this problem: Problem: Find the Length.
The problem asks you to calculate the length of the shortest cycle containing a given vertex. Furthermore, N, the number of nodes, is limited to only 300.
How to limit the number of nodes you ask? In our problem, N can be 200,000! Well, for any given a_i, its representation in binary can be no longer than 60 characters long (2^60 > 10^18), the problem limit. Store the binary representation of the N numbers in an array, of dimensions Nx60.
Now, we have two cases. If there are more than 2 ones in any single column of our 2D array, then it means that 3 or more numbers are all connected to one another. This means that the minimum cycle length is 3, so we can output 3 and end.
Otherwise, the graph is extremely sparse. If there are only 2 ones in 60 columns, it means that there are a maximum of 120 ones in the binary representation of 200,000 integers! An integer must have at least 1 one in its binary representation. This means that, in the worst case, N is at most 120!
At this point, problem D becomes identical to the other problem. Simply use BFS or Dijkstra's algorithm to solve the problem. The runtime will likely vary, but most runtimes on the reduced graph will pass.
Note that the fact that a_i can equal zero can be a problem. Since 0 bitwise-AND with anything (including another 0) is 0, you can simply ignore that a_i.
Thanks to this contest, I learnt that depth first search doesn't generate all simple cycles of the graph(which maybe a common sense for lots of people, but wasn't for me)
It implicitly does, you just need exponentially more time to actually find them.
Got WA on test case 28 in Div2D. Can anyone figure out the mistake ? Link
you need to clear "vis" before every dfs, i had the same problem
I have refreshed the vis array.
Using DFS to search for shortest cycle in a graph doesn't work. Consider this graph: 1-2, 2-3, 2-4, 4-5, 5-6, 6-1, 6-3
Say you start your dfs from 1 and it traverses like this:- 1->2->4->5->6->3
Back-edges found are 6-1 and 3-1, both of which give longer cycle length.
But dfs is done from all the vertices So it should find the smallest cycle.Right?
Its all due order of adj vertexes.
With enough bad luck, your order of vertices in adj list could be such that dfs can't find shortest cycle starting from any node.
Thanks. Got it !!
Loved the problems: less coding, more thinking. But I was confused by the phrase "It can be shown that the answer always exists" in 1205C - Palindromic Paths. It led me to thinking that the answer is not unique — but there is actually no condition that it has to satisfy, so it was not clear how is our output validated (as soon as it does not contradict with out queries).
I would phrase it like "Your set of queries should unambiguously determine all cells of the grid". Actually the first time I would appreciate something like "Vasya filled the grid with ones and zeroes, and you have to figure out the entire grid by asking him queries" :) Anyone had troubles with this or is it just me?
When the goal is to print a correct solution in an interactive problem, there must be at most one correct solution.
My solution, which was "find 2 possible grids, find a query where they give different answers", makes it clear that you can decide if there are 2 indistinguishable solutions or a unique one. That's a big benefit of this approach.
True. My solution was exactly the same, it is just before the last step I started thinking: do I really need to choose between two? Probably I am just spoiled by no-brainer statements like in 1023E - Down or Right.
Yes, I noted it as well that saying "It can be shown that the answer always exists" is a complete nonsense xD. Checker has some hidden board and answers some questions about it, such a statement makes no sense at all, it is not some constructive problem where answer satisfying some constraints may exist or not.
Could someone explain why am I getting an overflow error despite using long long which can store a number upto 10^18. This is my submission 59048621
use: ll nw = 1ll<<j; 59052313 see, you passed TC5 by using 1ll :)
Thanks for the help. Could you help me figure out the reason for the TLE. I think my code should pass given the constraints. Thanks in advance 59052813
long longhas limitation as well. usually it's 64 bits. and if you try to shift number4(which in binary form looks like100) 63 times — then you'll get an overflow. docsbut he's saying 1<<j not 4<<j to get overflow
my bad, didn't notice, that thought it was not
i << jJust remember, every time you use long long and want to write a number like 1 or 0 put an ll after it like 1ll or 0ll
Long queue(4-5 mins) during the contest is an upsetting thing :(
Could someone explain why I am getting TLE. I think my complexity is within limits. Thanks in advance. Here is my submission 59052813
Because you use cin. Add the following lines: ios_base::sync_with_stdio(false); cin.tie(0); Or use scanf();
because you wrote N^2. imagine a big TestCase where every number is the same and they're binery form is 1111.....111. in every DFS you look at all of them, even though you dont visit them. so N nodes visited in DFS, in which you look at all of the N other nodes to check them if you have visited or not, so N^2.
there is a trick to this problem, don't want to spoil it, but imagine what would happen if you had 3 numbers who would share the same 1 bit an 100000 other nodes...... what would the answer be, and why? think :D
Are you hinting towards the fact that the dfs should be performed in order of component size for faster execution, If yes, how would that improve the time complexity. I still feel it would remain the same, ans is the answer to your question 3?
yes the answer is 3. so in your vector vals[64] for every i if(val[i].size>=3) the answer will be 3 either way. so in worst case every one of them will have size 2, it means in worst case you would have 128 nodes in total. so..... you could make and Adj_List for those 128 nodes, so you only have the nodes you need and their relations.......
Yeah I just understood the trick.But I don't know why my code is failing at Test case 75, I find everything fine. 59054630
i checked the TC. I suspected that dfs wouldn't work for this problem, I'm actually suprised it got to TC75 :D if you draw the TC, you'll see what the problem is. but for how to solve the problem use bfs, and use the fact that bfs visits every node in shortest time possible while the edges are the same size, dfs doesn't have this property, it just merely visits every node. if you check the TC, you'll understand what I'm saying..... good luck :D
I completely got what you said.Thanks for helping out so much and being so patient.
no problem, happy to help :)
i did not mean that about dfs, i just meant you have made number of edges in total something like N^2...... so dfs turns to (N^2+N)
can someone tell me the name of algorithms that solve the contest question? I would like to study them
For problem D,you can use floyd or tarjan to find the minmum circle
In problem C the judge is not printing -1 for more than n^2 queries... wasted so much time thinking i am getting wrong answer instead of qle.. :(
I wanna know whether the problem in Div.1 C has a solution when the element (1,1) isn't 1,element (n,n) isn't 0.For example,(1,1)=0,(n,n)=0.
Consider the grid where it's all 0s or the grid where it's all 1s. You can't distinguish these via any queries.
Grids
101
011
111
and
111
110
101
are undistinguishable So 1 in top left and 0 in bottom right were important.
I'm rk1 in Div2 untill D&F FST.now I'm nearly rk1000 TAT
Why i am rated? I registered for the div2 contest 10 minutes after the start of the game！
you're still an official participant.
how we can know the path that we ask in Problem E (div 2) ?antontrygubO_o
like ? 1 1 3 3
path A : (1,1) , (1,2) , (1,3) , (2,3),(3,3)
path B : (1,1) , (2,1) , (3,1) , (3,2) , (3,1)
the rule for move is known as move to right or down and both follow rule
so which one is correct ? i read problem statement like 5 times and i didn't find anything guided me to know which one is correct ...
please help me ^^
and sorry for bad english ...
If at least one of all the paths is palindromic, you will get 1, otherwise you will get 0