Easy af, try again

Try to figure some constructive strategy and prove it to be optimal

Its greedy. Go back to Hint #2

Solution

Let X be number of '(' & Y be number of ')'. If it isn't impossible, at end X=Y (=N/2). For each '?' from left replace it by '(' till X becomes N/2. After that replace all remaining '?' by ')'. Check constructed string if at any point X<Y then it is impossible else output constructed string. Think about proof.

Proof Hint

Criminal can always come into liar without bringing contradiction "..)..(.." given it doesn't exceed N/2 ofc.

Read more… (102 words)