Codeforces Moving Chips Problem in Python and C++

Published February 24, 2024

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.

Codeforces Moving Chips problem

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:

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

moving_chips.py

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

Disclaimer: Our website is supported by our users. We sometimes earn affiliate links when you click through the affiliate links on our website.

Last Updated: February 24, 2024.     This post was originally written on February 24, 2024.