Codeforces Round #374 Div. 2 review

A. One-dimensional Japanese Crossword

Just count consecutive ‘B’ in the sequence.

This is also easy, just count the number for each string length. You even don’t need to process any string manipulation.

C. Journey

I felt it is difficult than problem D. During the contest, I tried to solve it by DFS but I got TLE.

To get answer, we can use DP (dynamic programming) to reduce computational complexity as $$O(mn)$$.

D. Maxim and Array

Basic strategy to get minimum product is as follows,

1. If the product is positive, then we want to reduce it. We can change the sign of number whose absolute value is minimum.

2. If the product is 0, then there exists at least one 0 in the array. We can change this 0 to get total product as negative.

3. If the product is negative, then we want to keep the sign of product as negative and just want to get the total absolute value product as maximum. To do this, we should get minimum absolute value and change this absolute value by $$+x$$.

To get minimum absolute value for each iteration efficiently, we can use priority_queue.