Easy af, try again
Try to figure some constructive strategy and prove it to be optimal
Its greedy. Go back to Hint #2
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.
Criminal can always come into liar without bringing contradiction "..)..(.." given it doesn't exceed N/2 ofc.
Read more… (102 words)