abhatter's blog

Help!!! how to solve USACO 2017 Silver: Bovine Genomics
By abhatter, history, 4 years ago, In English

Hello, Can you please explain how the solution is 22 to the given sample example in the problem description. Click to view problem description

Thanks in advance

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Hi! For each triplet of columns it is sufficient to explain spottiness if its patterns only appears on spotty cows or if its patterns only appears on plain cows.

Positions:    1     4     7 ... 

Spotty Cow 1: A ... A ... T ... 
Spotty Cow 2: G ... A ... T ...
Spotty Cow 3: G ... G ... T ...

Plain Cow 1:  A ... C ... T ...
Plain Cow 2:  A ... G ... T ...
Plain Cow 3:  A ... G ... T ...

The triplet {1, 4, 7} is sufficient

Positions:    1     2     7 ... 

Spotty Cow 1: A ... A ... T ... 
Spotty Cow 2: G ... A ... T ...
Spotty Cow 3: G ... G ... T ...

Plain Cow 1:  A ... C ... T ...
Plain Cow 2:  A ... A ... T ...
Plain Cow 3:  A ... G ... T ...

The triplet {1, 2, 7} isn't sufficient because the pattern AAT appears on spotty cows and plain cows

The solution to the given sample example are the triplets:

1 2 3
1 2 4
1 2 5
1 2 6
1 2 7
1 2 8
2 3 4
2 3 5
2 3 6
2 3 7
2 3 8
2 4 5
2 4 6
2 4 7
2 4 8
2 5 6
2 5 7
2 5 8
2 6 7
2 6 8
2 7 8
4 5 8
→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I am having hard time understanding as to how to generate patterns through triplets for each type of cows. This is causing big trouble from my side.

    From the below example

    3 8
AATCCCAT
GATTGCAA
GGTCGCAA
ACTCCCAG
ACTCGCAT
ACTTCCAT

    For spotty cows, the pattern formed by triplet 1,2,3 which is AAT can also be formed by spotless cows through triplet 1,7,3.

    Please correct me if I am wrong?

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

      You should consider triplets independently. The AAT pattern does not appear in the triplet {1,2,3} of any plain cow

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

        thanks alot. I think I am getting the point now. I will do a bit of analysis on my side and keep you posted.

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

          I was able to come up with a solution but the time complexity was not as good as O(N*M^3) and I had issues with my solution acceptance. Now, finally I was able to finally I was able to come up with O(N*M^3) solution and my solution now is accepted.

          Thanks for your quick response.

          → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

who can give me a hint, because I don't have any idea

→ Reply