AkaneSasu's blog

A Question about the Analysis of 804F — Fake bullions
By AkaneSasu, history, 8 years ago, In English

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 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:27191728

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

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AkaneSasu (previous revision, new revision, compare).

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I had commented below the tutorial and sent a message to the tutorial writer saliii about this,but nobody replies me :(

So,could anyone help me connect the writer? Thanks very much :)

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    We are from same school.

    We have a very very very hard final exam of religion tomorrow.

    We will answer you tomorrow after the exam.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Thanks very much! Wish you all high scores! :)

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In the sample test I think the answer is 4.

    If person number 1 is in top 2 it has at most 3 ways.

    If he is not person number 3 and person number 5 must be that it has one way.

    So the answer is 4.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We don't need to set the scores to Mx, we can just set their scores the same. Thus all people except person 2 can be in top 2.

      For example,if we want person 4 and person 5 to be in top 2,we can set their scores to 4, and the others the lowest, thus they are in top 2,and it's also one way.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        if you set them 4 person number 1 is at least 6. and both of them cannot be in top 2

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          But the statement says that "A gang with power p is in top gangs if there are no more than a - 1 gangs with power strictly more than p."

          And there is only one gang with power p strictly more than 4,so the 3 gangs with power 4 are all in top 2.

          Thus the answer should be 6.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 years ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            they told me problem in persian.

            the problem was that.

            we want to sort the array and choose top A, if there are some one equal we can swap them but no two gangs will have same rank.

            i didn't read the problem in english i'm sorry if it is not the statement.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              So,could you please correct the statement?

              And thanks very much for your patience :)

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                7 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                i will say it to saliii.

                thank you for sharing the point.

                → Reply