0

I find this very stupid to ask, but I've been trying a question on Google Kickstart (Round A, 2021).
Now, firstly, I'd like to clarify that I do NOT need help with the question itself, but I'm encountering a weird issue that seems to be compiler-related. This problem only arises on certain compilers.

I am posting the question link, then the question statement if someone does not wish to use the link, then the problem I'm facing along with the code that works and the code that doesn't work.

Question Title: K-Goodness String, Round A (2021)
Question Link: https://codingcompetitions.withgoogle.com/kickstart/round/0000000000436140/000000000068cca3

Problem
Charles defines the goodness score of a string as the number of indices i such that Si ≠ SN−i+1 where 1≤i≤N/2 (1-indexed). For example, the string CABABC has a goodness score of 2 since S2 ≠ S5 and S3 ≠ S4.

Charles gave Ada a string S of length N, consisting of uppercase letters and asked her to convert it into a string with a goodness score of K. In one operation, Ada can change any character in the string to any uppercase letter. Could you help Ada find the minimum number of operations required to transform the given string into a string with goodness score equal to K?

Input
The first line of the input gives the number of test cases, T. T test cases follow.

The first line of each test case contains two integers N and K. The second line of each test case contains a string S of length N, consisting of uppercase letters.

Output
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the minimum number of operations required to transform the given string S into a string with goodness score equal to K.

Sample Input:
2
5 1
ABCAA
4 2
ABAA

Sample Output:
Case #1: 0
Case #2: 1

Explanation:
In Sample Case #1, the given string already has a goodness score of 1. Therefore the minimum number of operations required is 0.

In Sample Case #2, one option is to change the character at index 1 to B in order to have a goodness score of 2. Therefore, the minimum number of operations required is 1.

The issue:
The problem is fairly straightforward, however, I seem to be getting a wrong answer in a very specific condition, and this problem only arises on certain compilers, and some compilers give the correct answer for the exact same code and test cases.
The specific test case:

2
96 10
KVSNDVJFYBNRQPKTHPMMTZBHQPZYQHEEEQFQWOJHPHFBFXGFFGXFBFHPHJOWQFQEEEHQYZPQHBZTMMPHTKPQRNBYFFVDNXIX
95 7
CNMYPKORAUTSYETNXAZQZGBFSJJNMOMINYKNTMHTARUMDXAJAXDMURATHMTNKYNIMOMNJJSFBGZQZAXNTEYSTUAROKPKJCD

Expected Output:

Case #1: 6
Case #2: 3

The problem arises when I do NOT use std::cout.clear() at a very specific place in my code. Just printing the value of any random variable also seems to solve this issue, it doesn't necessarily have to be cout.clear() only. I'm pasting the codes below.

**Original Code (Gives incorrect answer):** 
//
//  main.cpp
//  Google Kickstart - Round A (2021)
//
//  Created by Harshit Jindal on 10/07/21.
//

#include <iostream>
#define endl "\n"
using namespace std;

int main() {
    int num_test_cases;
    cin >> num_test_cases;
    
    for (int test_case = 1; test_case <= num_test_cases; test_case++) {
        int answer = 0;
        
        int N, K;
        cin >> N >> K;
        
        char s[N];
        cin >> s;
        
        int current_goodness = 0;
        for (int i = 0; i < N/2; i++) {
            if (s[i] != s[N-1-i]) { current_goodness++; }
        } 
        
        answer = abs(current_goodness - K);
        cout << "Case #" << test_case << ": " << answer << endl;
        
    }
    return 0;
}

Incorrect Result for original code:

Case #1: 6
Case #2: 6

Modified Code (With cout.clear() which gives correct answer):

//
//  main.cpp
//  Google Kickstart - Round A (2021)
//
//  Created by Harshit Jindal on 10/07/21.
//

#include <iostream>
#define endl "\n"
using namespace std;

