Hello everyone!
Codeforces round #385 will take place at the unusual usual time of Saturday, 17 December 19:35 MSK.
Thanks to the following people for making this round possible.
 LiChenKoh, xiaowuc1 for helping develop problems and discussing ideas with me.
 winger, AlexFetisov for testing the problems
 GlebsHP for all his valuable help with the round.
 MikeMirzayanov for the great Codeforces and Polygon platforms.
As usual, contestants will have 2 hours to solve 5 problems. Hope you will enjoy the problems!
Scoring will be announced closer before the round.
EDIT: It may be helpful to read the Interactive Problem Guide before the round for both divisions.
EDIT 2: The scoring distribution will be unusual:
Div2: 5001000150022502750
Div1: 5001250175022502500
EDIT 3: While you wait for system testing, here is a quick editorial: http://codeforces.com/blog/entry/49126
EDIT 4: Congratulations to the winners!
Div1:
Div2:
Interesting problem setters. Now, i'm more eager to participate :)
Deleted...
I am sure that this round by lewin will contain interesting problems(not as previous two rounds).
Clashes with COCI #4. It would be awesome to move it to 20:xx MSK (a hour later).
** ** *****?
yes ! :D
***
hope not to see comments like "is it rated?" or "usual time"
wandererS : ** ** *****?
Is it rated ?
Found it funny:"unusual usual time"..:)
nice tags
Till now I found out that lewin is fantastic setter. I hope another , balanced problemset !
When I see interactive task I know my rating will go down :D It would be nice to say before contest which task is interactive, for you it is not big deal for me and probably fot many users it is very important.
it's ( div2C/div1A ) or ( div2D/div1B )
we will need less than 2 minutes to find out :D
Why not div1C?
Again interactive! every time I see and I think well! I can solve it :D but then I say — Sorry me! :(
So you saw a lot of interactive problems. Interesting :)
After seeing the tags and round description, I'm wondering, if we will have to interact with cows...
moo?
Wondering how to hack the interactive problem?
The statement always explains how to.
sometimes source code can't be seen by double click or ctrl+clik after lock my submission, it shows only submission history. why?

