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 Fafa and the Gates problem 935B.
Fafa and the Gates problem
Please read the Fafa and the Gates 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 three test cases:
- fafa_and_the_gates_1.in answer:
0 - fafa_and_the_gates_2.in answer:
1 - fafa_and_the_gates_3.in answer:
2
Programming Solution Logic
The first line of input is n, the number of moves.
The second line is S, the list of moves as a string, one character for each move. In our code, we will call it moves, to make the variable name more intuitive.
From the problem, we see that if Fafa moves from one kingdom to another, only then does he pay 1 silver coin. Let us keep track of the number of silver coins in variable coins.
We first initialize coins to 0.
We then have to keep track of the kingdom Fafa is in currently and if his previous move made him move across kingdoms. For that, we will write a function which_kingdom(x, y) which accepts Fafa's coordinates and returns 1 if he is in kingdom 1, which is below the slope, and 2 if he is in kingdom 2, which is above the slope. The function also returns 0, if he is ON the slope.
In the main function, we keep track of the kingdom he was last in. This is using an int variable last_kingdom. This can take values 1 or 2. We first initialize last_kingdom to 0. Then, whichever kingdom he goes to first (1 or 2), we assign it to last_kingdom.
So, these are the possible scenarios:
- Kingdom 1 to 0 to Kingdom 1: No payment since he stayed in kingdom 1.
- Kingdom 1 to 0 to Kingdom 2: 1 coin payment since he moved across kingdoms.
- Kingdom 2 to 0 to Kingdom 2: No payment since he stayed in kingdom 2.
- Kingdom 2 to 0 to Kingdom 1: 1 coin payment since he moved across kingdoms.
- Kingdom 2 to 0 to Kingdom 2 to 0 to Kingdom 2: No payment since he stayed in kingdom 2.
Before starting, look at the test cases. A few moves are uppercase and a few are lowercase. To make it foolproof, let us convert the variables moves to uppercase and work with it.
First Test Case
1
U
This is straightforward. Fafa moved to kingdom 2, as returned by which_kingdom(). But since last_kingdom was set to 0 and he did not move from a non-zero kingdom, the number of coins he pays is 0.
Second Test Case
6
RURUUR
In the second test case, the value of last_kingdom stays at kingdom 1 for RURU. Then, while encountering the fifth move U, which_kingdom returns 2, while last_kingdom is 1. Since this was a transition between non-zero kingdoms, the number of coins increases from 0 to 1. The next move R keeps Fafa in kingdom 1. The number of coins he pays is 1.
Third Test Case
7
URRRUUU
In the third test case, last_kingdom is 2 for UR. The third move R will return which_kingdom to 1. So, that is one coin payment. A couple of moves later, RUUU, which_kingdom will return 2. That is another coin payment, bringing the total coins to 2. The number of coins he pays is 2.
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:
# Return 1 if first kingdom, under the / or
# 2 if second kingdom, above the /
def which_kingdom(x, y):
if x > y:
return 1
elif y > x:
return 2
return 0
n = int(input())
moves = list(input().upper())
x, y = next_x, next_y = 0, 0
coins = 0
last_kingdom = 0
for move in moves:
if move == 'U':
y += 1
elif move == 'R':
x += 1
curr = which_kingdom(x,y)
# for the first run
if last_kingdom == 0:
last_kingdom = curr
if curr != 0 and last_kingdom != curr:
last_kingdom = curr
coins += 1
print(coins)
In the Python code, we wrote a function which_kingdom(x, y) which returns the kingdom Fafa is in currently. The variable last_kingdom keeps track of which kingdom he was in; the valid values are 1 and 2. The border (x=y) does not count.
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 fafa_and_the_gates_1.in | python fafa_and_the_gates.py
0
$ cat fafa_and_the_gates_2.in | python fafa_and_the_gates.py
1
$ cat fafa_and_the_gates_3.in | python fafa_and_the_gates.py
2
My C++ solution
This is my C++ solution:
#include <iostream>
using namespace std;
/*
Return 1 if first kingdom, under the / or
2 if second kingdom, above the /
*/
int which_kingdom(int x, int y) {
if (x > y) {
return 1;
} else if (y > x) {
return 2;
}
return 0;
}
int main() {
int n;
string moves;
int x, y, next_x, next_y;
int coins, last_kingdom;
x = y = next_x = next_y = coins = last_kingdom = 0;
cin >> n;
cin >> moves;
for (int i=0; i < n; i++) {
char move = toupper(moves[i]);
if (move == 'U') {
y += 1;
} else if (move == 'R') {
x += 1;
}
int curr = which_kingdom(x, y);
// First move
if (last_kingdom == 0) {
last_kingdom = curr;
}
// Next positive move from kingdom to kingdom
if (curr != 0 && last_kingdom != curr) {
last_kingdom = curr;
coins++;
}
}
cout << coins;
}
In the C++ code, we used the sme logic. We wrote a function which_kingdom(x, y) which returns the kingdom Fafa is in currently. The variable last_kingdom keeps track of which kingdom he was in; the valid values are 1 and 2. The border (x=y) does not count.
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ fafa_and_the_gates.cpp
Now, run all the three test cases against a.out.
$ cat fafa_and_the_gates_1.in | ./a.out
0
$ cat fafa_and_the_gates_2.in | ./a.out
1
$ cat fafa_and_the_gates_3.in | ./a.out
2
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: 62 ms GNU C++20 (64) -- Time taken: 31 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.