vegeta996's blog

By vegeta996, history, 5 years ago, In English

Hi Everyone, I am not able to understand the editorial for the problem Serval and Parenthesis Sequence any help towards solving the problem will be appreciated.

My submission 52740091 is failing on test case 6. And I am not able to figure out the case for it.

  • Vote: I like it
  • +1
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
Rev. 3   Vote: I like it +4 Vote: I do not like it

-at the end you need to have n/2 of '(' and n/2 of ')'.

-what is the best way to arrange the n/2 of ')' so that the string is still strict prefix as long as it's less than n ? by putting them as far as possible so that the(number of '(' is greater as possible so that we won't allow any type to correct sequence before the end of the string)

-the best way to put the ')' is to go from n-1 .... 0 and in each step you check if s[i] = '?' and the number of ')' is less than n/2 if it's you put the ')' otherwise in every '?' you put '('.

-after you finish the previous operation you go from 0 .... n-1 and count the number of '(' and ')' on every step and check that '(' is always greater than the number of ')' and i < n-1 otherwise you print :(.

-after you finish the loop you check that the number of '(' and ')' is equal if so you print the string otherwise you print :(.

here is my submission : https://codeforces.com/contest/1153/submission/52723028 , happy solving!.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Try this testcase (??))??(?)))