int main() {
    int num_test_cases;
    cin >> num_test_cases;
    
    for (int test_case = 1; test_case <= num_test_cases; test_case++) {
        int answer = 0;
        
        int N, K;
        cin >> N >> K;
        
        char s[N];
        cin >> s;
        
        int current_goodness = 0;
        for (int i = 0; i < N/2; i++) {
            if (s[i] != s[N-1-i]) { 
                current_goodness++; 
            }
            cout.clear();
        } 
        
        answer = abs(current_goodness - K);
        cout << "Case #" << test_case << ": " << answer << endl;
        
    }
    return 0;
}

Correct Result for modified code:

Case #1: 6
Case #2: 3

A few additional details:

  • This issue is NOT coming up on my local machine, but on Google Kickstart's Judge with C++17 (G++).
  • Answer for Case #2 should be 3, and NOT 6.
  • This issue does NOT come up if only the second test case is executed directly, but only if executed AFTER test case #1.
  • The issue is ONLY resolved if the cout.clear() is placed within the for loop, and nowhere else.
  • We don't necessarily have to use cout.clear(), any cout statement seems to fix the issue.

I know it's a long question, but given that a problem is only coming up on certain machines, I believe it would require a deep understanding of c++ to be able to understand why this is happening, and hence posting it here. I'm curious to understand the reasoning behind such a thing.
Any help is appreciated.

