Блог пользователя Lewin

Автор Lewin, история, 9 лет назад, По-английски

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.

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: 500-1000-1500-2250-2750

Div1: 500-1250-1750-2250-2500

EDIT 3: While you wait for system testing, here is a quick editorial: http://mirror.codeforces.com/blog/entry/49126

EDIT 4: Congratulations to the winners!

Div1:

  1. tourist
  2. Petr
  3. PavelKunyavskiy
  4. YuukaKazami
  5. W4yneb0t

Div2:

  1. Akulen
  2. Rfox
  3. tpablo
  4. theodor.moroianu
  5. YouAndI
  • Проголосовать: нравится
  • +477
  • Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

Interesting problem setters. Now, i'm more eager to participate :)

»
9 лет назад, скрыть # |
Rev. 8  
Проголосовать: нравится -50 Проголосовать: не нравится

Deleted...

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -62 Проголосовать: не нравится

I am sure that this round by Lewin will contain interesting problems(not as previous two rounds).

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +40 Проголосовать: не нравится

Clashes with COCI #4. It would be awesome to move it to 20:xx MSK (a hour later).

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +434 Проголосовать: не нравится

** ** *****?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -124 Проголосовать: не нравится

hope not to see comments like "is it rated?" or "usual time"

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -36 Проголосовать: не нравится

Found it funny:"unusual usual time"..:)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

nice tags

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

Again interactive! every time I see and I think- well! I can solve it :D but then- I say — Sorry me! :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +36 Проголосовать: не нравится

After seeing the tags and round description, I'm wondering, if we will have to interact with cows...

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Wondering how to hack the interactive problem?

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -39 Проголосовать: не нравится

-

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +56 Проголосовать: не нравится

It seems that codeforces is cleaning up its inventory of problems before Christmas...

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -49 Проголосовать: не нравится

Today Petr is participating :) ,any guesses in which language(Java/C++/both) he will code in todays contest ?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -13 Проголосовать: не нравится

Hope the interactive problem will be interesting.:)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +37 Проголосовать: не нравится
»
9 лет назад, скрыть # |
 
Проголосовать: нравится +23 Проголосовать: не нравится

Four contests in a row) Four contests in 3 days) Real happiness...

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится

Good luck! I hope more Experts will be Candidate Master!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

I have registered for the div-2 contest but I am not able to see the problems. What should I do.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Hope to provide a grader for the interactive problem :/

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Bad timing for manchester united fan.

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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?

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +42 Проголосовать: не нравится

Deep♂Dark♂Fantasy (EvenImage, jcvb, YuukaKazami) in this round they will decide who will be the captain

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

I hate registering using the lower bottom, hope in this round I can reach Div1 and use the upper one

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Good luck everyone! Lewin always writes interesting problems.

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

I hope there will be lots of math questions!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

Explain B problem in Div2

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

DIV2 B problem statement :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

what is the explanation DIV 2 B means?

How can by one movement to right ..... XX... ..... ..... .....

be formed ??

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +21 Проголосовать: не нравится

Div2 Problem B ..So unclear problem statement. It does not even make sense to me :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I just love Ruski English.

GGWP ;)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -6 Проголосовать: не нравится

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?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

In DIV 2 B , is it 'x' or 'X' ?

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится -8 Проголосовать: не нравится

in problem B DIV 2 why this test outputs no? 3 3

.XX

XX.

XX.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can I delete my last accepted solution? I only need another one to be verified...

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

the problem statement on B is extremely weird !

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Hacking, hacking everywhere!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone have a hack case for Div. 2 B?

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Petr may reclaim his second rank today.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

How to solve Div2D and Div2E?

  • »
    »
    9 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve the problem about the table game?

»
9 лет назад, скрыть # |
Rev. 5  
Проголосовать: нравится +3 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Statement for DIV2 B could have been better.

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Please explain your solution.

    • »
      »
      »
      9 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      9 лет назад, скрыть # ^ |
      Rev. 2  
      Проголосовать: нравится +3 Проголосовать: не нравится

      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]

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +4 Проголосовать: не нравится

    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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

My first ever hack!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +32 Проголосовать: не нравится

Pretests passed in Div1-A by reading edges first then capitals — such strong pretests :( — http://mirror.codeforces.com/contest/744/submission/23053839

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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 4-connected 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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

I hacked 3 C solutions where their logic was as follows:
ans=n-k+1;
ans=(ans*(ans-1))/2;
ans=ans-m;
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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Div2 B is the worst problem I have ever seen in CF

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

DIV2 E test3?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

That moment when you discover your bug 30 seconds after the contest ends T_T.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.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 :|

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +16 Проголосовать: не нравится

I found 2 submissions with the same implemention http://mirror.codeforces.com/contest/745/submission/23067444 http://mirror.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!!)

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +10 Проголосовать: не нравится

I have taken almost 20 minutes to understand the problem B in div2 :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

I should practice more hard

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

So what's the right solution for B? Check whether it's a rectangle? Or what? Even C is easier than this.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

is it even necessary to have govt nodes Number in Div 2 C ? if i iterate over all nodes to do the dfs anyway ?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Both problem statement & pretest cases of problem B were really very weak.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +25 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

:)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Div2/B is just horrible, nice Div2/C BTW I got pretest passed in the last minute.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +50 Проголосовать: не нравится

