both problems here: https://leetcode.com/discuss/interview-question/5497148/snowflake-intern-oa-questions

Can anyone please give hints for the 2nd problem, I have no clue how to approach it. Thank you

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

1 | tourist | 3947 |

2 | ecnerwala | 3654 |

3 | jiangly | 3627 |

4 | jqdai0815 | 3620 |

5 | orzdevinwang | 3612 |

6 | Benq | 3586 |

7 | Radewoosh | 3582 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3474 |

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

1 | awoo | 163 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 154 |

5 | maroonrk | 152 |

6 | -is-this-fft- | 148 |

6 | SecondThread | 148 |

8 | Petr | 147 |

9 | nor | 145 |

10 | cry | 144 |

both problems here: https://leetcode.com/discuss/interview-question/5497148/snowflake-intern-oa-questions

Can anyone please give hints for the 2nd problem, I have no clue how to approach it. Thank you

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2024 01:52:37 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

Denote '0' for the zero-adjacent processor, '1' for the one-adjacent processor, and '2' for the two-adjacent processor. Then, each valid sequence of deployments results in a unique string of '0', '1', 'and '2'. We'll call such a string valid.

In a valid string, ignoring '1's, we see that '0' and '2' must "alternate", starting and ending with '0' (e.g. if you remove '1's in a valid string, then the sequence must look something like "020202020"). Furthermore, it is easy to see that any string that satisfies this corresponds to a valid sequence of deployments.

Then, setting up a DP recurrence should be relatively straightforward with this observation.

Think about applying all the possibilities of the types of adjacent and how for applying one type of operation on i, it affects on i+1.

It can be solved using dp

For example If want no adjacent on i, then it is bound for i+1 to be either one adjacent or two adjacent.

Or if I want i to be two adjacent then it bound for i+1 to be no adjacent or one adjacent

Thank you