Competitive programming problem

[Donatas123]

So I got a task to write a program, but my program doesn't pass all of the tests and I don't know what is the problem. I have the ability to test if my program is correct, but I don't have the tests myself.

Input: Number of letters N in first line and N capital Latin letters with spaces in between in second line.

Task: Given the list of letters, write a program which determines if it's possible to order the letters in a way that no two same letter are in a row. If possible, output one of the correct answers, if not, output "NE".

1 <= N <= 1000.


Please help and sorry if something isn't clear. I had to translate this from my native language.

#include <iostream>
#include <fstream>
using namespace std;

const int CMAX = 1000;

char letters[CMAX];

void changePos(char letters[], int from, int to){ // to - position before the letter which to insert
	char raid = letters[from];
	// if letter is being moved back
	if (from > to){
		for (int i = from; i > to; i--){
			letters[i] = letters[i-1];
		}
		letters[to] = raid;
	}
	// if letter is being moved forvard
	else {
		for (int i = from; i < to; i++){
			letters[i] = letters[i+1];
		}
		letters[to-1] = raid;
	}
}

int main(){
	int n;
	ifstream fd("duom.txt");
	ofstream fr("rez.txt");
	
	// input
	fd >> n;
	for (int i = 0; i < n; i++){
		fd >> letters[i];
	}
	
	for (int i = 0; i < n; i++){
		// checking for 2 same letters in a row
		if (letters[i] == letters[i+1]){
			// searching for a place to move the letter
			char r = letters[i];
			// checking if possible to move to start of array
			bool moveToFront = false;
			if (letters[0] != r){
				changePos(letters, i, 0);
				moveToFront = true;
			}
			// checking for other possible locations
			for (int j = 0; j < n && !moveToFront; j++){
				if (letters[j] != r && letters[j+1] != r){
					changePos(letters, i, j+1);
					break;
				}
				// no possible solutions
				else if (j + 1 == n){
					fr << "NE";
					return 0;
				}
			}
			i = 0;
		}
	}
	
	for (int q = 0; q < n; q++){
		fr << letters[q] << " ";
	}
	fr << endl;
	
	fd.close();
	fr.close();
	return 0;
}

[Handy Andy]

Hello Donatas123,

I have been working on your program for a while. It would be a big help if you would post your input file along with the output that you expect.

This way everyone will be working with the same information.

As it is my guess for an input file may not be working correctly.

In your program line 5 is OK at the global level.

Line 7 should be put in "main" and you should avoid this type of global variable. The next problem with this is that in "main" you are passing a global variable to your function. This is not needed because it is a global variable. By defining a new variable in the function, even if it has the same name as the global variable, you are creating a local variable in the function that will not see the global variable. Any changes that you make to the local variable are lost when the function ends and nothing will change with the global variable.

When you open an input file it is a good idea to check and make sure that the file is open.

Something like this:

int main()
{
	int n;
	char letters[CMAX]{};  // <--- Moved to here.

	std::string inFileName{ "duom.txt" };  // <--- Added this for use in the if statement and in line 8.

	ifstream fd(inFileName);
	ofstream fr("rez.txt");

	if (!fd)
	{
		std::cout << "\n File \"" << inFileName << "\" did not open" << std::endl;
		std::this_thread::sleep_for(std::chrono::seconds(3));  // <--- Needs header files chrono" and "thread".
		return 1;
	}

Checking if the output file opened properly is not always necessary because if the file does not exist it will be created.

I am wondering if you have to use a character array or if you could use a "std::string"? The "std::string" would be much easier.

Note; the for loop to input from the file will skip any spaces in the file and put all the letters one after the other. Not sure if that is what you want.

Hope that helps,

Andy

[Browni3141]

There is an algorithm which is both faster and easier to understand/implement than what you're using. Under what conditions will there be no solution?

Your current program fails with input 5 aaabc. It outputs aabac

[Thomas1965]

I think there will be no solution under 2 conditions:

1 if the length of the number is odd and the highest count of a char is > (length / 2) + 1 => aaaba

2. if the length of the number is even and the highest count of a char is > (length / 2) => aaabab

[Browni3141]

You could use the single condition:

if (highest char count > floor((length+1)/2))

The question was meant for OP to answer. The point of solving problems like this is to improve critical thinking skills. There is no benefit to OP if the answer is given freely.

My follow up question is, what does the answer look like when "highest char count == floor((length+1)/2)?" What simple strategy can we use to generate a solution given that one is known to be possible?

[Donatas123]

Thank you for your reply Andy,

Input file is working correctly. I had clear instructions on how to take input, so that was not the problem.

I moved char array inside the main function as you have suggested. I didn't even notice what I was doing with that. I know that using such global variables isn't very good and I will keep this in mind next time.

As for checking if file opened correctly, I don't think that it's necessary here, because tests output "invalid input" if something is wrong with that.

I didn't think about using strings then, but it could be easier, now that I think about it.

And yes, I want to skip spaces and put all letters one after the other.

[Donatas123]

Thank you for your help Browni3141,

After you gave an example input that was giving wrong output, I saw what was the problem in my solution:

I changed line 61:

i = 0;

With:

i = -1;

That is because after I put a letter in a different place, I want my loop to start from the beginning. When my loop went to next iteration, i got incremented. I didn't think of that.

Now all of the tests pass.

[Donatas123]

As for your follow up question.

I think I could have come up with the condition myself pretty easily.

What does the output look? The char that is used the most is in positions that differ by 2.
E.g.: A B A D A B A D A C A

First solution that comes to mind is to remove those char from the array and then put them back in correct places.

Now that I think about this more, I think using a string would be better for this task in general.

While this solution works, I don't know if it's a good nor a fast one though. I don't know if this would be good for bigger inputs.

My question is: Is there a faster and a better way of doing this? And could I make my solution faster? How should I avoid such errors in the future? Because I found a couple and in a bigger problem I think it would take much more time to correct them on the spot.

[Handy Andy]

Hello Donatas123,

You wrote:

As for checking if file opened correctly, I don't think that it's necessary here, because tests output "invalid input" if something is wrong with that.

Do not count on this. When I changed the file name and commented out the if statement the program did not open the file, but did run to its end and the output file was empty.

Any time you open a file for input it is best to check that the file is open before you continue with the program.

I do not know how much your original code has changed, but working with your original post I did come up with this idea. Start by removing the first number from the input file and read the file this way:

while (fd >> ltr)
    letters[n++] = std::toupper(ltr);

Now "ltr" is defined as a "char" and I initialized "n" to zero when defined. This way you do not have to count all the letters in the input file and start with a number, which is error prone, the program will count for you.

The best I can tell the program is doing what it should do. The above code should make things easier.

Hope that helps,

Andy