AlGoreRhythm's blog

By AlGoreRhythm, history, 8 months ago, In English

1848A - Vika and Her Friends

Hello CF! Could you explain to me why these two codes output different results?

Problem 1848A: Vika and Her Friends

My Code:

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

void solve() {
    ll n, m, k; //Size of mall and # of Vika's friends
    ll x, y; //Vika's coordinate
    cin >> n >> m >> k >> x >> y;

    //For each of vika's friends, check whether they are in the same square as her. If so, print NO
    for(int i = 0; i < k; i++) {
        int xx, yy;
        cin >> xx;
        cin >> yy;
//!!! PROBLEM SEEMS TO BE HERE vvv!!!
        if((x + y) % 2 == (xx + yy) % 2) { 
            cout << "NO" << endl;
            return;
        }
    }
    cout << "YES" << endl;
//!!! PROBLEM SEEMS TO BE HERE ^^^!!!
}

int main() {
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

Editorial's code:

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
 
int32_t main() {
    int t;
    cin >> t;
    while (t--) {
        int n, m, k;
        cin >> n >> m >> k;
        int x, y;
        cin >> x >> y;
        string ans = "YES\n";
        for (int i = 0; i < k; ++i) {
            int xx, yy;
            cin >> xx >> yy;
            if ((x + y) % 2 == (xx + yy) % 2) {
                ans = "NO\n";
            }
        }
        cout << ans;
    }
    return 0;
}

The problem seems to be inside the for-loop. I used a different method to output a "NO" when it's found that one of Vika's friend is on the same square colour as Vika. This method seems to yield an incorrect result when there's a previous test case ('t') that outputs a 'NO' already (although I could be wrong).

I asked ChatGPT several times with different prompts on why these two code output different results, but I'm still quite confused. Out of options, I have to resort to asking you guys. Would be really nice if you guys could help a little newbie like me. Thanks!

EDIT: MISTAKE FOUND by Hazzler. Thank you for your time!

By using the return function, I didn't finish reading all the input from testcases that yields a NO before moving on to the next testcase. The result is the rest of the input from this testcase will be read as an input for the next testcase, leading to an incorrect result.

In hindsight, this mistake is one of the 200 IQ moments of all time.

  • Vote: I like it
  • -1
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you check with ll xx,yy?

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

You have a return statement inside a for loop, so it terminates before you read the whole data. Idk whether it was intentional or not, but somehow this still passes pretests.

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Doesn't seem to be the case. The 4th test case seems to yield a "YES" instead of a "NO".

    Yes the 'return' is intentional. My logic is: once it's found that one friend starts on the same square colour as Vika, it outputs NO and move on to the next test case. Without return it would print a "NO" and a "YES", so I have to prevent that.

    Just FYI, I tried replacing "return" with "break" and it doesn't change things. Only implementing the editorial's for-loop leads to the correct solution.

    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You need to finish reading previous testcase before starting reading the next one.

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh riiiight (-‸ლ). Truly 200 IQ move by me. Thanks.

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by AlGoreRhythm (previous revision, new revision, compare).

»
8 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

c++ can give you 3 % 2 == -1 (example), so maybe you need abs