Changing position of data in Input file to a .cpp program Changes output unexpectedly

Question

This is what the code is for: https://www.codechef.com/LRNDSA04/problems/STACKS

Here is the code snippet:

#include<bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        vector<int> a;
        while(n--) {
            int x; cin >> x;
            if(a.empty()) {
                a.push_back(x);
            } else {
                vector<int>::iterator it = upper_bound(a.begin(), a.end(), x);
                int pos = it - a.begin();
                if(pos == a.size()) {
                    if(a[pos] > x) {
                        a[pos] = x;
                    } else {
                        a.push_back(x);
                    }
                } else {
                    a[pos] = x;
                }
            }
        }
        cout << a.size();
        for(auto e: a) {
            cout << " " << e;
        }
        cout << "\n";

    }
    

    return 0;
}

Input to this program is:

2
6
3 4 5 1 1 2
8
14 5 13 19 17 10 18 12

The Unexpected output it generates:

3 1 1 2
3 5 10 12

If the input is changed to:

2
8
14 5 13 19 17 10 18 12
6
3 4 5 1 1 2

It shows up correct output:

4 5 10 12 18
3 1 1 2

The test case with 8 numbers as input if its position is altered in the input file. Then this behavior is observed.

When looking at the run of the code via gdb, it gives expected output for both input files, no problem then.

The output is not justified, what am I missing to see?

Now you need to learn something that online competition/judge sites won't teach: ***Debugging***. Use a debugger to step through your code, statement by statement, while monitoring variables and their values and see how they change. — Some programmer dude, Jul 08 '20 at 20:28
@Someprogrammerdude OP says they get the correct result when running with `gdb`. Maybe there's UB somewhere. — cigien, Jul 08 '20 at 20:30
https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h/31816096#31816096 — Werner Henze, Jul 08 '20 at 20:31
@Someprogrammerdude Yes! I have already, Hence, I mentioned about `gdb`. Used it and went through the entire code step by step, `vector a` at the end of gdb run was showing up expected values. The output only is not coming out correct. — amarVashishth, Jul 08 '20 at 20:33

score 2 · Accepted Answer · answered Jul 08 '20 at 20:32

2

In this check:

if(pos == a.size()) {
    if(a[pos] > x) {   // this is UB

if the condition is true, then you are indexing into an invalid position of a, which invokes undefined behavior.

It seems you want to do

if(pos != a.size()) {

instead. The conventional way to check for this condition is

if(it != a.end()) {

answered Jul 08 '20 at 20:32

cigien

57,834
11
73
112

The problem was not in the comparison, it was in the assignment, I did `a[pos] = x` and this was done when condition is `pos == a.size()` BLUNDER! Replaced it by `a[a.size()-1] = x` and it all works fine now. Thanks. – amarVashishth Jul 08 '20 at 20:47
@amarVashishth Yes, that's what I meant, the incorrect check leads to the UB. See where I marked it in the answer. – cigien Jul 08 '20 at 20:49

Changing position of data in Input file to a .cpp program Changes output unexpectedly

1 Answers1