yamero's blog

By yamero, history, 6 weeks 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

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Due to the short limits, (n = 50) you can try all the possibilities

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  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.

»
6 weeks 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");