qhung312's blog

By qhung312, history, 4 years ago, In English

Given a string s and t and a list of transformation arr, determine if after we can turn s into t after applying exactly n transformations from arr (choosing which operation to perform on each turn the string is up to you, as long as it's a valid transformation)

Example: With s = "XO" and t = "XXXO", n = 4 and list of available transformations:

"XX" -> "XO"
"XO" -> "OO"
"O" -> "XX"

Explanation: We can apply the second operation to turn s into "OO". Next apply the third operation to the first character and we'll get "XXO". Apply the third operation to the last character and we get XXXX. Finally, apply the first operation on the last two characters and we get the string s = "XXXO", which is equal to t.

Contraints:

  • The length of s will be no more than 40 characters, and so is t.
  • Length of arr (the list of transformations) is no more than 10.
  • Each string in arr is at maximum 10 characters in length
  • n <= 15
  • Time limit: 1s

Full text and comments »

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

By qhung312, history, 4 years ago, In English

1345C - Hilbert's Hotel requires you to check if all (i + arr[i]) % n is distinct, so I did:

for (int i = 0; i < n; i++) {
  ll x;
  cin >> x;
  arr[i] = (i + x) % n;
  s.insert(arr[i]);
}
cout << ((s.size() == n) ? "YES" : "NO") << '\n';

This got WA on test 2, whereas if I change it to:

arr[i] = ((i + x) % n + n) % n;

This got AC. But aren't (i + x) % n and ((i + x) % n + n) % n the same thing?

Full text and comments »

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