Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

Блог пользователя yamero

Автор yamero, история, 3 года назад, По-английски

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
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 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.

»
3 года назад, # |
  Проголосовать: нравится 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");