How do I solve this problem for all constraints

Question

1.00/5 (1 vote)

See more:

Farmer John has N cows in a line (1≤N≤3⋅10^5). Unfortunately, there is a sickness spreading throughout.
Initially, some cows start off infected. Every night, an infected cow spreads the sickness to the cows on their left and right (if they exist). Once a cow is infected, she stays infected.
After some amount of nights, Farmer John realizes that the issue has gotten out of control, so he tests his cows to determine who has the sickness. Find the minimum number of cows that could have started with the sickness.
INPUT:
The first line contains N, the number of cows that Farmer John has.
The next line contains an N character bitstring of only 1s and 0s where a 1 represents an infected cow and a 0 represents an uninfected cow after some number of nights.
OUTPUT:
Output a single integer: the minimum number of cows that could have started with the sickness.
SAMPLE INPUT:
5
11111

SAMPLE OUTPUT:
1

Suppose the middle cow was the only cow to start off infected. Then the cows would be infected in the following order:
0 nights: 00100 (the third cow is initially infected)
1 night: -> 01110 (the second and fourth cows are now infected)
2 nights: -> 11111 (the first and fifth cows are now infected)
3 nights: -> 11111 (all cows already were infected, so no additional cows are infected)
-> ...

After two or more nights, the final state of the cows would look like the input. There are many other initial states and number of nights that could have produced the input state, such as:
0 nights: 10001
1 night: -> 11011
2 nights: -> 11111

or:
0 nights: 01001
1 night: -> 11111

or:
0 nights: 01000
1 night: -> 11100
2 nights: -> 11110
3 nights: -> 11111

All of these initial states contain at least one infected cow.
SAMPLE INPUT:
6
011101

SAMPLE OUTPUT:
4

What I have tried:

I have tried 2 different solutions, passing a few test points, some different:
1.

C++

#include <iostream>
#include <vector>

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected += (current_sequence_length + 1) / 2; // Adjusted logic
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                total_infected += current_sequence_length;
            }
        }
    }

    // Consider the last cow
    total_infected += consecutive_ones;

    // If all cows are infected, set total_infected to 1
    if (total_infected == cow_states.size()) {
        total_infected = 1;
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}

2.

C++

#include <iostream>
#include <vector>

bool is_consecutive_ones(const std::vector<int>& cow_states, int index) {
    return index >= 2 && cow_states[index - 1] == 1 && cow_states[index - 2] == 1;
}

int calculate_infected_cows(const std::vector<int>& cow_states) {
    int total_infected = 0;
    int consecutive_ones = 0;
    bool override_total = false;

    for (int i = 0; i < cow_states.size(); ++i) {
        if (cow_states[i] == 1) {
            consecutive_ones++;
        } else {
            int current_sequence_length = consecutive_ones;
            consecutive_ones = 0;

            if (current_sequence_length == 1 || current_sequence_length == 2) {
                total_infected += current_sequence_length;
            } else if (current_sequence_length >= 3 && current_sequence_length % 2 == 1) {
                if (i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                    total_infected++;
                } else if (is_consecutive_ones(cow_states, i)) {
                    total_infected++;
                    override_total = true;
                } else {
                    total_infected += current_sequence_length;
                }
            } else {
                if (current_sequence_length == 3) {
                    if (i - 1 >= 0 && cow_states[i - 1] == 0 && i + 1 < cow_states.size() && cow_states[i + 1] == 0) {
                        total_infected++;
                    } else {
                        total_infected += current_sequence_length;
                    }
                } else {
                    total_infected += current_sequence_length;
                }
            }
        }
    }

    if (override_total) {
        total_infected += consecutive_ones;
    } else {
        total_infected += cow_states.back(); // Consider the last cow
    }

    return total_infected;
}

int main() {
    int n;
    std::cin >> n;

    std::vector<int> cow_states(n);
    for (int i = 0; i < n; ++i) {
        char c;
        std::cin >> c;
        cow_states[i] = c - '0';
    }

    int result = calculate_infected_cows(cow_states);
    std::cout << result << std::endl;

    return 0;
}

This is my basic logic, however I do believe it may be incorrect.

Logic for counting how many cows (n is a constant for a number of 1s):

