If you are preparing for USACO or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the Bark to Unlock problem 868A.
Bark to Unlock problem
Please read the Bark to Unlock problem on Codeforces. Make sure you understand the problem first. Write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or a diagrammatical flowchart.
Test cases
You can download these four test cases:
- bark_to_unlock_1.in answer:
YES - bark_to_unlock_2.in answer:
NO - bark_to_unlock_3.in answer:
YES - bark_to_unlock_12.in answer:
YES
Programming Solution Logic
The first line of input is a 2-character password.
The second line is n, the number of 2-character words forming the brute force password by Kashtanka.
The subsequent n lines when joined together, in no particular order (L-R or R-L) forms the string. Let us store the n 2-character words in a list / array called words.
First Test Case
ya
4
ah
oy
to
ha
In the first test case, the password is ya. As in the exampe, looking at the four subsequent 2-letter strings, we can combine oy and ah to create oyah, which contains the password ya. It returns YES.
Second Test Case
hp
2
ht
tp
In the second test case, the password is hp. There are two 2-letter strings. Either combination of ht and tp or tp and ht will not contain the password hp. It returns NO.
Third Test Case
ah
1
ha
Here, the password ah matches with ha.
Fourth Test Case
aa
1
aa
In this test case too, the password aa matches with aa.
At this point, we can tell that it should return a 'YES' if the password is present in the array words. If not, then we can create a nested for loop over the 2-character words with x and y being the outer and inner elements of the for loop. We then compare the password with x + y or y + x. If the password contained in the concatenated string, then return 'YES'. At the end, if there is no match, return 'NO'.
Install Python or C++
If you do not have Python or C++, you should first install it. Codeforces uses Python 3.8 for evaluating your code. If you are using C++, they have versions 17 and 20.
My Python solution
This is my Python solution:
def bark(password, words):
if password in words:
return 'YES'
else:
for x in words:
for y in words:
if password in x + y or password in y + x:
return 'YES'
return 'NO'
password = input().strip()
n = int(input().strip())
words = [input().strip() for _ in range(n)]
print(bark(password, words))
In the Python code, we wrote a function bark(password, words) which accepts the password and list. It returns the answer to the main function. We use the in operator to find password in x + y or y + x.
In another blog post, I noted that creating functions and outsourcing logic in functions makes your program faster than using global variables and putting everything in the main function in Python.
Running the Python code
Run the Python code from your Terminal. I am using macOS, but you can use any Linux-based OS as well.
$ cat bark_to_unlock_1.in | python bark_to_unlock.py
YES
$ cat bark_to_unlock_2.in | python bark_to_unlock.py
NO
$ cat bark_to_unlock_3.in | python bark_to_unlock.py
YES
$ cat bark_to_unlock_12.in | python bark_to_unlock.py
YES
My C++ solution
This is my C++ solution:
#include <iostream>
using namespace std;
bool is_in(string words[], string password) {
for (int i=0; i < words->size(); i++) {
if (password == words[i]) {
return true;
}
}
return false;
}
int main() {
string password;
cin >> password;
int n;
cin >> n;
string words[n];
for (int i=0; i < n; i++) {
cin >> words[i];
}
if (is_in(words, password)) {
cout << "YES";
exit(0);
} else {
for (int i=0; i < n; i++) {
for (int j=0; j < n; j++) {
if ((words[i] + words[j]).find(password) != std::string::npos) {
cout << "YES";
exit(0);
}
}
}
}
cout << "NO";
}
In the C++ code, we wrote a function is_in(words, password) which accepts the words array and password and returns whether the password is present in the array. Most of the logic in the main function. We use a nested for loop and for every element, we combine both elements and search for password in the concatenated string. If found, print 'YES' and exit. At the end, if nothing is found and we are at the last line, it means it was not found, so print 'NO'.
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ bark_to_unlock.cpp
Now, run all the three test cases against a.out.
$ cat bark_to_unlock_1.in | ./a.out
YES
$ cat bark_to_unlock_2.in | ./a.out
NO
$ cat bark_to_unlock_3.in | ./a.out
YES
$ cat bark_to_unlock_12.in | ./a.out
YES
Submit your code
Submit your Python code and C++ code to Codeforces. When your code successfully passes all test cases, you will get a green "Accepted" message with the time taken.
Which is faster?
In the Codeforces submission page, these were the results:
Python 3 -- Time taken: 46 ms GNU C++20 (64) -- Time taken: 15 ms
What about software design, conventions and standards?
This is competitive programming. The goal is to complete the program with minimum effort and maximum efficiency. Using single character variables and ugly formatted code are okay, as long as the program runs and runs well within the scope. In the C++ code, we also shamelessly exited the program. That is fine, as long as your program works and you are able to submit it.
Later in life, when you start working in a professional environment, please beautify your ugly code, follow conventions, add comments and make your code readable. Readability and maintainability is key if you want to be a successful software engineer.
Conclusion
If there is anything you would like me to add to this article, feel free to comment below or contact me. Thanks.
Related Posts
If you have any questions, please contact me at arulbOsutkNiqlzziyties@gNqmaizl.bkcom. You can also post questions in our Facebook group. Thank you.