Блог пользователя abhatter

Help!!! how to solve USACO 2017 Silver: Bovine Genomics
Автор abhatter, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

»
3 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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
→ Ответить
  • »
    »
    3 года назад, # ^ |
    ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить