If you are preparing for USACO, ACSL or any other competitive programming, Codeforces is a good place to practice your programing. This article contains my Python and C++ solutions for the Moving Chips problem 1923A, a part of Educational Codeforces Round 162 (Rated for Div. 2). This was posted on February 23, 2024.
Moving Chips problem
Please read the Moving Chips problem on Codeforces first. Make sure you understand the problem fully. Write the algorithm on paper before coding anything. For your algorithm, you can write either pseudocode or draw a flowchart.
Test cases
You can download this test case input and the expected output:
- moving_chips_1.in input file
- moving_chips_1.out output file
Programming Solution Logic
The first line of input is t, the number of test cases.
The first line of each test case contains n, the number of cells.
The second line of each test case contains string ribbon, which is made up of n cells, each of which is separated by a single space. Each cell may have 0 or 1. If there is a 1, it means there is a chip present.
Our solution is to make the rightmost 1s flip with the 0 immediately on the left until we are left with one whole consecutive block of 1s.
We will look at a few of the test cases in the the input file moving_chips_1.in and compare the answers to the ones in the output file moving_chips_1.out .
First Test Case
The first ribbon is:
0 1 1 1 0 1 1 0
To create a single block of 1s in the least number of operations, we switch the rightmost 1 with the first 0 to its left.
0 1 1 1 0 1 1 0
0 1 1 1 1 1 0 0
It took one operation to get a single contiguous block of 1s. The output is 1.
0 1 1 1 1 1 0 0
Second Test Case
The second ribbon is:
0 1 0 0 0 0
This test case already has only one 1, so that is the block we need. There is no operation needed to be performed. The output is 0.
Third Test Case
The third ribbon is:
1 1 1 1 1 1
This test case already has one contiguous block of 1s. There is no operation needed to be performed. The output is 0.
Fourth Test Case
The fourth ribbon is:
1 0 1 0 1
Since we have two 0s between the first and last 1s, we have to use multiple operations to get a contiguous block of 1s.
We switch the rightmost 1 with the 0 to its left.
1 0 1 0 1
1 0 1 1 0
We still do not have a singular block of 1s, so we continue the switching. We move the rightmost 1 with the 0 in the second place.
1 1 1 0 0
It took two operations to get contiguous 1s. The output is 2.
1 1 1 0 0
Fifth Test Case
The fifth ribbon is:
0 1 1 0 0 0 1 1 0
Step 0) 0 1 1 0 0 0 1 1 0
Step 1) 0 1 1 0 0 1 1 0 0
Step 2) 0 1 1 0 1 1 0 0 0
Step 3) 0 1 1 1 1 0 0 0 0
It took three operations to get contiguous 1s. The output is 3.
0 1 1 1 1 0 0 0 0
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
# https://codeforces.com/contest/1923/problem/A
# Returns indices of largest block starting and ending with 1s
def get_largest_block(s):
l = s.index('1')
r = len(s) - s[::-1].index('1') - 1
return l, r
# Returns number of operations to get single largest block with all 1s
def single_block(s):
ops = 0
l, r = get_largest_block(s)
block = s[l:r]
while '0' in block:
while l < r:
if s[l] == '0' and s[l+1] == '1':
s[l], s[l+1] = '1', '0'
l += 1
ops += 1
l, r = get_largest_block(s)
block = s[l:r]
return ops
# Main function
t = int(input())
for _ in range(t):
n = int(input())
ribbon = input().split(' ')
print(single_block(ribbon))
In this Python code, we wrote two functions.
1) get_largest_block(s) accepts the ribbon string s as input and returns the indices of the first and last occurrences of 1.
2) single_block(s) accepts ribbon string s as input and returns the least number of operations needed to create the single block of 1s. This function makes a call to function get_largest_block(s) and sends the ribbon s as parameter. This function returns the indices of the substring of cells from the first instance of 1 to the last instance of 1. We then swap the 0 and 1 in that order. We repeatedly call the get_largest_block(s) while sending the ribbon s as parameter. In the end, we get the single contiguous cells with 1. Each iteration adds to the counter ops and is returned by this function. That is our answer.
We call single_block(s) from the main function and print the returned value.
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.
Here, I am running the program, which reads the input file with 5 test cases. Later, I also viewed the contents of the output file to compare the results.
$ cat moving_chips_1.in | python moving_chips.py
1
0
0
2
3
$ cat moving_chips_1.out
1
0
0
2
3
My C++ solution
This is my C++ solution:
#include <iostream>
#include <tuple>
using namespace std;
// Returns indices of largest block starting and ending with 1s
tuple <int, int> get_largest_block(string s[], int n) {
int l = -1, r = -1;
for (int i=0; i < n; i++) {
if (s[i] == "1") {
if (l == -1) l = i;
r = i;
}
}
return make_tuple(l, r);
}
// Returns true if '0' is in the block
bool is_0_in(string block[], int block_size) {
for (int i=0; i < block_size; i++) {
if (block[i] == "0") {
return true;
}
}
return false;
}
// Returns number of operations to get single largest block with all 1s
int single_block(string s[], int n) {
int ops = 0;
int l, r;
tie(l, r) = get_largest_block(s, n);
int block_size = r - l + 1;
string block[block_size];
for (int i=0; i < block_size; i++) {
block[i] = s[l+i];
}
while (is_0_in(block, block_size)) {
while (l < r) {
if (s[l] == "0" and s[l+1] == "1") {
s[l] = "1";
s[l+1] = "0";
}
l++;
}
ops++;
tie(l, r) = get_largest_block(s, n);
block_size = r - l + 1;
block[block_size] = {};
for (int i=0; i < block_size; i++) {
block[i] = s[l+i];
}
}
return ops;
}
// Main function
int main() {
int t;
cin >> t;
for (int i=0; i < t; i++) {
int n;
cin >> n;
string ribbon[n];
for (int j=0; j < n; j++) {
cin >> ribbon[j];
}
cout << single_block(ribbon, n) << endl;
}
}
In the C++ code, we used the same logic. We wrote a function get_largest_block(s) accepts the ribbon string s as input and returns the indices of the first and last occurrences of 1.
A second function single_block(s) accepts ribbon string s as input and returns the least number of operations needed to create the single block of 1s. This function makes a call to function get_largest_block(s) and sends the ribbon s as parameter. This function returns the indices of the substring of cells from the first instance of 1 to the last instance of 1. We then swap the 0 and 1 in that order. We repeatedly call the get_largest_block(s) while sending the ribbon s as parameter. In the end, we get the single contiguous cells with 1. Each iteration adds to the counter ops and is returned by this function. That is our answer.
The function single_block(s) is called from the main function and we print the answer.
We can compare the printed output with the correct output in the .out file.
We use the tuple library to return a typle of int, int from the get_largest_block() function, so we include it at the top.
#include <tuple>
Running the C++ code
Compile the C++ code from your Terminal. This command creates a.out.
$ g++ moving_chips.cpp
Now, run the test cases against a.out.
$ cat moving_chips_1.in | ./a.out
1
0
0
2
3
$ cat moving_chips_1.out
1
0
0
2
3
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: 109 ms GNU C++20 (64) -- Time taken: 46 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.