ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1273. Tie

What the heck is wrong with this stupid problem?
Posted by Jiang Xu 16 Jul 2005 03:08
I've seen there are many WA's for this problem, even if you only need basic knowledge to solve it. Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

#define MAXN 101

typedef struct shit
{
    int x, y;
};

shit a[MAXN];
int N, i, j;
int m[MAXN];

int cmp(shit a, shit b)
{
    return a.x < b.x ? 1 : 0;
}


int main(void)
{
    scanf("%d\n", &N);
    for (i = 0; i < N; i ++)
        scanf("%d %d\n", &(a[i].x), &(a[i].y));
    sort(a, a + N, cmp);

    int ans = 1;
    m[0] = 1;
    for (i = 1; i < N; i ++)
    {
        m[i] = 1;
        for (j = 0; j < i; j ++)
            if (a[j].y < a[i].y && 1 + m[j] > m[i])
                m[i] = 1 + m[j];

        if (m[i] > ans) ans = m[i];
    }

    printf("%d\n", N - ans);

    return 0;
}
Re: What the heck is wrong with this stupid problem?
Posted by Sandro 16 Jul 2005 22:37
Try K=0. Good luck!
Re: What the heck is wrong with this stupid problem?
Posted by Macarie 18 Jul 2005 14:39
"Although i find my source perfect, i cannot imagine what makes it receive Wrong Answer on test #3..."
Oh yeah...
Re: What the heck is wrong with this stupid problem?
Posted by Danica Porobic 19 Jul 2005 01:50
I couldn't find bug in your source, but since I had many problems myself on this one I can send you my code. E-mail me on dporobic at gmail dot com .
Re: What the heck is wrong with this stupid problem?
Posted by Jiang Xu 11 Aug 2005 00:02
You were right. Thanks!