Middle cases:
If there is a sequence of 1s with only a single 1 (a sequence is a continued string of 1s, separated by 0s from other 1s), count how many 1s there are to find total.
If there is a sequence of 2 1s, count how many 1s there are to find total
If there is a sequence of n 1s, where n is odd and n>=3, use the formula: x=(n+1)/2 to determine the day it is. Then apply the formula n=2x-1 to weed through all sequences of consecutive 1s to determine if the day count is correct.
If it is not correct (a sequence of an even number of consecutive 1s) or (an odd number of 1s not equating to the aforementioned string), count how many 1s there are to find total.
If it is correct and applies to all other sequences, add 1 to the total.

Special cases (on both ends):
If the bitstring starts with 10, erase current total and count how many 1s there are to find correct total.
If the bitstring ends in 01, erase current total and count how many 1s there are to find correct total.
If the bristring starts with 110, there may be 2 original cows, or only 1, depending on the middle sections.
If the bristring ends with 011, there may be 2 original cows, or only 1, depending on the middle sections.
If the bitstring starts with x0 (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.
If the bitstring starts with 0x (where z is a bitstring representing the number x of 1s), there may be x original cows or only 1, depending on the middle sections.

Posted 16-Dec-23 21:46pm

User 16126649

Updated 17-Dec-23 7:22am

merano99

v2

Add a Solution

3 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

KarstenK · Answer 1 · 2023-12-16T22:21:00

You should use some "divide and conquer" strategy to solve that problem. To do it you should write different functions for every criteria.
Best is to think about some data structure like an array of cows for the data on which your functions are working.
Than write tests for every single function and eliminate the bugs. Write some useful output, like some print of all cows state as formated texts.

So you may end with some

C++

infect(Cows *cows, Cows *resulting, int pos)

function which looks if pos is infected and than infect the previous and later in the resulting area. Else you may infected too much. May you add som days_infected value to better debug it.

Good luck with your homework. Use it to improve your coding skills like debugging.

Member 16165259 · Answer 2 · 2023-12-17T22:41:00

Solution 2

Your last two points aren't necessarily correct. For instance, consider the starting position
01000001000
11100011100
11110111110
So clearly there were two original cows which is neither x nor 1.

Posted 17-Dec-23 22:41pm

Member 16165259

merano99 · Answer 3 · 2023-12-18T17:05:00

A possible solution could be to write several subroutines that find all areas with ones in a given string, a program that determines given string, a program that determines whether there have been infections overnight and then, of course one that calculates how many cows were originally infected.

The starting point for calculating the minimum number of cows in which the disease could have broken out would be a subroutine ListInfected() that finds the infected areas in a given test result would be useful. The return could be the start and end positions as well as the length in a vector. The easiest way to store the test result is in a string; a 1 for an infected cow and a 0 for an uninfected cow.

Example:

C++

string testresults = "011101"; // result 4

Some required data structures for a range and for a list of ranges.

C++

// Definitions
typedef struct { unsigned start, end, len; } areatype;
typedef vector<areatype> listtype;

listtype ListInfected(const string& testResults);

The number of initially infected cows can be counted in a further subroutine CountInitiallyInfectedCows(). To simplify the subroutine, a subroutine that calculates how many nights are required for infection would be recommended. If there is an area where an infection overnight can be excluded, the result would be the sum of all infected cows.

C++

unsigned CountNights(const string& testResults, const areatype& area);
int CountInitiallyInfected(const string& testResults);

My assumptions that no infection can have taken place overnight:

1. Special case: All bits have the value 0, no night
2. Bit sequence starts with 10
3. Bit sequence ends with 01
4. One or two '1' bits isolated by '0' in the bit sequence

And here is the main program which calls up everything.

C++

int main() {
    // Sample cases
    // string testresults = "011101";  // result 4
    // string testresults = "11111";   // result 1
    string testresults = "1110";       // result 1

    // Output of the test data
    cout << "Test data: " << testresults << endl;

    int infectcount = CountInitiallyInfected(testresults);

    cout << "Minimum number of originally infected cows: " << infectcount << endl;

    return 0;
}

How do I solve this problem for all constraints

3 solutions

Solution 1

Solution 2

Solution 3

Add your solution here

Preview 0