When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

yamero's blog

By yamero, history, 3 years ago, In English

Hello, im relatively new to cpp and codeforces. Ive been working the problem 1494A for 2 days now, but I am still failing at some testcases. I really dont want to consult the solutions. Could anyone just provide me a hint as to what im doing wrong. Any advices in general are also appreciated....

Thanks a lot. Here is my 119538142 for the problem no: 1494A - ABC String

  • Vote: I like it
  • 0
  • Vote: I do not like it

| Write comment?
»
3 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Check if A(s) + B(s) = C(s) or otherwise

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

There is an issue with the way you check if the sequence is valid. For example it says "())))(((()" is valid. Other than that, everything else is fine.

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

How to check correct bracket sequences (here is pseudocode):

bal = 0 
for i in s: 
   if i == '(': bal++ 
   if i == ')': bal-- 
   if bal < 0: // incorrect bracket sequences
if bal > 0: // incorrect bracket sequences

So, check all variants. But 3^50 is very big number. This optimization will help: When you paste bracket ('(' or ')') check, that bal >= 0 (If bal < 0 — break). And total bal == 0 (If bal > 0 — break). Example:

bool solve(char A, char B, char C) {
  string b = a;
  for (char& i : b) {
    if (i == 'A') i = A;
    if (i == 'B') i = B;
    if (i == 'C') i = C;
  }
  int bal = 0;
  for (char i : b) {
    if (i == '(') bal++;
    else bal--;
    if (bal < 0) return false;
  }
  if (bal > 0) return false;
  else return true;
}
bool ok = false;
ok |= (solve('(', '(', '(')); // 000
ok |= (solve('(', '(', ')')); // 001
ok |= (solve('(', ')', '(')); // 010
ok |= (solve('(', ')', ')')); // 011
ok |= (solve(')', '(', '(')); // 100
ok |= (solve(')', '(', ')')); // 101
ok |= (solve(')', ')', '(')); // 110
ok |= (solve(')', ')', ')')); // 111
cout << (ok ? "YES\n" : "NO\n");