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

# | User | Rating |
---|---|---|

1 | tourist | 3565 |

2 | Benq | 3540 |

3 | Petr | 3519 |

4 | maroonrk | 3503 |

5 | jiangly | 3391 |

6 | ecnerwala | 3363 |

7 | Radewoosh | 3349 |

8 | scott_wu | 3313 |

9 | ainta | 3298 |

10 | boboniu | 3289 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 199 |

2 | Errichto | 196 |

3 | rng_58 | 194 |

4 | SecondThread | 186 |

4 | awoo | 186 |

6 | Um_nik | 182 |

7 | vovuh | 178 |

8 | Ashishgup | 176 |

9 | antontrygubO_o | 173 |

9 | -is-this-fft- | 173 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Mar/04/2021 16:17:10 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

The triplet {1, 4, 7} is sufficient

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:

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

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?

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

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

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.

You're welcome! :D