A Question about the analysis of 804F — Fake bullions

Revision en2, by AkaneSasu, 2017-05-22 05:42:16

Hi,I am Akanesasu.

I tried to solve 804F - Fake bullions 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 since we has already know the Mn and Mx of every gang,we can just count the number of gangs whose Mx is equal to or greater than the A-th biggest Mn.

If we assume this number is D,the answer should be CDB,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 is above the A-th biggest Mn , and set the other score to the minimum,we can do it.

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

if we set the score 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.

But the standing code gives 4.

There is my 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)