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