10698 - Football Sort

All about problems in Volume 106. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

contest 2004-8-7 problem C - 10698 Football Sort

Post by Maniac » Sun Aug 08, 2004 12:15 am

I kept getting WA for this easy-looking problem during contest. Can anyone tell me any mistakes I could have made or take a look at my code?

Thans in advance, Erik

[cpp]
code removed, got AC
[/cpp]
Last edited by brianfry713 on Tue Jan 21, 2014 1:51 am, edited 2 times in total.
Reason: Title

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 08, 2004 12:37 am

Did you notice that in the output of the first example there were 3 teams sharing third place? Their order was "TC Td TE", so sorting alphabetically was CaSe InSenSItIve.

Very "misselijk" to not explicitly state it in the problem text, but to hide it in the sample output.

Lesson (leermoment): If you get WA, always compare your output with the sample output using diff (Linux) or fc (DOS).

Maniac
Experienced poster
Posts: 105
Joined: Tue Oct 14, 2003 3:24 pm
Location: Utrecht, Holland

Post by Maniac » Sun Aug 08, 2004 12:52 am

Thanks, that will surely be the problem with my solution. Very "irritant" indeed that that fact about sorting wasn't stated :evil:

Nexttime I'll use the file compare for sure! Let's just say that this proves that the eye doesn't catch all differences between two sets of data :-)

Mazzel, Erik

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Aug 08, 2004 12:50 pm

The problem does say that the sorting should be done alphabetically, and I have never seen someone claim that "d < C" alphabetically. However, the problem doesn't state how a dash should compare to the other characters, but it turned out that using the ascii ordering was the right thing to do.

There are also lots of ways to get PE due to spacing errors, mainly because the problemsetter considered the sample I/O self-explanatory, but I think you've got it right.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 08, 2004 1:09 pm

't Was not the fact that "d > C" that caused the trouble, but the fact that "d < E". It is at least confusing. I can give you at least 20 problems in the set where "d > E", without any further mention than that sorting is "lexicographical". I agree that both terms are not the same, but IMO the problemsetter should have been more clear; now it was a cheap trap. And indeed the order of "abc-qrs" and "abcdef" is unclear.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Sun Aug 08, 2004 1:26 pm

Yeah, and I would say that only mentioning "lexicographical" ordering without specifying how characters are ordered does imply the case-sensitive ASCII ordering (where "d > E"), whereas using the word alphabetical implies the case-insensitive alphabetical ordering of characters (where "d < E").

Had it not been tested by the sample I/O, I would definitely have agreed with you that it was a bit nasty, but since sample I/O contained such cases, I'm not so sure.

The only problem I can think of right now (though I know there are more of them) which actually uses the word "alphabetical" is 195, though it also clarifies that upper case letters goes before corresponding lower case letters. On the other hand, there is no sample I/O to check it there.

There is also 10194 which says "lexicographical, but case insensitive", to clarify that it is not the usual ASCII ordering which is meant.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Sun Aug 08, 2004 2:09 pm

Yes, my claim was false. Can't find any. Sorry, should keep my big mouth shut...

breezechan
New poster
Posts: 4
Joined: Sun Aug 29, 2004 3:46 pm

10698-football sort

Post by breezechan » Sun Aug 29, 2004 4:01 pm

according to the describe "or alphabetically when they have the same position."
i think the first sample output should be :

1. tA 4 4 1 1 0 33.33
tB 4 4 1 1 0 33.33
3. tC 4 4 0 0 0 33.33
tE 4 4 0 0 0 33.33
td 4 4 0 0 0 33.33
6. tF 0 0 0 0 0 N/A


but it is described as :

1. tA 4 4 1 1 0 33.33
tB 4 4 1 1 0 33.33
3. tC 4 4 0 0 0 33.33
td 4 4 0 0 0 33.33
tE 4 4 0 0 0 33.33
6. tF 0 0 0 0 0 N/A


could anyone tell me if i am wrong and give me some hint.

titid_gede
Experienced poster
Posts: 187
Joined: Wed Dec 11, 2002 2:03 pm
Location: Mount Papandayan, Garut

Post by titid_gede » Sun Aug 29, 2004 4:14 pm

not case sensitive, so : TC < Td < TE
anyway it's quite annoying since i cant get AC in the contest :(
Kalo mau kaya, buat apa sekolah?

breezechan
New poster
Posts: 4
Joined: Sun Aug 29, 2004 3:46 pm

Post by breezechan » Sun Aug 29, 2004 6:25 pm

thanks,
i've got ac.

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Mon Aug 30, 2004 10:34 pm

i have solved the problem 10194 aka soccer which is very similar to this peoblem.but could not solve this problem.Any critical input plz....
thanks in advance.

Note that if several teams have are in a draw, only the position of the first is printed.

