### yamero's blog

By yamero, history, 6 weeks ago,

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

• 0

 » 6 weeks ago, # | ← Rev. 2 →   0 Check if A(s) + B(s) = C(s) or otherwise
 » 6 weeks ago, # |   0 Due to the short limits, (n = 50) you can try all the possibilities
 » 6 weeks ago, # |   0 No need for powerful data structures, simply brute forcing the string's characters and checking whether it's a valid bracket sequence will suffice due to n being small.
 » 6 weeks ago, # |   0 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.
 » 6 weeks ago, # |   0 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");