Harshit Jindal
  • 621
  • 8
  • 26
  • `cin >> s;` exhibits undefined behavior by way of a buffer overrun. The buffer doesn't have space for the terminating `'\0'` character. – Igor Tandetnik Jul 10 '21 at 13:30
  • @IgorTandetnik, in that case, shouldn't it throw an exception at `std::cout.exceptions(std::cout.failbit)`? I tried running it, and it ran without any issue – Harshit Jindal Jul 10 '21 at 13:31
  • 2
    There are things you can do to avoid the kind of pain you're experiencing right now. First, if your input is line-based, then use `std::getline` and then parse stuff out of it with `std::istringstream`. Second, use `std::string` so you don't have to worry about memory. Third, don't use variable-length arrays -- they are not standard C++. – paddy Jul 10 '21 at 13:31
  • 1
    Undefined behavior is undefined - you can't expect any particular outcome. `operator>>` just gets a `char*` pointer and has no idea how large the buffer is, so it can't do bounds checking even if it wanted to. – Igor Tandetnik Jul 10 '21 at 13:33
  • @paddy does that mean that the google kickstart judge might be running instances on a lower memory than my local system? – Harshit Jindal Jul 10 '21 at 13:35
  • @IgorTandetnik But the input is only ~100 characters long, can this cause a memory overrun? – Harshit Jindal Jul 10 '21 at 13:36
  • I'm not sure what you mean by "memory overrun"; I'm not familiar with the term. The program is writing 97 bytes into a buffer 96 bytes large. The extra byte is written beyond the buffer boundaries, overwriting whatever happens to lie in memory past it. Apparently, the thing being overwritten is something important, affecting the behavior of the program. – Igor Tandetnik Jul 10 '21 at 13:38
  • 2
    The real problem here is that whichever C++ textbook you learned `char s[N];` from is a very bad textbook, because this is not even standard C++, and not every C++ compiler will even compile this. You should get rid of it and get a good C++ textbook that teaches how to properly read input into a buffer, in a manner that logically prevents these kinds of bugs. The best way to avoid these kinds of bugs is to make it logically impossible for them to happen. – Sam Varshavchik Jul 10 '21 at 13:39
  • @IgorTandetnik I understand what you're saying and it makes sense. Thank you so much. Just one quick clarification, from what I understand, the `cin` buffer is 96 bytes long? – Harshit Jindal Jul 10 '21 at 13:47
  • @SamVarshavchik Yes, using a `string` dtype instead of the variable length char array seems to solve the issue without having to clear the `cout` buffer. Thanks a lot, I would have never figured that out on my own – Harshit Jindal Jul 10 '21 at 13:48
  • `char s[N]` is 96 bytes large when the value of `N` is 96 – Igor Tandetnik Jul 10 '21 at 13:48
  • `#define endl "\n"`? Why? – Mat Jul 10 '21 at 13:50
  • @Mat because I read on competitive programming forums that `"\n"` is faster than `endl`, so I just put it at the top because I find typing `endl` easier than `"\n"`. Also, I saw a lot of the top rankers (the top 10 global finalists) using this on their submissions, so I guess there's no harm in doing this? – Harshit Jindal Jul 10 '21 at 13:52
  • Eww, well since you also imported the entire std namespace, then any sensible person who writes `std::endl` will find it expands to `std::"\n"` and cause a compiler error. But then again, competitive programming doesn't teach you to be a good programmer, nor develop good habits. As long as you don't expect to benefit from this in the long run, it's fine. – paddy Jul 10 '21 at 13:53
  • Although it is true that "\n" is marginally faster than using `std::endl`, you will be hard-pressed to observe any tangible difference with modern multi-Ghz CPUs. All you will find on these "competitive programming forums" are bad programming practices and meaningless tricks that result in convoluted, unreadable, and hard to follow code. The only way to correctly learn and understand C++ is from an appropriate textbook. Otherwise the end result is code that only whoever wrote it can understand. Which becomes a problem if whoever wrote it can't figure out what's wrong with it, and asks others. – Sam Varshavchik Jul 10 '21 at 13:55
  • @paddy I picked this up from the global finalists on the google kickstart previous rounds. I never thought about it this way. You're right. I will NOT use `#define endl "\n"` in future – Harshit Jindal Jul 10 '21 at 13:56
  • 1
    I don't think that sentiment is quite true, Sam. `std::endl` causes a flush, which makes the process (more) I/O bound. If the output is redirected to a file, the difference can be significant. – paddy Jul 10 '21 at 13:57
  • @SamVarshavchik yes I have to agree with that. there are plenty of people who also tell us to import the entire `` header. I'm guessing that's not a good practice either? – Harshit Jindal Jul 10 '21 at 13:57
  • 2
    It's okay practice to use that header for competitive programming, because usually you want to reduce the amount of code you write. But if you pull that out in a job interview, don't expect anybody to be impressed. – paddy Jul 10 '21 at 13:58
  • Thank you for answering that. These are the things I have much more confidence with since I'm getting answers from professionals, and NOT fellow students. I just came to understand the error in this code, but I learnt a thing or two extra. So thanks again – Harshit Jindal Jul 10 '21 at 14:06
  • @SamVarshavchik could you please recommend a book from where I could learn C++? I never really followed a book for C++, but I did K&R for C – Harshit Jindal Jul 10 '21 at 14:11
  • See [stackoverflow's list of C++ textbooks](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Jul 10 '21 at 14:13
  • A flush is a flush, @paddy. And, of course, modern operating systems use buffered I/O and it might actually be faster to shuffle a few bits around in memory, with no further action and only an actual write at some point later, than to go through all the work of rendering text on a terminal. It's `fsync`, and friends, that will grind things to a halt, for a while. `std::endl` will not do that. – Sam Varshavchik Jul 10 '21 at 14:16

1 Answers1

0

As pointed out by Paddy, Sam and Igor in the comments, here is the solution as I understand it:

The problem arises because char s[N] is NOT C++ standard, any variable length arrays, for that matter. That might cause a buffer overrun, and will write over memory outside of the array, causing all sorts of weird behaviour.

The best way to avoid these kinds of bugs is to make it logically impossible for them to happen. – Sam Varshavchik

In this case, using string s solved the issue without having to call cout.clear().

Also, using #define endl "\n" might be faster when redirecting output to files, but since we're importing the entire std namespace, any person who does std::cout will get an error because it'll essentially get translated to std::"\n" which does not make sense.

Harshit Jindal
  • 621
  • 8
  • 26