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 ChamrAn and MohammadJA. Also Hifdah, Navick, Folorn, 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:

3-al13n

4-cki86201

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.

hi

don't hate me

why? because you are a little boy?

you are very funny that send message with my account and reply to it ...

see her interview

Two Impressive Setter's Profile ChamrAn & Folorn from today's contest

I hope problem statements won't say us to assume

all other words that should be told:pHope 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 sa1378

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 know`

`all the other words that should be told.`

Wow... It's... Awesome..

greatcontext 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 ChamrAn, But he didn't answer me...

And the contest has been pushed by 10 minutes :)

good luck to everyone!

Hoping to solve some problems before exam..

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 Sa1378 (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

Hey Mr, you trying to get some fake sympathy here dear?

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!!

And now 4!

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 Sa1378 (previous revision, new revision, compare).The 7th problem is almost ready? :)

Laughing so hard at this!! =))))

= ChamrAn what is the score distribution ? -read the problem statement

hahahahhaAhaha

ffs we have finals

And again ... !!!

UPD 2Contest delayed by 5 minutesCF 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...

another 5 mins :)

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?

They are doing Binary search on delay . first 10 min, then 5 min... :|

In this way the contest will never start :)...paradox

Not in machinary computing case! >D

Good point, hahaha

Why So Much Delay ? :(

Now i regret i upvoted the blog...

Contest delayed by minutes

it shows that contest will starts at end!

Accepted

What the Fuck, Dude

5 more Minutes pleaseIs it dalayed? Twice? Or have a bad computer?

Oh sorry I didn't see the update announcement :P

dalayed...

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 keyboardHaaaahaa

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

I'm sleepy...

long time no cf :)

You know what? 100 rating points on another 5 minutes. :)

Auto comment: topic has been updated by Sa1378 (previous revision, new revision, compare).Long queue :(

Hack page is not loading. :(

Solved 2 cant submit any so quitting this round

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 :(

I think Div2 A, B, C, D are too easy. Most people solved them in < 1 hour. Maybe system test will prove me wrong.

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

s_{i}'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

s_{i}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

s_{i}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

s_{i}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

s_{i}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

s_{i}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. Forn≡ 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 whenn≡ 0, 1mod4.)Construction is harder. But I guess one should use the following identities:

(12)(34)(13)(24)(14)(23) =

e(1

x)(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 4kthen 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.

Auto comment: topic has been updated by Sa1378 (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(S_{i}) ?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.

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

a_{1}≤a_{2}≤ ... ≤a_{n}be the sizes of the trees in the forest, andq_{i}the number of times treeiis the smaller tree in a query. Also, let andThe 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

a_{i}are sorted, so in the worst case everya_{i}has elements greater than it.)Edit: pulgares did this in an earlier comment below, sorry about that.

Very nice explanation GeometryMaster, 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) withU≤V.Ugets visited at most times in total.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

The first & the second of DIV 2 have never take part of any previous contest !? Congratulations every one and best of luck in the next contests :)

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

Today was not your day mate :(

The first & the second of DIV 2 have never take part of any previous contest !? Congratulations every one and best of luck in the next contests :)

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