Why Codeforces nowdays testing user's ability to understand problem statement???

»
9 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +9 Проголосовать: не нравится

Problem statements were really confusing -_-

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

Problems were fine, statements were trash

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -15 Проголосовать: не нравится

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.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +19 Проголосовать: не нравится

I really liked Div1 B!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Problem B not passed — nooooooo! So it's actually wrong to output yes when the piece is a rectangle.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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).

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -42 Проголосовать: не нравится

Is it rated ? :p

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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 ?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +24 Проголосовать: не нравится

 welp, this was unexpected

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Waiting for rating

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

The statement for problem B (division 2) was very poor!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

whatever....what about ratings???

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

system pending wasnt faster before ? :-"

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +18 Проголосовать: не нравится

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. ;)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When can i up-solve problems? cant submit any solution now! there is no option ! if i click on 'submit code' tab, its shows 'contest is over'!

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +156 Проголосовать: не нравится

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +4 Проголосовать: не нравится

Div.1A, test 15. Are you sure that given graph is stable?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Goodbye Expert...

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Where is the new rating?

»
9 лет назад, скрыть # |
Rev. 24  
Проголосовать: нравится +8 Проголосовать: не нравится

C approach:

let k be the number of governments

Make k sub-graphs such that each of them contains one government node (k strongly connected components), so vi nodes with government.

Note that there will be, let say p nodes in anarchy (no government) with pe edges between them.

We will attach those nodes to some of the k sub-graphs and generate the maximum number of possible edges. (No node can be attached to two different sub-graphs)

Let g1 be the edges generated by

  • Two nodes with government

Let g2 be the edges generated by

  • Two nodes without government

Let g3 be the edges generated by

  • Nodes with government
  • Nodes without government

We agree g1 has a fixed amount, thus no decision with the anarchy nodes will influence its value.

Then we need to see that g2 ≤ p * (p - 1) / 2 - pe. We can't have more edges between p nodes than the possible pairs of them. Any solution with g2 = p * (p - 1) / 2 - pe has an optimal value of g2. Any solution that set the p vertex in the same group has an optimal value of g2 (1)

Note that adding one anarchy node to a group with government generate vi edges of type g3. (denote vi the original amount of nodes per group).

If j is the sub-graph with more nodes then vi ≤ vj with any sub-graph i

where ci is the amount of anarchy nodes that go to the sub-graph i

As ci * vi ≤ ci * vj

this means adding all anarchy nodes to the group j implies an optimal g3 value, cause equality is obtained. But if we do so then all anarchy nodes will be in the same group, because of (1) g2 is optimal As g2 is optimal, g3 is optimal, and g1 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 ei is the amount of edges that already exist per group

Total complexity: O(n)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +6 Проголосовать: не нравится

Start the upsolving, please

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

When can we submit for problems??

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Well, just 1 far from expert :( Look at my graph

»
9 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +1 Проголосовать: не нравится

I think something is wrong here one code with 2 different verdict (hack, accept) 23067626 , 23072618

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +20 Проголосовать: не нравится

I think there is a problem on codeforces , i can't do anything on the site
look here

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

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 ?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Anyone know what testcase 15 on Div1A/Div2C contains? I'm failing on it.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I can't see test cases :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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*(size-1))/2 to my final answer.Finally I gave the output as this sum-m , the no of edges. My submission is http://mirror.codeforces.com/contest/745/submission/23076645 . Thanks in advance !

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    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*(x-1)/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)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +60 Проголосовать: не нравится

Back to CF after 1.5 years...

Looks like I have not completely forget all about algorithims :)

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Очень интересно тут считается рейтинг. После первого участия в олимпиаде я стала специалистом, хотя решила всео одну задачу. Потом было пару раундов, на которых я не успела решить ни одной задачи, рейтинг не снизился. Было пару раундов, когда я отправляла неправильное решение, так и не решив до конца — рейтинг упал. Вчера мне все таки удалось решить одну задачу, но рейтинг еще понизили. То есть, лучше бы вообще ни одной не решила, что б хоть не понизили? Обидно. Зачем так новеньких обламывать?

  • »
    »
    9 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Рейтинг меняется в зависимости от твоего места. Потом было пару раундов, на которых я не успела решить ни одной задачи, рейтинг не снизился. Если ты ничего не отправляешь, система считает, что ты не участвовала в контесте (что логично), и твой рейтинг не меняется, потому что в принципе не на что опереться при его пересчете — места-то нет. Было пару раундов, когда я отправляла неправильное решение, так и не решив до конца — рейтинг упал. Как только ты делаешь отправку, твое решение проверяется, выдается какой-то вердикт, и тебе присуждается место в контесте в зависимости от твоих баллов. Раз ты не решила, то место у тебя было судя по всему низкое, и у тебя забрали рейтинг.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Is it just me or rating is not updated yet?