Hi!
I'd like to invite you to join in Codeforces Round #411 that will be held on May 4 at 17:35 MSK.
Actually I didn't do anything for this contest :) and most of the contest is prepared by my good friends saliii and MohammadJA. Also amsen, Navick, tundra, kastarika and I helped them in testing problems, writing statements and these sort of things. At the end, Thanks to KAN for his huge help in all of the contests and MikeMirzayanov for great Codeforces and Polygon platforms. (Sorry if there's someone I didn't mentioned, This is everything I know).
Each division contains 6 problems (4 common problems). Hope you enjoy them.
The round is rated and score distribution will be posted soon and good luck and have fun and hope you high ratings and all the other words that should be told.
UPD 1 Contest delayed by 10 minutes.
UPD 2 Contest delayed by 5 minutes. :)
UPD 3 We can see the scores now in contest page.
UPD 4 Contest is finally over, Hope you enjoyed the problems. Cause of technical issues editorial will be posted tomorrow.
UPD 5 And here are the top5 in each division:
Div1:
1-riadwaw
3-al13n
5-zeliboba
Div2:
2-_ISB_
3-Dipak
And also congratulation to hahaschool, MKyzy and shanin who solved problem F in div2.
UPD 6 Editorial is ready now.
I hope the problem statements will be clear, short and easy to understand like this blog :'D
Me too XD
How much will the round last? I see that it's a non-standard round (having 6 problems).
L.E: oh, it's 2 hours. I didn't check out the contest tab
"good luck and have fun and hope you high ratings and all the other words that should be told." is like saying "wish you all the best" in happy birthday
A round at the beginning of the summer vacation, What's better than this :)
It's a round on the last day of high school for me :)
It's the beginning of our final exams, What's worse than this :)
begining of our 4th sem exams and my first codeforces round... fingers crossed!
GOOD LUCK
I was hoping for a Star Wars contest in the announcement.
Two Impressive Setter's Profile saliii & tundra from today's contest
I hope problem statements won't say us to assume all other words that should be told :p
Hope there won't be any other "HOS" in statments :D
Why did you think at this way?
Already having a Hir in blog
So what is the common thing between "Hir" and "Hos" else 'H'?
Ask Batman
I want test you!
6 problems and 2 hours.WOW!
Maybe they are too easy...
hopefully the statements will be short !!
Or you are too strong
Or I didn't even read the problems :)
Really ?
Some of them :)
Actually I didn't do anything for this contest :)Sorry if there's someone I didn't mentioned, This is everything I knowall the other words that should be told.Wow... It's... Awesome..
great context of my Friend :)
30 minutes before the beginning of the contest and score distribution hasn't been posted...
8 minutes remaining now
I asked them from saliii, But he didn't answer me...
Maybe it will be good if CF implements a feature to reveal scoring distribution automatically, say 5 minutes before the round.
I prefer more than 5 minutes, but I'm agree with you.
Well, the delays usually do the job :D
I've never understood why scoring distribution always has to be revealed at the last minute. I mean, why couldn't they reveal it when they first made this post?
may be it is something to do with the number of registered participants ... just a guess
Don't worry. I'm aware that problem D is easier than C (for me at least), LOL.
My guess is, to prevent people from using well-thought-out strategies. Making you think which problem to start first, second, and so on right before the contest boosts your adrenaline :D
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
Good luck for all!
Why the delay? I know I'll never get an answer.
extension by 10 has become common
Agree, really disappointing.
Thx for delay :) I'm in bus getting home right now
thanks again :D I even finished eating
Probably, still not decided on score distribution
late-10minutes.
one of the worst things about codeforces contest :(
who's girlfriend missed the registration?
checked yours? :P
I have no girlfriend :'(
so sad.
so sad, wish you have a girlfriend before the next contest. :D
Your pray is guaranteed. Still, have a girlfriend. Pray next for better thing.
Don't worry, She must waiting you to find her. just patient.
Then, we are two. I'm in the friend zone since past week :o
A codeforces a day keeps girlfriend away.
GLHF
Maybe server was unexpectedly fast, so they must make delay to see what is wrong :P
We saw that, maybe we can see scoring distribution next?
Yes maybe, that's not impossible.
Also it is not possible.
These numbers <3 :'D
Blin che za nesereznost'?
Just 2 minutes till to learn scores of problems :P
Contest delayed 5 more minutes LOL :D
and now 1 min !
and 6!
and now 6 min
U say what?
WTF? :D
Refreshed page 5 more minutes :(
and now 5 minutes!!
Maybe it will be dynamic scoring :D
While I am seeing just dynamic start time :)
Maybe 12 minutes or more.
Why need to delay? I mean I'm okay with seeing scoring when the contest starts
I think there's another problem...
Again 5 minutes late.So sad:(
Contest delayed by 5 minutes.
Again Delay!! :(
Delays ... Delays Everywhere
I can only say:
UPD 2 Contest delayed by 5 minutes.
How did you know that? :DDD
he is GOD :)
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
The 7th problem is almost ready? :)
Перенесите, пожалуйста, еще на 10 минут, мне надо сделать чай
= ChamrAn what is the score distribution ? -read the problem statement
hahahahhaAhaha
UPD 2 Contest delayed by 5 minutes
CF is delaying the contest little by little so we don't understand that thank you CF :|
If this contest gets pushed back any further I'll be late for work...
I hope this round wont cancel at the end of the delays
Can we have an announcement about these delays or not? :/
2.5 mins next?
No. That's too predictable. We'll make it 15 next time.
And here I was hoping for a GP.
Therefore the total delay is 20 minutes? :P
Please stop playing with my heart.
A first delay is ok, A second one? that's irritating
Why the contest is not starting?
Ребята, вы задолбали раунд переносить! Вы что не в курсе, что это настрой сбивает? Не участвовали в олимпиадах совсем? Если вы что-то не успели, то лучше переносите на следующий день, а не на 15-20 минут.
Я специально из дома работаю сегодня, на завтра ни-ни!
They are doing Binary search on delay . first 10 min, then 5 min... :|
In this way the contest will never start :)...paradox
Good point, hahaha
Now i regret i upvoted the blog...
Contest delayed by
minutes
it shows that contest will starts at end!
What the Fuck, Dude
Is it dalayed? Twice? Or have a bad computer?
Oh sorry I didn't see the update announcement :P
Annoying : delay
More annoying : second delay
Most annoying : people complaining
Mostiest annoying: people complaining about people complaining
Mostiest annoyingest: people complaining about people complaining about people complaining.
Expecting: Due to the delays starting the contest. This contest will be unrated.
breaks keyboard
Haaaahaa
Delays are for the people using Internet Explorer.
The scoring is going to be a surprise this time :p
Quite frustrating when you reschedule everything in your day so you can fit the codeforce's contest but it keeps delaying.
So we have infinite geometry series, next delay will be 2.5 minutes, and 1.25 minutes, and so on, so total delay time will be 20 minutes to sum up. :)
Or they'll be like 10, 5, 10/3, 2.5, 2, etc st the contest will never start, how can we know?
Waiting for next delay.
No delay :p
Надеюсь что раунд запомнится главным образом не задержками, а задачами P.S. Да, запомнился) Блокировкой задачи после взлома и необычной сложностью задач)))
I'm sleepy...
long time no cf :)
You know what? 100 rating points on another 5 minutes. :)
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
Long queue :(
Hack page is not loading. :(
I waited 20 minutes for the page loading to hack a code, and then it tells that the code was hacked !!!!
EDIT : 4 codes
I dont like rounds where if you are put in a room where everyone solves the problem right you cant participate well :(
long queue :s
Queue is driving me MAD!
In queue :(
And at this moment Jackson knew... He f***ed up
I've been waiting forever for the hack form to load.
What was approach to solve problem D?
Make a little observation and you will get it.
result of aaab is same as result of aab+aab and you get 3 a's at the resultant string.
So, the recurrence you get is R(n) = 2*R(n-1)
Little bit more observation will show that taking R(0) = 1 works for all cases.
And the initial sting aaab was available without any transformation. So the answer will be R(n)-1 for this case. Now, think about what you do for the case aabab, and you will know the solution.
"Bubble sort" all 'a' to right side of string, count all swaps. On every swap 'b' becomes doubled.
What is the hack for C (Div.2 E)?
what the hell??? I hope this contest won't be rating
Why?
Maybe
2 5
0
0
1 2
Or something like this
maybe each node has 0 element in their set?
I was hacked by the test where no ice creams are given in any set. So i was outputting total colors as 0 whereas it should be 1(color all of them the same).
NOOOOOOOOOOOOO I'M SO DUMB
Great. That bull#&! testcase made the difference between ~+120 and ~-50 rating for me (according to rating estimator extension)
You're not the only one, buddy.
For me problemset was like AAACDE but still nice though. I think may have missed something in one of problems ABC, so are there any special cases except l == r in A?
How to solve D?
IF we have string with 'a' and n 'b'-s, it becomes 2*n 'b'-s and one 'a' after n operations. Then start from the end of the string and every time you will have string of this type, so you count operations you need and new number of 'b'-s
Probably go from left to right and count 'a'. If encountered 'b', then ans=(ans+pow(2,count_of_a)-1)%(1e9+7) Because of my very stupid mistake I got AV test 13. I just precalculated powers for only first 32 arguments....
I did something like this before:
count a from left to right and count a, if I encounter b then ans = (ans + (1 << count) — 1) % (1e9 + 7) but still not pass pre-test 6 Not sure why, then I tried going from right to left, also fail
Gonna wait for the editorial then ..
Well 1 << count can easily overflow. You should use binary exponentiation instead.
Think of it as sending every 'a' to the end of of the array, by operating it against all 'b' on it's right. If we start from the rightmost to leftmost 'a', there will be a contiguous (subarray) stream of 'b' for each 'a'. The number of 'b' will double for each 'a' that passes it.
Found this during the contest but couldn't figure out anything. Can these things actually help to solve E?
How to solve E?
The graph class you should be looking for is chordal graphs.
.
It seems to be a happy hack round. :)
How to solve Div1C/Div2E?
BTW, End sem aa rahe hain :P
Very bad contest Problems are very bad and first 4 problems very easy to div 2 and hacks are overrrrrrrr
Does a character string (example char s[200000]) have junk value towards the end ??
I'm just curious: is it so well-known that an empty graph is considered a connected subgraph? I've had this doubt during the contest, but somehow this phrasing got me thinking that it should have at least one vertex. Shouldn't this be an aspect worth clarifying in the statement?
Graph has non-empty set of vertices. So rejudge or unrate should be done.
Many hacks have been done with empty subgraphs in the input, which is a bit unfortunate.
Source?
Russian wikipedia, at least
English wikipedia suggests an ambiguity too:
"Moreover, V is often assumed to be non-empty, but E is allowed to be the empty set."
I would not assume any re-evals will occur though
I don't think that round should be unrated. Seems that the best way is accept all hacks, but rejudge solutions without such tests.
Do authors and coordinator KAN even read the comments? Anyway it is a fault in statements, and we see no reaction.
Yes, I read comments. We will think how to resolve the situation.
So, what was decided in the end? I am not insisting of anything, just asking out of curiosity :)
First, this test was indeed a hack test.
Second, I think that in this particular problem the ambiguity was much less than in general question "is the empty graph a graph?". Of course, it would have been better if we had explicitly mentioned this in the statements. But now, I think the best option is to leave it as it is.
I think the ambiguity was exactly the same, which is also confirmed by the fact that authors haven't made such tests. If the problem was "count the number of connected subgraphs in the tree", no one would consider the empty graph. If not mentioned in the statements, it must have been tested by pretests, because it is clearly a matter of understanding the problem.
Leaving it as it is is the most unfair for those who wasn't hacked. But I don't see the better option now too.
"First, this test was indeed a hack test."
Does it mean that organizers didn't provide it or it wasn't added to systests?
There were a lot of hacks added to systests, and there were no such tests in the testset provided by organizers.
Yeah, and array has non-empty set of elements, and string has non-empty set of characters.
Source?
Not exactly: https://en.wikipedia.org/wiki/Null_graph
"Some authors exclude K_0 from consideration as a graph"
Still debatable ...
If there are two valid interpretations, but the problem doesn't specify anything like "sum of si's must be positive", it seems like the problem setters want to allow null graphs.
If there are two valid interpretations, there is a serious issue with the problem statement.
Well, the input criteria (all si are allowed to be 0) seemed to clear up the ambiguity.
For instance, don't you sometimes see problems where the text says something like "subsequence" or "substring" and only later when you read the input specifications you figure out it is contiguous/nonempty/etc?
Actually si being equal to 0 is irrelevant to the problem of empty graph (because even if all vertices had sone color it is possible that some color is not present in the graph)
E.g consider testcase
Makes sense. I was thinking more in terms of the case when all si are 0.
But the problemsetters haven't made such tests, see my comment below.
Yes, I agree this is the real issue. Perhaps the authors aren't even aware of the ambiguity.
Note that even if the problem setters didn't add the ambiguity intentionally at the first, the problem setters could've announced a clarification during the contest. Certainly, there were questions about the ambiguity and author must have been aware of it. Therefore, I can say that the problem setters intentionally created the ambiguity in a sense.
"Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph."
Misinterpretation can happen here if you do not consider null graph as graph .
As cited: "To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."
A null graph is connected.
I agree that graphs generally have at least one vertex. The problem's context (it's possible that all si are 0) led me to believe otherwise.
Actually I just saw this:
"Please note that we consider that empty set of vertices form a connected subgraph in this problem."
This does fix every issue I said. :D I don't think there is anything wrong with this problem (except checker issue discussed down in comments).
This phrase was added just recently.
To prevent confusion, I'm here to say that this part was added after the contest to make sure no one face this issue later.
"To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."
I agree that graphs generally have at least one vertex. The problem's context (all si can be 0) led me to believe otherwise.
Well, if you consider empty graph a graph, it's obvious it's connected (I mean definition is that any pair of vertices is connected which is true)
Whether it's a graph is a good question, though
But you can't say that an empty graph is not connected? Unless you can provide two vertexes, that aren't connected by any path.
Definition of a path is a sequence of edges which connect a sequence of vertices. If you have a path containing no edges, then there is no path, correct? Therefore your empty graph is not connected.
I agree that there are many interpretations, but I believe the problem was ambiguous enough to warrant a rejudge
The empty graph is definitely connected. "For every pair of vertices in the graph, there exists a path between the two vertices." is vacuously true, since the set of vertices is empty.
That is not entirely correct :). A graph with only one vertex and no edges is usually considered connected. But you have just proved that it isn't.
My point was that an expression, opposite to graph being connected is "Exist u,v from V such that there is no path between u and v". You can't select anything from empty set thus it is not correct, thus empty graph (if it is really a graph) is connected.
Moreover, seems like all tests with empty subgraphs are actually hacks. So it's fault not in statements but in validator.
My solution for E is way too simple to be true. How to solve E?
In Div1 E is the answer YES iff n=2^p, n!=2?
No, the answer is YES iff n = 4k, 4k + 1. Proving that 4k + 2, 4k + 3 doesn't work can be done by looking at the parity of the number of cycles in the cycle representation but I couldn't find a construction for 4k, 4k + 1 in contest time.
answer is yes when n ≡ 0, 1mod4. For n ≡ 2, 3mod4 the answer is no. (which is clear, because trivial permutaiton is even so the number of transposition should be even and
is even only when n ≡ 0, 1mod4.)
Construction is harder. But I guess one should use the following identities:
(12)(34)(13)(24)(14)(23) = e
(1x)(xy)(y1) = (xy)
Yeah, I knew the parity argument. I could only come up with a construction for n=2^p so I kind of assumed that was the only case.
ok. The full solution is:
when n = 4k + 1 construct first for 4k then using (nx)(xy)(ny) = (xy) plug inside all (n, 1), (n, 2), ..., (n, n - 1).
when n = 4k + 4 then construct first for 4, 5, ..., 4k + 4 by induction. Put (12)(34)(13)(24)(14)(23) at the beginning. And plug inside all (1x), (2x), (3x), (4x) as we did in the first case.
DIV 2E
I was thinking that each node will form a clique of size number of icecream in that node i.e if there are 3 icecream in a node in T, then there will be a clique of size 3 for that node in G. I found maximum size of clique and colored nodes such that no 2 items in a clique will have same color.
It failed on pretest-3. Am I missing something?
I think every vertex set will form a clique. And every clique will have colors = size of clique. I don't know what else to think.
Why so much math and greedy? I don't know about E and F though. I solved E by greedy that i did't even understand why it passed the pretest ?_?
Have I understood the problem E correctly? There is no meaning to use edges between vertices in the given graph T?
agree with you
Same. I do 2 clarifications and still don't understand what is the use of edges in the tree..
Yes, it guarantees there won't be contradictions between nodes. Also you can fill the answer in the order of tree traversal.
What's the point of tree?
So the new constructed graph will not have cycles.
For example: {1,2}, {2,3}, {3,1} can't be nodes on a tree. (vertices which have the same type of ice cream form a connected subgraph)
Can you please explain with a sample case?
This is invalid.
can someone explain why this is invalid??
The new constructed graph will have cycles if vertex set size >= 3, right?
I meant, vertex set of given tree, not the new one.
No, maybe you missed this:
Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.Hmm, I think what you mean is, after compressing each clique to one node in the new graph, we have a new tree. Am I right?
Yes, G was a "tree of cliques".
You could use the tree to assign the colors greedily correctly :)
I now understand why input has to be a tree. Otherwise, we might have clique of cliques. The solution only works if G is a tree of cliques.
The "every ice cream forms a connected subgraph" condition means nothing, unless graph is specific. In case of a clique any pair of vertexes are connected. That means there are absolutely no restrictions. You can easily reduce any vertex coloring to it.
3 задача самая легкая
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
When problem C is about finding yourself :D
I was sure my solution for C is correct, but obviously it is not :)
Is asnwer always max(Si) ?
Is it even a div2 E level problem!
When there are 6 problems? Yes.
So the solution is the size of maximum clique size?
Yes
I didn't solve it :D I have no idea what is wrong , but possible I am a little stupid.
Nope, look at this case:
4 4
3 1 2 3
2 1 4
2 2 4
2 3 4
1 2
1 3
1 4
[DELETED]
This test case violates the fact that vertices with color 'i' form a connected subgraph. Consider color 2.
I edited the testcase. I think it is valid now..?
UPD: Sorry, no, it is still wrong.
Again it is not valid.
I was right. But I do not know how I missed implementation part.
Yeah...
I also thought the same thing as you did, but then I came up with invalid testcases like this one! -_-
No, because all Si can be zero, but you should answer 1. XD
And yeah, this test is used as a hacktest on the contest. Many contestants missed this including me at first.
Div 2 A — D problems were almost two liners. xD
For me it's an advantage. I prefer enjoyable thinking to tons of coding (often frustrating).
but there weren't much thinking either...
It depends on the skill level of participant.
agreed, I personally find A-D too easy, while I can't understand what E is asking, so i give up. Anyone mind explaining what E is asking for?
In my Div2 B
link 1 — fails pretests
link 2 — passes pretests
Any help ??
Does setting s[n]='\0' matter ??
Yes, it does.
Thanks I got 2 wrong submissions because of that !!
when you're dealing with string as a char array, it does.
500-500-500-1500-2500-3000
In C (Div.2 E), not including a test where all vertexes have sets of size 0 is like purposely making a 'hack problem.'
Shouldn't hacking not be about something like that?
Nice contest overall though
Did anyone have trouble understanding F? I still don't understand what the problem is asking for, and I wasn't even sure where to start in terms of clarifications. Maybe one question is, do the coin transfers happen all simultaneously at each hour? Is there a fixed number of hours? Usually, when I see 10^100, it suggests that we let a random process run until it converges, but I don't see any randomization here, so that's probably another reason I got confused.
Here you can consider 10^100 inf.
The problem ask for this:
For each gang consider that after 10^100 hours it has a[I] billions at first and it has b[I] billions now.
Each of them will have a number of accepted billions between a[I] and b[I].
Police sort them in increasing order and choose a gangs from top and choose b of them.
What is the number of choosing b gangs.
Ok that makes a bit more sense. I guess my other question would be how exactly does the tranfer process work? It seems we have the i mod s_i thing which seems not to suggest splitting indices up by gcd. Also I guess you also split the gangsI into strongly connected components and solve those individually. I believe there is a cycle involving arbitrary gangs within the same strongly connected component. Can you check my understanding is correct?
It works till they see a completely same state that they saw it before ( it happen before 10^100 hours)
Does the selling and trading happen in separate stages or can they be mixed together?
Ok, I think I finally figured it out. Here is what was confusing to me.
There are two distinct parts to this problem: 1) Compute for each person, can they eventually receive a fake coin? 2) Afterwards, there is the math problem that you mentioned above.
I was very confused about part 1, and was not sure how to interpret the statement. For example, a sample explanation explaining the process would have helped greatly in clearing up any confusion, and I don't think it would have made the problem easier. Because I wasn't able to figure out what part 1 was, I didn't even get a chance to think about part 2. It was only having the interpretation with part 2 in mind was I able to correctly decipher what the statement was asking. To be honest, I think statement is unambiguous, but I don't think it was clear or concise.
Also, as a side note, my solution is O(sum s_i + n^2), but it takes 2.7s. Is there a faster solution in mind?
I'm happy that you understand this problem.
I agree with you that the statement wasn't clear enough but it changed at the last moments, I read the last one and that was clear, for some changing in problem they change the statement.
I was tester of the problem and my solution works in 700ms.
Гневные многобукаф, но не мог не высказаться.
Ребят, я конечно все понимаю: то, что сервера не выдерживают такого наплыва народа и все дела, но это происходит уже не в первый и даже не в пятый раз: почти каждый раунд на протяжении нескольких месяцев почти постоянно возникают какие-то технические проблемы. Вот вроде перенесли сервера в датацентр мейла, а все равно такие же очереди на 30 страниц, десятиминутное ожидание вердикта, негрузящиеся страницы и как результат — пропадает фан от написания контестов. Точно ли ведутся работы в направлении того, чтобы это побороть?
А еще очередной хакфест в Div2A. Сколько можно? Авторы и координаторы, разве это действительно хорошая идея — делать тесты так, чтобы тупой
print(2)проходил все претесты? Конечно, давайте запустим волну взломов и повесим очередь к чертям, чтобы народ еще дольше ждал своего вердикта, а места в топе распределились в соответствии с тем, кому в комнате больше невнимательных людей попалось и кто успел их всех нахачить. Очень весело, да. А остальных заставим обновлять страницу комнаты в ожидании новых сабмитов: народ же все равно не будет читать сложные задачи — зачем они вообще нужны?Мне всегда казалось, что вся идея хаков состоит в том, чтобы найти кейсы, до которых не додумались авторы при составлении тестсета, а тут вот оно как дело-то обстоит. И страдает из-за этого вполне приятный проблемсет с интересными задачами.
Honestly , speaking , questions weren't clear . Some had multiple answers but there wasn't any clarifications regarding this. :(
well most of them informed that if there were multiple solutions you could print any.
How to solve Div2 F/Div 1D ?
You can find for each component its diameter and the distance from each node in that component to the furthest node.
Now you need to find the average for combining two components.
This can be done in O(n * m) time where n is the number of nodes in the first component and m is the number of nodes in the second. However, this obviously wouldn't run in time. We can speed it up greatly by knowing the average diameter will just be (avgA + avgB + 1) Where avgA is the average max distance of all nodes in the first component and avgB is the same for the second component. However, this isn't always true. In some cases, connecting two nodes will not extend the diameter further than it currently is in the two components.
Thus, we need to count these cases where the diameter doesn't change. We can do this in O(n) time where n is the number of nodes in the first component.
We will for each node, binary search which node we can connect it to such that the diameter doesn't change. (We will have all distances of each component in sorted order so we can binary search) Then we can do some math with cumulative sums and cumulative averages to subtract out the appropriate portion and add back what we need knowing that all of these pairs will result in an unchanged diameter.
This brings our runtime down to O(n * q * log(n)). This is still far too much. However, we can do two speedups to get it to run in time. First, we can memoize the answers we find for each pair of components. Thus, we will never need to deal with the same query more than once. Second, we will always do the linear loop on the smaller component. This will bring our runtime down to O(q * sqrt(n) * log(n)) which is good enough for the time limit.
Use 2-pointers will decrease the Time To : (n+q)*(sqrt(n))
You have to be very careful doing a two point sweep there. If each pointer always gets to go its full distance, you don't get the sqrt(n) speedup and your runtime is O(n * q).
Why after last optimization you do, complexity turns to O(q * sqrt(n) * log(n)) ?? Can you prove it please ?
Let a1 ≤ a2 ≤ ... ≤ an be the sizes of the trees in the forest, and qi the number of times tree i is the smaller tree in a query. Also, let
and 
The runtime is
. We can forget about the 
term and multiply by it after we're done. Now,
The second term in the inequality comes from the fact that if
we must have 
(because the ai are sorted, so in the worst case every ai has 
elements greater than it.)
Edit: lmn0x4F did this in an earlier comment below, sorry about that.
Very nice explanation tbuzzelli, could you give some insight about the sqrt(n) in your complexity analysis?, I have some sign that could be like it, when the sizes of the each tree in the forest are: 1, 2, 3, ..., x and this sum is equal to n, for this x = sqrt(n), and now answer the querys is as you say O(q*sqrt(n)*log(n)), is it correct? What is a better analysis for it?
mckkentmwk,
Because each component will only contribute it's size for all things larger than it, it is fairly easy to show that in order to maximize runtime, all the components should be the same size. Now the question is, how many components should we have.
Let N equal the number of nodes in our graph and let X be the number of components. Our runtime would thus be q * (N / X). However, each query must be unique because we memoize. Thus q <= X^2. Therefore our runtime is actually max(q, X^2) * (N / X). Let's assume that q = X^2 because any excess queries would just be repeats and are trivial to handle. Now we have a runtime of X^2 * (N / X) = X * N. We want to maximize X. Because X^2 <= max number of queries, X should be sqrt(100,000) which is technically sqrt(N) in this case because I considered the variables for bounds on N, M, and Q to all be the same for Big-Oh runtime analysis.
I hope this makes sense. It is a fairly common runtime as if X is too large, the pairs don't contribute much and as X gets too small there just aren't enough pairs to make a large runtime. Feel free to message me if you have any further questions.
This is such a nice and simple speed up! Did you came up with this during contest or is this something somehow common?
Also, could you elaborate on where did the sqrt came from? I thought something like:
For each query we find U, V (connected components) with U ≤ V.
This leads me to something like
Is there other way to think about it?
Thanks :)
So as long as we only loop through the smaller of the pair, we can show that our runtime will amoritize to q*sqrt(n) if we make sure to never repeat the same pair
This is a fairly common speedup. In order for us to get a bad case, we need the max of n and m to be as large as possible where m and n represent the sizes of our two components.
Because no pair can be repeated (because we memoize) the worst case on queries will be if we get every pair of components given to us(this may not be possible if the number of components is large but we will assume we can have an infinite number of queries for now). Thus, if we query every pair of components, our runtime is the sum of min(n(i), n(j)) for all (i, j) pairs. Therefore, for each component it only contributes it's size to our runtime the amount of times equal to the number of components greater in size than it. If we have two components of size n/2 we will have O(n/2) just for that but then we have little to no nodes left. It turns out that the way to maximize this runtime would be to have sqrt(n) equal size components. This brings us to the sqrt(n)*q runtime. The log(n) part is because we binary search ontop of that.
This is a well known technique, introduced in IOI 2009
Я один не понял или другие тоже ? Зачем в задаче Е даются ребра первого графа ?
Ну, я запускал dfs по первому графу
Так быстрее искать смежные вершины в новом графе — нет нужды перебирать все вершины, достаточно пройтись по связному подграфу dfs'ом
Затем, что важно условие "образуют связный подграф". Иначе быстро не решить
Потому что если к примеру перебирать вершины в порядке увеличения индексов и для каждой вершины красить все не покрашенные, как сначала делал я, то существует контртест, 3 2 1 1 1 2 2 1 2 1 3 3 2 Ты покрасишь 1 в 1 цвет и 2 в 1 цвет.
That feel when you realized you did not fix your own bug before hacking others :(
How was DIV2C/DIV1A supposed to be solved? :c
(n — 1) / 2
Thanks
When you are that one guy -_- (Div1 A, somehow thought that answer on 1 would be 1 :D and then locked it immediately) :D :D
Ставь лайк, если тоже получил TL в С((((((((((((((((
Дизлайк, если тоже так и не понял, почему в A не заходит writeln('2');(((((((
Для теста 3 3 ответ не 2
Will the system testing be today itself??
I believe it should start in less than an hour like normal.
How to solve Div2 E?
What was pretest 3 for Div 2 E ? I used DSU for finding connected subgraphs and assigning colors incrementally to each node in each subgraph !! WA on pretest 3
how this code get AC http://codeforces.com/contest/805/submission/26862337 and this get TLE ?!!!!!!!!! http://codeforces.com/contest/805/submission/26850899
How ????????????????????????????????
Edit this code get AC how !!
http://codeforces.com/contest/805/submission/26864979
They both rejected. Pretests are just pretests you know.
yeah! but see this one!
http://codeforces.com/contest/805/submission/26850369
Magic does exist!! Wth? how did it passed.......
that's the power of "constructive algorithms", it may looks illogical, but that's how the world of math works lol
Div3 contest difficulty
Ice cream coloring : "Wrong answer on test 131" :((((((
i have wa143
I have never seen so much systest fails as Div 2 E.
It depends on your room xD
Pretest Passed/Accepted ratio for Div2 E O__O
how do you check that statistic ?? in submissions ??
[deleted]
Sorry I found a bug in my code.
Stop crying.
What it was?
Just removed this line with swaps at all and get OK:
http://codeforces.com/contest/804/submission/26864400
Sorry, man, too difficult code.
GG me lost :( Every time I gets near that purple bar I always go haywire lol. Curse of the Expert is strong with me.
I have attempted a hack on solution submitted by user: exp1ore. I thought and I still think that his solution should get a TLE verdict. Problem:805A — Fake NP His submission:26862337 I have seen similar brute solutions receiving TLE verdicts, can someone please clarify the situation? Similar solution receiving a TLE verdict: 26850899 WTF, the same person I have tried hacking just got a TLE verdict in an even smaller case 26862337
here is one of them :D http://codeforces.com/contest/805/submission/26850369
WTF, the same person I have tried hacking just got a TLE verdict in an even smaller case 26862337
how can this code pass without tle? he ran a loop l to r and got AC!
http://codeforces.com/contest/805/submission/26850369
such a powerful server ... lol
How come nobody hacked it ?
Tried! but unsuccessful! :D
When C was more solved than A ... (Div 2)
It's not C div 2. It's n div 2 lol.
Wow! This wa129 on div1c on everybody's solutions makes it look like authors themselves made 0 tests with number of icecream types greater than maximal number present in data. That's the quality!
Yeah, rip rating :(
[DELETED]
By the way, may I wonder how many author solutions failed on first hacking attempt in div1c? :D
I have an argument that the tests that failed a lot of people in Div1C are invalid: how is T "a tree with n vertices and m types of ice cream", as the task described, if some of those m types DON'T APPEAR on the tree? I think it is perfectly valid to assume that each number WILL occur at least once, because otherwise the tree actually has less than m types of ice cream.
I liked a suggestion someone said above on fixing this: keep the hack scores, but remove these tests and rejudge the solutions.
Why so? If m=4, the tree can have only one ice cream of type 4. The other three are available, but not used. But this is not illogical. Unusual, but still valid.
I forgot to cast the function size of vector to long long in problem F div 2 :'(
Кто-то может объяснить как решать D? Потому что как я понял "Разбора нет, но вы держитесь..."
Процесс закончится, когда строка будет вида b...ba...a (иначе найдётся подстрока ab). За каждый ход b и a меняются местами и кол-во b увеличивается на 1. Рассмотрим какую-нибудь b. Она должна поменяться местами со всеми a, встречающимися левее её. Но за каждый ход кол-во этой b удваивается. Значит, с первой a левее её она совершит 1 ход, со второй — 2, с третьей — 4 и т.д. Пусть f(i) — кол-во a левее b, стоящей на i-той позиции. Тогда для этой b кол-во ходов будет равно 1+2+4+8+...+2^(f(i)-1) или 2^f(i) — 1. То есть общим ответом будет сумма 2^f(i) — 1 для каждой b в строке.
Div2 E Test 143
Input
Correct Output
How ?! 1&2 are in the same set of node 3 so there is an edge between them how could they have the same color?
That's your output to the test case. The correct output is:
Oh!, I'm so sorry I didn't recognize that xD
It is not correct answer, it is your output.
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
The output for Div1 C for the following test case:
3 6
3 1 2 3
3 4 5 6
2 3 6
1 2
2 3
For most of the solutions is:
3
1 2 3 1 2 3
But as you can see vertices 3 and 6 are adjacent and cannot have the same color. Most of the solutions seem wrong or i don't understand the question.
the colors form a connected component
Basically the ice-creams in each set form a clique and the tree structure doesn't matter, right?
Why All of my submissions show skipped? All of them are passed in system test.
Because your code matches with another person's code may be. Did you copy pasted ?
No, I did n't.
My code for Problem C (Problem E for Div2) produces wrong colors, e.g. color values out of range(<=c) and for some tests even prints more than c colors. But it gets AC. Plz check...
26864974
UPD: I didn't mention that this code got AC...
Yes the checker doesn't even check that number of colors used should be equal to c, like in test 3, 5, etc.
Printing max(1, maxSi) and 1 2 3 ... M got AC (26865288)! :D
Thats a serious problem with the checking policy. Not expected on codeforces.
lol max
Ping KAN
Even max(1, maxSi) is seems wrong to me. Eg:
3 3
2 1 2
2 2 3
2 1 3
1 2
2 3
Since all 1, 2 and 3 ice-creams are adjacent to each other, the number of colors required should be 3.
your test is incorrect. 1 and 3 have color 1 and are not connected
Node 1 and 3 has same color but not making connected subgraph. So it doesn't meet problem description.
The vertices that have 1 don't form a connected subgraph.
I guess i did not get the question. Could someone please elaborate?
http://codeforces.com/blog/entry/47258?#comment-316511
It looks like the range was set to [1, M], not [1, C].
26865686
Oops this is a serious problem. We will investigate how many people are affected by it. If this number is large, then... unfortunately you know what it means. If there are only few people affected, we will think.
The result will be delayed as it takes some time to analyse the problem.
It happened that only one person was affected by this bug, so this is a bit of luck to us, no rejudge needed.
Nevertheless, it doesn't cancel my error. Sorry about that.
I have a feeling that, the only person was the judge himself .
Could one of the writers please provide the full test 25 for problem F in div2? I get a negative result. Not sure if there's a bug in my code (which I can't find) or a problem with overflows (on long long or double).
EDIT: nevermind, I found the bug.. I was forgetting a cast to long long
I am not getting why if in DIV 1 C I call dfs first and calculate the value later then it gives WA..
Try that test:
Thanks ... Got it ... :-)
The tests in D are somewhat weak. My solution 26859777 uses two pointers instead of binary search and works 50s on test with one component of size n / 2 and n / 2 components of size 1, queries are all pairs of type (large component, small component). After changing to binary search, it works 0.6s.
we have ten of such tests! but seems you passed them.
¯\_(ツ)_/¯
Speaking seriously, could you share a generator for them? I think it'd be useful to fully understand the situation to prevent such issues in future. Could be a bug in generator, for example, or we simply misunderstood each other on the test structure.
Yes, Of course. The correct generator should be this.
We tried many time-limit-exceeded solutions, and they successfully timed out. But about your code, I don't know.
Hah, seems like I was testing in Debug mode. I've run it on other machine in Release mode and my code works 3.1s on my test and 2.3s on your test. The difference between them is that I use a path as a large tree.
So
operations is ok for modern computers :)
UPD In run mode my code 26877753 works 5.3s. So the tests are weak still.
UPD2 I changed generator in several ways to make the same test that I used in my solution — still works 3.1-3.5s. Don't know what's the difference now.
UPD3 If I output my test in file and then read it instead of generating in the code, it works 3s too. C++, you make me crazy!
I have a path, too. In the last test. And I don't have any Idea for better tests.
Yes, see the last comment. Reading my test from the file speeds up the solution somehow. I have no idea why though.
After all, we are guilty. I must tell you sorry about the problem. We could lower the time limit.
Then there would be more solutions with correct complexity receiving TLE. Honestly I don't know how to prevent passing of my code without cutting these solutions. Furthermore, many
solutions were faster than 
solutions, so you can't cut the first complexity.
If graph coloring is NP-complete, why is it possible to solve div1-C (Ice cream coloring)? I solved it but can't understand why the same idea cannot be aplied in a general graph.
Then why can't I see the code in your submissions?
As for the question, the structure of the tree is extensively used in the solution: the vertices in the subtree of v are handled after v. Take a careful look at this thing in your solution, if you've really solved it.
This is a fake account, real account is ordan , he don't want to get downvotes.
Oh, so surprising (no).
Imagine the dfs while "remembering the colors".
You are on some vertex, there are c slots for colors (u1, u2, u3, u4, u5, ... uc) ui has been colored using color i. If you go to some next vertex and some ui inside some slot isn't there, you can open this slot. If there's some new ui, you need to find some empty slot to fill with ui. Since the subgraph that has only the points that have ui is connected and the original graph is a tree you will never have a path from inside ui to outside ui and back inside without going back inside through the same point that you first went outside. This means that if you start the dfs from the point that has the most colors, when you go to some other point you will always have enough slots for new colors (if you are using all slots and some new ui appears, some uj will disappear) and you will find only 1 color for every single ui (you won't try 2 colors because you will enter its connected component only once).
How did this solution pass ? :D
http://codeforces.com/contest/805/submission/26865714
KAN Batman
KAN replayed it here.
Дурацкий контест, это был забег на скорость
первые три задачи уровня див2А четвёртая уровня див2Б
у 17ого места задач как у 1808
Я по результатам систестов прыгнул со 160 места на 25, было занимательно)
Div1C checker is wrong. Div1D tests are weak (some participants got AC with O(n^2 + q * sqrt(n))). I think this round is even worse than the previous one.
also hacking was so much important to get high rank, which is really bad in my opinion.
Technically, C never claims anything about G. The part which mentions that an empty set of vertices is a connected subgraph is referring to the constraint on the original tree T. G is never defined to be connected and is not even connected in the samples.
Furthermore, no where does it claim that all colors must be used. I do agree, however, that it is somewhat stupid to have a problem with such an easy break case for people to hack with.
-Edit- -Edit 2- (the following clarification was apparently added after contest) The part that says "Please note that we consider that empty set of vertices form a connected subgraph in this problem." makes it clear that not ever color needs to be in T. This definition would be unnecessary if every color was present.
This comment wasn't there initially. I (almost) always open all tasks at the beginning of the contest (just in case of cf technical troubles). It seems that the comment was added without any notification.
UPD: lol, not even before the end of the contest. Seems that it's for future submissions and isn't supposed to affect the results of the contest.
I'm pretty sure this comment was added recently.
Oh. I didn't know that. Thank you for letting me know.
http://codeforces.com/contest/804/submission/26865288
как это решение прошло?
UPD: там просто количество цветов правильное выводится, сама раскраска вообще неправильная.
UPD2: Вот еще одно такое же решение — http://codeforces.com/contest/804/submission/26866214 Мало того, что оно тоже неправильное, так еще и копия прошлого.
Выше в комментариях можно почитать, что с этим уже разбираются.
Да, уже заметил.
the checker for 1c is broken
and why 1a 1b are so trivial?
Wll there be an official eitorial?
I'm sorry,but I get confused with div2 problem E with this input :
Some AC code get the output with
But actually the output should be
Could anyone help to explain me where am I wrong?
UPD1: Thanks for tfg in the previous input vertex
3 1 2 4and vertex2 3 4are not connected in the induced subgraph with only these two vertices.Here's a brief for dfs algorithmThat's not a valid input since the vertices with 4 aren't connected. "Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph."
Can anybody explain me the Div 2E.I'm getting a WA on third subtask. Every set of vertex v will form a complete subgraph. So the minimum no. of req colors is size of the subgraph. Is this true?
Problem E (div 2), "Each vertex i has a set of si types of ice cream. Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph." Does this statement hold for the graph G which we are trying to build ? Does it have any use ?
wow ! 26865501
Reyna is my hero:)
JUST WOW, you guys did it! Finally amazing INTERESTING problems (despite technical issues with tasks and translations in div1C) I'm looking forward to ur next contests!
Editorial ???
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
Why there are 2 UDP5 ? :)
UPD: Fiexed
Cause I copied that and forgot to change it :).
Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
in div2E: the reason behind that the sets where given as nodes in a tree with edges between them is that the order of filling the colors of the new graph nodes is guaranteed to be correct using DFS, for example in a case where n=3, m=2, node1 has set with color 1, node2 has set with color2, node3 has set with colors 1 and 2:
1) using a normal loop you will check the set of node1 of the tree (having color1) and assign node1 in the new graph with first unused color in the set which is 1 (for example if set with colors 4 and 5, node4 is assigned color1 in the new graph, and node5 isn't assigned yet, so first unused color is 2), then you will check the set of node2 of the tree using the same strategy (so node2 of the new graph will be assigned color1), which will make a contradiction because colors 1 and 2 are in one set in node3 of the tree which wasn't checked yet.
2) using dfs if you started from node1 of the tree and checked its set and assigned node1 in the new graph color1, you will guarantee the next node that you will check its set is node3 (because nodes having color i form connected subgraph), since node3 and node1 both have color1 in their set they will be connected in the given tree, and since node3 and node2 have color2 in their set they will be connected in the given tree, and since this is a tree node1 will never be connected with node2 (cycle), so since you will move from node 1 to node 3 in the dfs you will assign node2 in the new graph the first unused color in the set of node3 of the tree (which is color2) and no contradictions then.
note: in the contest time i didn't notice this so mine failed in system test (test 143)
brilliant explanation
when does the contest start in India? please reply with Indian standard time.
What?
The contest finished.