thanks lewin for suggesting to read the interactive problem guide. i would have wasted some time in the contest to learn how to solve interactive problems. i never solved an interactive problem.
This contest seems to be better one.
It seems that codeforces is cleaning up its inventory of problems before Christmas...
Today Petr is participating :) ,any guesses in which language(Java/C++/both) he will code in todays contest ?
Hope the interactive problem will be interesting.:)
tourist vs TooDifficuIt vs Petr
vs allllekssssa
I bet on allllekssssa
At least I have the biggest opportunity to change color :D
to blue ? :D
Yeah :) it is relly bad to do following three rounds unofficial :D
Clash of titans xD
Finally... =)
vs WJMZBMR
aka "how the heck did he lost rating as a rank2/3"
vs jcvb vs Um_nik
Do we need to flush cin? Like not using cin.tie(NULL);
Four contests in a row) Four contests in 3 days) Real happiness...
And all of them are Rated :D
Good luck! I hope more Experts will be Candidate Master!
*** ****** ** ?
Is Codeforces trying to implement "Boxing Day" algorithm from the England Premier League? Xp 4 Codeforces round in 3 days. That's something worth living for...
4 Codeforces !! are u arsenal fan :v
Excited for interactive problem!Hope i could solve it. Thanks lewin.
I have registered for the div2 contest but I am not able to see the problems. What should I do.
Contest has not started yet! its about 1 hour 44 minutes to go.All the best!!
I did realize that later, I actually thought that contest was supposed to start at 8:05.
Hope to provide a grader for the interactive problem :/
ICPC REGIONALS ON 22ND, UNIVERSITY PRACTICALS ON 22nd Onwards.Ladies and Gentlemen . Codeforces will always be there, when you need to get high.!Thank you codeforces for the contest series this week.
Bad timing for manchester united fan.
Considering the amount of people who are trying to find out how interactive problems works and sending submissions and how hard it works right now on problem "Guess The Number" do you think it will be ok during the contest?
Deep♂Dark♂Fantasy (TooDifficuIt, jcvb, WJMZBMR) in this round they will decide who will be the captain
Deep♂Dark♂Fantasy(TooDifficuIt, jcvb, WJMZBMR) and they still have the same number of legendarys
I hate registering using the lower bottom, hope in this round I can reach Div1 and use the upper one
I guess I'll cheer you on since I like the problems you write :D
Hi I new to this platform. Today I will be solved by second contest.
I was wondering why the newer comments go to the bottom rather than addition of comments to the top.
Thank You . Jai Babe di.
You are going to be solved? XD
He is the problem, you know... =)
When You Write Problem statements like Div2 B .
at least I can make you understand what I mean.
And also Don't Worry Be ruski
Good luck everyone! lewin always writes interesting problems.
I hope there will be lots of math questions!
Explain B problem in Div2
DIV2 B problem statement :(
what is the explanation DIV 2 B means?
How can by one movement to right ..... XX... ..... ..... .....
be formed ??
they said two identical copies. I think that's your ans. although I couldn't solve the problem!
Div2 Problem B ..So unclear problem statement. It does not even make sense to me :(
Damn right!
I am done with this contest. I am either really stupid or other people who are solving this fast are really geniuses.
I just love Ruski English.
GGWP ;)
In Problem C Div2 "There is at most one edge connecting any two nodes " and the graph is undirected :/ How is that possible if graph is undirected?
I think it means that there is at most one undirected edge connecting two nodes i.e no parallel edges.
In DIV 2 B , is it 'x' or 'X' ?
X
thanks pretest passed !!
in problem B DIV 2 why this test outputs no? 3 3
.XX
XX.
XX.
I will get my eye sight tested I cannot understand what was meant by their problem statement.
But interesting problems though. ;)
Especially D.
I guess we cannot move the individual "X"s. I first submitted the solution based on checking whether "X"s form a rectangle or not. Then thought we can move individual "X"s so checked if there exists a,b such that # of "X"s = a*b. If a<=n and b<=m, said YES else said NO. Then decided to hack solutions and then realised after unsuccessful hacking attempt that we are wrong. We have lost this round brother!
yes i was hacked on this case . you cannot move the X's which is poorly phrased on the statement .
But then how
5 5
.....
..X..
.....
.....
.....
This outputs YES?
Because here the single X is the complete puzzle. I failed in English and not code skills. Sad life. Wish I hadnt submitted it again.
.XXXX XXXX. XXXX. or .XX XX. XX. .XX XX. XX. It can't be rectangle
How can you make a rectangle using two such pieces?
say why yes > know why no
Can I delete my last accepted solution? I only need another one to be verified...
Only last successful submit will go to system testing.
the problem statement on B is extremely weird !
Hacking, hacking everywhere!
Ok, it was really great contest))
Does anyone have a hack case for Div. 2 B?
2 3
XX.
.XX
Answer is NO.
There goes my B solution...
Could you please explain why its NO?
I'm not sure if I understood properly but why cant you arrange it like this: .XXYY. .XXYY.
(Rearranging the tiles in the puzzles and putting them next to each other. Y are the tiles from identical board)
Why is it no? Can't you slide all pieces to the right on the first piece and then slide all to the left on the second piece so that it looks like:
.XXXX. .XXXX.
Why is the answer NO? Cannot we make it as
.XX
.XX
and the other one as
XX.
XX.
and combine two pieces
It mustn't intersect and you can't change the figure.
How do they intersect?
We cannot change individual X positions within one piece. I misunderstood the question :(
"The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."
Doesn't this mean you can change individual x positions?
You can move only puzzle pieces not the part of the puzzle pieces. I think it sounds confusing, but russian version is ok.
Yeah my bad. I should've asked for a clarification but the other way of understanding it didn't even cross my mind in contest lol.
.XX XX.
XX and XX form a single piece(4 connected).
No, you can move only a whole puzze piece, not parts of them
The puzzle piece has to be one of the following types:
1. Rectangle
2. Horizontal segment
3. Vertical segment
If the figure formed by 'X' symbols does not belong to one of these 3 types — the answer is
NO
. Otherwise, the answer isYES
.Petr may reclaim his second rank today.
and he has done.
How to solve Div2D and Div2E?
Div2D: example: n=8 ask1 : 1 3 5 7 ask2 : 2 4 6 8 ask3 : 1 2 5 6 ask4 : 3 4 7 8 ask5 : 1 2 3 4 ask6 : 5 6 7 8 then answer for the 1st row is min(answer2, answer4, answer6) answer for the 2nd row is min(answer1, answer4, answer6) answer for the 3rd row is min(answer2, answer3, answer6) etc The idea is to consider the binary form of the number. Ask 1 and 2 is for the least significant bit, 3 and 4 is for the second and so on.
How to solve the problem about the table game?
If I pass system testing this will be my best contest ever...fingers crossed wish me good luck.
btw what was the hack for DIV 2B ???
:)
UPD: It passed.
:) UPD2:finally blue...here I come Div 1...
I don't know if it was the hack case but my first submission passed pretests and failed for this case:
3 3 .X. XXX XX.
Answer is yes. My first submission was awfully written though (so was my second lol) so maybe it was just me that was wrong on this.
How is it yes?
I think I may have misunderstood the problem.
4 4 .... XXX. ..X. .... I did like 4 hacks :)
Answer is yes right?
what should the answer be ???
No
I hacked a solution using this test case
4 4
....
.X.X
.X.X
.XXX
The answer should be NO
Statement for DIV2 B could have been better.
How to solve Div 1 B / Div 2 D?
I kept dividing intervals in n/2 and asking for 2 questions each. For n = 1000, it asked 21 questions somehow :\
Edit: it seems the approach was correct as in editorial. However the last question was redundant and trying to find values on the main diagnol only
Please explain your solution.
Suppose you want answer on a table NxN. Then lets query n/2 numbers twice, the first query questions indices 0, 1...n / 2  1, and the second query questions indices n / 2...n  1. Graphically, this means you know all information for the bottomleft and topright of the current table(verify this with a picture). Now recurse on the topleft and botright, notice that they still have the diagonal with 0's.
I think this is what he meant.
I don't see why this is right. I thought the same thing. Obviously, binary division was involved, given the constraints, but I couldn't prove it's correctness.
Yes exactly, this was what i was doing. For the topleft and bottomright, part you can divide them into 2 new sub matrix and solve for them too. However direct implementation of this will lead to no of steps as f(x) = 2 + 2*f(x/2). However each of the queries on the leftside and rightside are disjoint and one could merge it into a single query too. That would make f(x) = 2 + f(x/2)
As for why its right, it is effectively searching all the matrix values
Your implementation sounds exactly like what I tried as well, unfortunately it seems I had a flaw in implementation.
I finally understand :) So, its 2*log(n) .
for each bit i, do 2 query, one for all the index whose ith bit is 0, one for all the index whose ith bit is 1.
now for row k, we only check the reply which desn't contain M[k][k], that is, those query that checks ith bit different from k's ith bit.
UPDATE: M[i][i]>M[k][k]
My approach was, first I split all N numbers in two queries by taking groups of 1:
1 3 5 7 9... and 2 4 6 8 10...
then I take groups of 2:
1 2 5 6 9 10... and 3 4 7 8 11 12...
then take groups of 4:
1 2 3 4 9 10 11 12... and 5 6 7 8 13 14 15 16...
and so on.
With this queries you can test every element in the matrix, and get the minimums.
Problem B pretest cases were extremely weak, I couldn't believe some of the passed solutions that I hacked. rankings in Div.2 are more influenced by number of guys with bad solution in your room than time penalty. I think pretests should be stronger, so hacking would be more challenging.
I agree, one of the people I hacked just checked whether there exists a rectangle that has the area equal to the number of X's. No idea how that passed pretests.
I did the same, but I also checked that the number of X inside the rectangle is same as the area of rectangle.
Agree, I hacked 8 submits with easy hacks like
My first ever hack!
Pretests passed in Div1A by reading edges first then capitals — such strong pretests :( — http://codeforces.com/contest/744/submission/23053839
AlexDmitriev had the same problem :(
I took revenge from the guy who hacked him and me: http://codeforces.com/contest/744/room/12 :D
To be honest that was not the only my problem in A
Really sorry about this. This is definitely not intentional. I think the way to fix this would be to make sure to include more pretests in general (for this problem, we only had 7, which in hindsight is really small).
Div 2B question should have had a clear statement.
"The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions." is very confusing. I thought that the pieces could be moved independently of each other and only understood why my answer was wrong in the last 10 minutes.
When the initial statement read "It is guaranteed that the puzzle pieces are one 4connected piece", I thought that only referred to the input and not that the pieces had to remain connected throughout.
Nice questions in Div 2 otherwise.
Yeah I thought the same. It could've been a really nice problem if it wasn't for the unclear statement.
I hacked 3 C solutions where their logic was as follows:
ans=nk+1;
ans=(ans*(ans1))/2;
ans=ansm;
If any of you did this, it is wrong.
Counter test case:
6 2 2
1 3
1 2
3 4
Correct answer is 5.
LOL, this solution is really retarded. The pretests are really weak if it worked.
Div2 B is the worst problem I have ever seen in CF
I'm sorry you feel that way :( I tried to balance a short statement versus a clear statement. It seemed it was too short on details.
Thanks for your effort though! It was a good problem I think just very unclear (at least for me).
It's alright, you tried your best. Other problems were very good. Just that this problems statement should've been a bit more clear :)
Other problems were great...thank you very much for your effort..
I was sad too.
But then I had a bhangra session to enjoy life.
DIV2 E test3?
That moment when you discover your bug 30 seconds after the contest ends T_T.
can someone figure out why my code is giving Idleness limit exceeded on pretest 2 even though I am flushing many many times?
(bug is probably in n<3 part since pretest 2 has n=2)
http://codeforces.com/contest/744/submission/23071215
I have tried finding the error for the past hour and have used 8 incorrect submissions on this problem :
disclaimer: i am CPPer
shouldn't it be like this? (corrected n < 3 part)
I first submitted a correct submission on div2B and then got confused, changed the code so that it outputs wrong on some cases, and submitted it! :(
Similar thing happened to me, but I noticed in time and changed it back. Still lost 10 minutes :C
I found 2 submissions with the same implemention http://codeforces.com/contest/745/submission/23067444 http://codeforces.com/contest/745/submission/23067030
I just read the first one and i didt understand why he used big integer with this problem, but i think the cheating detector will find it soon :)) (hope so!!)
getting 3rd place with a stolen code, seems legit
I have taken almost 20 minutes to understand the problem B in div2 :(
Same here, the funny is I submit a solution without understanding the problem and got pretest passed !!
I should practice more hard
So what's the right solution for B? Check whether it's a rectangle? Or what? Even C is easier than this.
Yeah, I can't say with confidence that I know, even though I passed pretests... I just made sure the input was a rectangle, since you can always combine two rects to make another rect.
Then why there seems to be such a confusion about this problem? This was the most obvious thing to implement.
Yeah, I guess a lot of people have confusion about what a 'piece' is. Many believe you can shift individual 'X' characters in any fashion you like, where the problem statement says that 'X' characters come together to form one connected piece which must be shifted as a whole. Many people don't quite understand the intent of the question, so hopefully we are not one of those people.
But didnt they say that you could move pieces in any direction?
So technically even if the input is not a rectangle, it may form one on rearrangement.Did I miss understand?
By puzzle pieces, they mean the big given grid, and not individual X's
Oh my god....
So basically you have to paste one grid on top of another and the resulting 'X's should be a rectangle(with no overlaps)?
I hope so, because that's what I did. :)
You comment should be part of the problem statement ;)
Yes, it has to be a rectangle. There's no other way.
considering the problem conditions , main problem will be this : check if in the input exist only 1 rectangle or not ? if there exist exactly 1 rectangle without any 'X' more print "YES" otherwise print "NO"
is it even necessary to have govt nodes Number in Div 2 C ? if i iterate over all nodes to do the dfs anyway ?
Of course they are needed, you can't put edges between vertices that are connected to some capitals. The example contains such a test.
shit i am f*cked.
Both problem statement & pretest cases of problem B were really very weak.
That weird moment when you get pretest passed without understanding the problem at all and pray to get hacked before it's to late :P
And when it get hacked...you start to read and understand the question again :(
That weirder moment if you get accepted instead without understanding the problem
This contest was nice but the pretest for Div 2 B sucked...like they weren't just bad they were the worst...my friend solved an entirly different problem and got pretest passed...
but other than that it was great.
:)
in the problem B DIV2 it says in the statement " The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."
and now you say i can't move peaces how is that ?
Well...you actually can. But you'll get a rectangle only when the pieces are initially rectangles. I don't understand the confusion about this problem.
.XX
XX.
this is not a rectangle but if i moved each peace in the first row one step it will be rectangle
I don't understand you, how can you get a rectangle from to pieces that look like this?
XX.
XX.
this one peace if i have two peaces it will be like this XXXX.. XXXX..
there are two copies.
The confusion is whether they meant the board as a whole is a 'piece' or do they mean the 'X's as the pieces?
If we consider the latter, then the input does not have to be a rectangle originally.
Div2/B is just horrible, nice Div2/C BTW I got pretest passed in the last minute.
Why Codeforces nowdays testing user's ability to understand problem statement???
Why not? ;)
Because it's not an English language testing platform _
Why did this guy _index solved the problem A in 2 minutes and problem B in 6 minutes?
He said he read the statements in Russian where they were clearer (according to him).
Ok, TheMaverick is definitely not russian (and has a badass toxedo) :)
He solved B in 9 minutes.
theodor.moroianu is from Romania and he solved B in 4 minutes!
What are you trying to prove here saying "He" solved B in "T" minutes?
Do I really need to clarify?
Did you see how many people failed in the system test in problem B?I don't think there is any corner case in this problem.
So do you want us to believe that they all got the statement right and coded wrong?Seriously?
"you want us to believe that they all got the statement right and coded wrong?"
No, I wanted to say that 1240 people understood the problem and coded it correctly. And I wanted to say that for the people with enough experience B wasn't a problem at all. Understanding the problem correctly (however unclear it is) is, I believe, a part of the problem solving skills.
If tourist or Petr participated in Div2, they would have solved A and B in no time =)
Div2 B, they said "It is guaranteed that the puzzle pieces are one 4connected piece." and didn't accept rotate, flip and overlap. ==> only move. Because there are two copies of puzzle, only rectangular input is accepted. no stairs shaped, window shaped...
Problem statements were really confusing _
Problems were fine, statements were trash
hahaha
Lets see how many solutions of B pass system test.
As I understand now, the code I wrote is COMPLETELY wrong.
Yet,it still passed pretests and a hack too...
In Div2, Only a few could solve D or E. The gamechanger question was B whose problem statement was horrible. People have submitted considering individual "X"s can be moved. This round should be made unrated for Div2 as B has clearly caused complete turbulence.
I never saw weak pretests being reason for unrated contest.
Weak pretests + confusing statements + D,E were very hard.
The only times I've seen contests be unrated are when the queue is bad. I think there was one contest where the judge solution for Div 2. D was actually wrong and they just removed the problem instead of making it unrated. So today will probably be rated.
Then how come some people understood the statement correctly? Have you ever played jigsaw puzzle? The question clearly stated two puzzle pieces. It should've occurred to you that 'X' != puzzle piece when you saw the first sample case.
When people go undercover to make the contest unrated.
The contest can not be unrated just because of a problem statement.
Also many were not able to give time to D because they were stuck in B.
I really liked Div1 B!
Problem B not passed — nooooooo! So it's actually wrong to output yes when the piece is a rectangle.
Not true, mine passed. Probably a bug in implementation.
Wow, that's even worse. The pretests are so weak.
I have a question. I wonder how people can solve Div2 B, though they are confused about it... Is it a gap between me and high ranks?
I'm definitely not a "high rank" but because of weak pretests, it's possible to "solve" the problem without actually understanding it. For parts that were unclear for me, I assumed parts of the problem that were actually incorrect but worked with the sample cases. And with passed pretests, it made me think it was actually correct (when it wasn't at all).
I agree with you. I had the same experience before.
Is it rated ? :p
downvotes coming .. Hell yeah 'B' is worst ever B of mine on CF. _
Before the contest : ** ** *****?
After the contest : ** ** *****? xD
The pretests for Problem B DIV2 is very weal i got pretest passed and i don't know even what is the problem is .. and Now i got Wrong answer and i still don't know the problem .? could someone explain what the problem ?
find out if the surface covered with 'X' forms a rectangle
It would've been Problem A with an understandable statement but they made the statement so confusing so that it would have the difficulty of a B problem..
3 3
X.X XX. .XX
i understand that we can make rectangle with this by shifting?
You're not allowed to shift 'X' You can only move left, right, up or down the whole matrix (the whole piece)
You have to get a rectangle by appending two identical pieces. You can get that only if you have a rectangle in the given piece.
oh man thank you very much =D . i see it's easy now
You're welcome :)
welp, this was unexpected
I take 'he is allowed to move them in any directions' as 'he is allowed to move X in any directions' in the statement of problem B. Actually i was solving a different problem and i got pretest passed.
Waiting for rating
The statement for problem B (division 2) was very poor!
whatever....what about ratings???
Div1 is still undergoing system testing.
system pending wasnt faster before ? :"
Let's hope rating will be updated in 25 minutes, otherwise there will be few lucky div1 participants who can participate officially in tomorrow's round. ;)
When can i upsolve problems? cant submit any solution now! there is no option ! if i click on 'submit code' tab, its shows 'contest is over'!
You have to wait until system testing is over and ratings get updated, then the problems will be available for practice.
Div.1A, test 15. Are you sure that given graph is stable?
You are reading capitals after the edges, but they are given before them.
Thanks!
Surprising part is that it passed 14 tests..
You should read capitals first, then edges, not vice versa.
Goodbye Expert...
Where is the new rating?
div1 updated Div2 on queue
C approach:
let k be the number of governments
Make k subgraphs such that each of them contains one government node (k strongly connected components), so v_{i} nodes with government.
Note that there will be, let say p nodes in anarchy (no government) with p_{e} edges between them.
We will attach those nodes to some of the k subgraphs and generate the maximum number of possible edges. (No node can be attached to two different subgraphs)
Let g_{1} be the edges generated by
Let g_{2} be the edges generated by
Let g_{3} be the edges generated by
We agree g_{1} has a fixed amount, thus no decision with the anarchy nodes will influence its value.
Then we need to see that g_{2} ≤ p * (p  1) / 2  p_{e}. We can't have more edges between p nodes than the possible pairs of them. Any solution with g_{2} = p * (p  1) / 2  p_{e} has an optimal value of g_{2}. Any solution that set the p vertex in the same group has an optimal value of g_{2} (1)
Note that adding one anarchy node to a group with government generate v_{i} edges of type g_{3}. (denote v_{i} the original amount of nodes per group).
If j is the subgraph with more nodes then v_{i} ≤ v_{j} with any subgraph i
where c_{i} is the amount of anarchy nodes that go to the subgraph i
As c_{i} * v_{i} ≤ c_{i} * v_{j}
this means adding all anarchy nodes to the group j implies an optimal g_{3} value, cause equality is obtained. But if we do so then all anarchy nodes will be in the same group, because of (1) g_{2} is optimal As g_{2} is optimal, g_{3} is optimal, and g_{1} is fixed, adding all vertex to greater group is the optimal solution.
After doing so we count the amount of nodes and edges per group and solution will be
where e_{i} is the amount of edges that already exist per group
Total complexity: O(n)
Tutorial on C — The simple made tough
it's a simple problem and you can figure out the solution intuitively. This is not the solution, but the proof of it.
Start the upsolving, please
When can we submit for problems??
Well, just 1 far from expert :( Look at my graph
Sleep well and tomorrow you'll have a chance to get blue :)
I think something is wrong here one code with 2 different verdict (hack, accept) 23067626 , 23072618
I think there is a problem on codeforces , i can't do anything on the site
look here
I've been having such a problem for a couple of hours, though :/
Me too. I can't see my own submissions, which is quite annoying.
is there any tutorial on C Div.2 ? i tried to solve it but i can't find out what's the problem :( i think the solution might be DFS , but i feel like i'm missing something ...
When I go to any of the problems a message says "No such problem"
and all my solutions in this contest disappeared
and my graph is updated and the rating still the same ,
does anyone have the same problem ?
it seems like everyone is having this problem, idk why, the rating is still the same but the color doesn't change though.
I just fixed it , you have to change your ip address (by restarting your router or whatever)
Anyone know what testcase 15 on Div1A/Div2C contains? I'm failing on it.
Try this case; if you count this edge ?
It seems that your program can solve this case.Then i have no ideal what's wrong with your program.
Even I am failing on that test case. The test case is large enough ! So no gain.
You need to make all components cliques.
Say capitals are 1 and 4.
you have to make an edge 8  9 and connect that component to any other, adding 3 * 3 = 9 edges, so total is 10 edges.
Damn, my code already passes your test case :( Still not sure why it's failing 15 because I can't see the whole input.
did you completed linking the other governments, check this
I can't see test cases :(
Can someone please help me with Div2 C problem? I made disjoint sets of all the capital cities and the nodes connected to them directly or indirectly. Then I calculated the number of nodes who aren't connected to any of the capitals,I did this by calculating the sum of sizes of various disjoint sets and subtracting it from n. Then for every capital city I added (size*(size1))/2 to my final answer.Finally I gave the output as this summ , the no of edges. My submission is http://codeforces.com/contest/745/submission/23076645 . Thanks in advance !
Here's my approach. First of all, if you have make disjoint sets in such way, make each of those disjoint sets a complete subgraph (let's say the set contains x nodes, so the number of edges we can add to make it a complete subgraph with x nodes is x*(x1)/2 — e where e is number of default edges on that sets).
Then after we make each disjoint sets a complete graph, we search every disjoint sets who doesn't have a capital city (special node) as their member and do the following process :  since we want to add as many edges as possible, find the best disjoint set that have capital city as its member (e.g. the disjoint set who has the maximum number of nodes as its member)  add our variable answer with sum[x]*sum[y] (**_sum[x]_** is how many vertex in disjoint set x)
Back to CF after 1.5 years...
Looks like I have not completely forget all about algorithims :)
Now you can probably stop saying you were carried by team members. xD
They don't let you solve :P
Is it just me or rating is not updated yet?
Tough solutions of problem B(Div2) passed the main test , i tested some codes and they(main test passed solutions) gave different answers :( my test case 3 3 ... .X. ..X