hope this draw refers to "When more than one team have exactly the same number of points, goal difference, and scored goals, these are considered as having the same position in the classification."...........if i have not mistaken.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Mon Aug 30, 2004 11:26 pm

you have right, I got accepted using this way. Clue for accept this problem is sorting I think. Critical is post made by titd_gede :-) Read it carefully and get accepted :-)

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

harry
New poster
Posts: 20
Joined: Mon Aug 30, 2004 10:20 pm
Location: HK

Post by harry » Tue Sep 07, 2004 8:08 am

Thanks for the reply.
i got ac now.
Clue for accept this problem is sorting I think.Dominik Michniewski :D
thanks man.

User avatar
mlvahe
New poster
Posts: 23
Joined: Wed Jul 30, 2003 6:54 am
Location: Yerevan, Armenia

Post by mlvahe » Tue Sep 07, 2004 1:38 pm

I keep getting WA's whatever I do.
I need your help.

Please compare my outputs with yours or give me some critical input.

[cpp]
#include <iostream>
#include <iomanip>
using namespace std;
#include <stdlib.h>
#include <string.h>

struct player
{
char name[16];
char nameup[16];
int points;
int gplus;
int played;
int gminus;
};

player p[30];
int n;

int getpid(char *pname)
{
int i;
for (i = 0; i < n; i++)
if (!strcmp(pname,p.name))
return i;
return -1;
}

int mypcmp(player *a, player* b)
{
if ((a->points) > (b->points))
return 1;
else
if ((a->points) < (b->points))
return -1;
else
if (((a->gplus) - (a->gminus)) > ((b->gplus) - (b->gminus)))
return 1;
else
if (((a->gplus) - (a->gminus)) < ((b->gplus) - (b->gminus)))
return -1;
else
if ((a->gplus) > (b->gplus))
return 1;
else
if ((a->gplus) < (b->gplus))
return -1;
else
return 0;
}

int playercmp(const void* ptra, const void * ptrb)
{
player *a = (player*) ptra;
player *b = (player*) ptrb;
if (mypcmp(a,b))
return mypcmp(a,b);
else
return -strcmp(a->nameup,b->nameup);
}

main()
{
char c, str[16];
int m, i, p1, p2, g1, g2, j, s = 1;
n = 0;
cin >> n >> m;

while (n + m)
{
if (s)
s = 0;
else
cout << '\n';
for (i = 0; i < n; i++)
{
cin >> p.name;
for (j = 0; p.name[j]; j++)
if (p.name[j] >= 'A' && p.name[j] <= 'Z')
p.nameup[j] = p.name[j] - 'A' + 'a';
else
p.nameup[j] = p.name[j];
p.points = p[i].gplus = p[i].gminus = p[i].played = 0;
}
for (i = 0; i < m; i++)
{
cin >> str;
p1 = getpid(str);
cin >> g1 >> c >> g2 >> str;
p2 = getpid(str);
cout << p1 <<' '<< p2 << '\n';
p[p1].played++;
p[p2].played++;
p[p1].gplus += g1;
p[p1].gminus += g2;
p[p2].gplus += g2;
p[p2].gminus += g1;
if (g1 > g2)
p[p1].points += 3;
else
if (g1 < g2)
p[p2].points += 3;
else
{
p[p1].points++;
p[p2].points++;
}
}
qsort(p,n,sizeof(player),playercmp);
for (i = n - 1; i >= 0; i--)
{
if (i == n-1)
cout << " 1.";
else
if (mypcmp(&p[i],&p[i+1]))
cout << setw(2) << n - i << '.';
else
cout << " ";
cout << setw(16) << p[i].name;
cout << setw(4) << p[i].points;
cout << setw(4) << p[i].played;
cout << setw(4) << p[i].gplus;
cout << setw(4) << p[i].gminus;
cout << setw(4) << p[i].gplus - p[i].gminus;
if (p[i].played == 0)
cout << " N/A\n";
else
cout << setw(7) << setiosflags(ios::fixed|ios::showpoint) << setprecision(2) << p[i].points / (p[i].played * 3.0) * 100.0<< '\n';
}
cin >> n >> m;
}
}
[/cpp]

User avatar
LPH
New poster
Posts: 34
Joined: Mon Nov 17, 2003 10:41 am

Post by LPH » Sun Oct 03, 2004 9:07 am

To mlvahe:
The sort of points, goal difference, scored goals are in decreasing order, and the name is in increasing order. In your compare function it is inversed.

(Think of the simpliest compare function, which is used in sorting numbers:

Code: Select all

int comapre(const void *a, const void *b)
{
  return *(int *)a-*(int *)b;
}
This compare function sorts number in increasing order. Work through this one and you'll know when to return negative and when to return positive. :) )
LPH [acronym]
= Let Program Heal us
-- New Uncyclopedian Dictionary, Minmei Publishing Co.

Post Reply

Return to “Volume 106 (10600-10699)”