Блог пользователя Neel_Knight

Автор Neel_Knight, история, 3 года назад, По-английски

Hi!

I know the quoted round and problem is really old, but, just for the sake of correctness of the editorial for all those who might stumble upon it while practicing from the a2oj ladders, I believe an update to reflect the correct solution/approach would be nice and help prevent confusion.

This is the problem: https://mirror.codeforces.com/contest/456/problem/A

And, this is the editorial: https://mirror.codeforces.com/blog/entry/13336

The editorial says a check to compare all a[i] to b[i] should be sufficient to solve the problem whereas it isn't. The following sample case would print "Happy Alex" whereas it should print "Poor Alex".

Case: 5 1 1 2 2 3 3 4 25 5 30

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The editorial says:

"There is very simple solution. Let's check that for all i a[i] = b[i]. If this condition is true we should print "Poor Alex"."

You might be confusing this statement with an "if and only if". The implication in this statement is only for one side. It doesn't say that the only case where we should print "Poor Alex" is if $$$a_i$$$ $$$=$$$ $$$b_i$$$ $$$\forall i$$$. The rest of the editorial gives the full condition that should be satisfied for the answer to be "Poor Alex".

»
2 года назад, # |
Rev. 3   Проголосовать: нравится -10 Проголосовать: не нравится

Neel_Knight you are right.

My Solution :

void solve()
{
    int n;
    cin >> n;

    vpi v(n);

    for (int i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;

        v[i] = {x, y};
    }

    sort(v.begin(), v.end(), myComp);
    int pos;
    for (int i = 0; i < n - 1; i++)
    {
        if (v[i].first != v[i + 1].first && v[i].second < v[i + 1].second)
        {
            cout << "Happy Alex";
            return;
        }
    }

    cout << "Poor Alex";
    return;
}

International Master's solution:

void solve()
{
 int n;
    scanf("%d", &n);
    int a, b;
    for (int i = 0; i < n; i++)
    {
        scanf("%d %d", &a, &b);
        if (a != b)
        {
            printf("Happy Alex");
            return ;
        }
    }
    printf("Poor Alex");
return;
}

Both print different outputs in this case

2
2 1
3 2

Mine prints "Poor Alex" and his code prints "Happy Alex"

Mine and his submission both are accepted.

His code just checks if there exists any pair for which ai != bi and prints "Happy Alex". What's going on??