Neel_Knight's blog

By Neel_Knight, history, 3 years ago, In English

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://codeforces.net/contest/456/problem/A

And, this is the editorial: https://codeforces.net/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

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

| Write comment?
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 years ago, # |
Rev. 3   Vote: I like it -10 Vote: I do not like it

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??

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    You should read the bounds of the problem (In particular, your test case does not satisfy them).