A Question about the analysis of 804F — Fake bullions
Difference between en3 and en4, changed 0 character(s)
Hi,I am Akanesasu.↵

I tried to solve [problem:804F] several days ago,and i have a question about the analysis and the standing solutions.↵

The Link is above,and you can read the problem by yourself.↵

I have no doubt about the first part of the analysis,about how to calculate the $Mn$ and $Mx$.↵

My question is that since we has already know the $Mn$ and $Mx$ of every gang,assume the A-th biggest $Mn$ is $E$,we can just count the number of gangs whose $Mx$ is equal to or greater than $E$.↵

If we assume this number is $D$,the answer should be $C(D,B)$,where $C$ is the number of combinations.↵

Because we can choose any $B$ gangs from these $D$ gangs,and there is always a way to set the score to satisfy the situation.↵

You may think thats not possible,but if we set the score of the gangs which we choose to the lowest score it can reach and at least $E$, and set the other score to the minimum,we can do it.↵

Prove:↵

The gangs whose $Mn$ is greater than $E$ has already considered before,the number of them is no more than $A-1$. And the other gang's socre is just equal to or less than $E$,so the gangs we choose are all among the top gangs.↵

Look at this case:↵

~~~~~↵
5 2 2↵
01011↵
00011↵
11000↵
00100↵
00110↵
10 1110100101↵
1 1↵
7 1001000↵
4 1001↵
10 0110001100↵
~~~~~↵

As the whole graph is an SCC ,the mn and mx are:↵

~~~~~↵
mn[1]=6,mx[1]=10↵
mn[2]=1,mx[2]=1↵
mn[3]=2,mx[3]=7↵
mn[4]=2,mx[4]=4↵
mn[5]=4,mx[5]=10↵
~~~~~↵

We find that $D$ is 4.↵

And if we set the scores as follow:↵

~~~~~↵
score[1]=6↵
score[2]=1↵
score[3]=4↵
score[4]=4↵
score[5]=4↵
~~~~~↵

then we can choose any 2 gangs from gang 1,3,4,5, so the answer should be 6,which is C(4,2).↵

But the standing code gives 4.↵

There is my submission:[submission:27191728]↵

I wonder if the data and the analysis is incorrectly.Thanks!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English AkaneSasu 2017-05-25 09:51:12 2
en4 English AkaneSasu 2017-05-22 05:51:49 0 (published)
en3 English AkaneSasu 2017-05-22 05:50:18 1493
en2 English AkaneSasu 2017-05-22 05:42:16 86
en1 English AkaneSasu 2017-05-22 05:40:27 1564 Initial revision (saved to drafts)