Soccer League

are the numbers in the input separated by spaces or not? and can there be a newline at the end of the last output?

Yes

Yes

How should the program take the input data? Through a file or what?

Read FAQ

I am printing the output just after inputting every case. Is it wrong format and can result in Wrong Answer? Plz. reply ASAP admin

@admin i think my code is working well but getting WA

@admin i think my code is working well but getting WA

@admin can you provide some more test cases

what will be the answer for n=1?

is there any input in which no team have a chance for wining

for case

3

1 1 1

1 1 1

1 1 1

then which team have chances for wining

what will be output for n==1

@admin i think my code is working well but getting WA

@amritpal: Read the problem statement carefully. Your input is an invalid one.

@admin what is output for n==1

@kailash

can u tell me what is the output for n=1

My code is working good too in my PC for lots of tests, but I'm getting WA there...

@amritpal , @shrish read the problem statement carefully. Answer for n=1 is clearly understood.

@kailash

can u tell me in the first sample case

all the team loose the match 0 0 0

then how it is possible

@umesh

do u mean it wud b 0 because aii=0

for n=1 answer should be 1 as there would only one team in the league.....so it is the winner

@ admin

can u plsss tell me what is the output for n=1

@admin plz reply  what is output for n==1

@H Umesh can you give some more test cases plz

Is there any need to check for invalid inputs.

I think output for n = 1 has to be 1. and thats quite obvious i suppose.

where can I find other tests to that?

admin can you please provide some more testcases

could please provide some more test cases..please..

something may be broken in the website testcase...

My code is working good oin my PC for lots of tests, but I'm getting WA there... [2] PYTH It's gotta be correct. something's broken on the website. Please look in soon.

@admin if a team can become a co-champion

then what would be the output ?

My code is working good in my PC for lots of tests, but I'm getting WA

The test cases provided are enough. The judge tests the code for a number of inputs other than the ones provided here. That might be the cause for WA, TLE. I'd request you all to stop asking for test cases and prepare sample ones locally.

what is output for

4

3

1 1 0

0 0 0

0 0 1

8

0 1 1 1 1 1 1 0

1 1 1 1 1 1 0 0

1 1 1 1 0 0 0 0

0 1 1 1 1 1 1 0

0 0 0 0 0 0 2 1

1 0 0 2 2 0 0 0

1 0 0 0 0 0 0 0   

1 0 0 2 0 0 0 0

5

1 1 1 1 0

0 1 1 1 0

0 0 1 1 0

0 0 0 0 0

0 0 0 0 1

2

 0 0

1 0

@ admin plz reply what is output for

what is output for

4

3

1 1 0

0 0 0

0 0 1

8

0 1 1 1 1 1 1 0

1 1 1 1 1 1 0 0

1 1 1 1 0 0 0 0

0 1 1 1 1 1 1 0

0 0 0 0 0 0 2 1

1 0 0 2 2 0 0 0

1 0 0 0 0 0 0 0   

1 0 0 2 0 0 0 0

5

1 1 1 1 0

0 1 1 1 0

0 0 1 1 0

0 0 0 0 0

0 0 0 0 1

2

 0 0

1 0

Plz any body help me.

@Md. Najmuzzaman: Please read the question carefully!!!! your input is invaid!

only 4th test is ok, others are invalid - look team A wins with team A  ?!

@Md. Najmuzzaman

your test casrs are wrong .........read the problem statement............

ok thanks.Now What is the output of this case 

4

3

0 1 1

0 0 0

0 0 1

8

0 1 1 1 1 1 1 0

1 0 1 1 1 1 0 1

1 1 0 1 0 0 0 1

0 1 1 0 1 1 1 1

0 0 0 0 0 0 2 1

1 0 0 2 2 0 0 0

1 0 0 0 0 0 0 0   

1 0 0 2 0 0 0 0

5

0 1 1 1 1

1 0 0 1 1

0 1 0 1 0

0 0 0 0 0

0 0 0 1 0

2

 0 0

1 0

sorry

plz any body help me.

my program says:

100

11010000

10000

what do you think>?

my output is

100

11010000

10000

01

and 4th test: 01

so i have the same output, by my program gets WA ;/

is a team also considered as a champion if it is a co champion?

Everybody - DO NOT POST TEST CASES. DO NOT ASK FOR TEST CASES.

Continue to do so and you may be disqualified from the contest.

@Md. Najmuzzaman

Your inputs are wrong, for the fact aij+aji=1 i.e either one of aij or aji is 1 while other is 0

More over aij=aji=2 i.e if one of aij is 2 then other is also 2

If i supply my code with your wrong input it gives

100

11010000

10000

01

@ Admin

admin can you please provide some more testcases. I am getting WA while is have tested with good no of test case, all give fine answer

is a team also considered as a champion if it is a co champion?

I code works well in my machine for many test cases... but getting WA here.. how to proceed ???

Hmm.. I am almost there seems like my code is not working for some last test case... :| ... i cant come up with such awesome test case ...

How do i test my test case output now. This is so big that I have to write another code for this.... ohh wait... how do i know the second piece of code is giving right output..... i am in one sad situation....

what should be output if no teams played at all

@kapil Do you mean the case where no teams have played up to now? Then every time still has a chance to be the winner.

@admin Is a co-champion a winner?

Everybody: DO NOT ASK FOR, POST OR DISCUSS TEST CASES HERE. You will not get any assistance from the admins unless they find a problem with the judge, in which case they will inform us, but even then, they will never give out the test cases.

thanks brian

Everybody:  plz help me out.. i m getting correct results... but codechef shows wrong answer....

i can't understand where the problem is......

Plz help me...my code which i hav written is giving me correct answers according to the sample test case..but i am getting WA.. please send us some more test cases...

@admin.. alone with WA, can u also specify the TEst case... so that we can get to know the root of error

@Sheikh and shwet: dont hope too much guys guessing the extreme test cases is part of the problem as well and its expected from you only. Nobody will help you with guessing the test cases. I know its really frustrating but no use i guess.

@Everyone

Do we have to also do testing on data as well like if the input is like this:

1 1 1

1 1 1

1 1 1

this is invalid input... do we have to consider all these...

The test cases provided and the problem statement are enough to understand this problem. No additional test cases will be provided.

This is really addictive.......... not useful though.

everyone:

my program is working on every input in give... but i dont understand why i get WA... somebody help me out....

Does increase in number of submissions decrease the scoring?

@vignesh From the main contest page: "You can submit solutions as many times as you'd like, there are no penalties for incorrect submissions."

@Sheikh Of course nobody is going to help you. Please don't ask silly questions.

@vignesh That question is answered on the contest page.

@Everyone (who is asking for test cases) Once the contest is over, these problems will be moved to the practice section; we may then be able to discuss test cases. In the meantime, hopefully you will finally listen to the admin and stop talking about them, or you will risk disqualification. The FAQ says the input is guaranteed to be valid.

@Sheikh Again, when the contest is over, you may be able to get help (anyone who has made a successful submission will be able to see your submission). In the meantime, what Stephen said is harsh but true.

The persistent question about co-champions above can be answered by analysing the provided test cases.

if any one has successfully solved this problem... can u provide me the output for the following test case if possible

1

8

0 2 0 1 2 1 1 0

2 0 0 2 1 1 0 2

1 1 0 1 2 0 2 0

0 2 0 0 0 2 0 0

2 0 2 1 0 1 1 1

0 0 1 2 0 0 1 0

0 1 2 1 0 0 0 1

1 2 0 1 0 1 0 0

hopefully the test case it correct

No. Please don't ask for anyone to break the rules of the contest.

@Shwet Anyone who asks or answers that sort of question risks disqualification.

@Shwet Your input is invalid. I'm not going to explain why because this is a contest.

will a co-champian considered a winner?

I'm using visual c# 2008 express edition.. while i upload the solution, should i select mcs(1.0.1) or mcs(2.0.1)??

Cuz i'm selecting (1.0.1) and getting WA even though all the cases i try are correct.

And if i select (2.0.1) i get the message saying that solution cannot be submitted in that language..

Kindly help, Thanks...

@shwet

ans of test given by u is 00001000

and tell me what is ur output for the same input...

i'm also gettiing wa

In case there are more than one team which has the largest number of points, these teams will be co-champions of the league

What is meaning of the above statement ??? in question

Submissions to C#2 are now working.

@Arvind Please re-read the statement.

Anyone discussing test cases from this point on will be disqualified.

@Sumit Bindal  and @ admin.... does the format given has to be followed strictly... my code gives output for the given case and then ask to input the next case.... i mean do we have to print it in the multidimensional array format that you have given under the heading OUTPUT and have to take all the input cases at once without interruption.....can it cause in getting a WA...

please help..................

The comments are increasingly becoming a way for coders to interact regarding the problem in ways they are not supposed to. I know that this is more the fault of the participants rather than the feature, but if disabling this feature stops such discussion, I would request admins to disable the feature of comments on the problem page.

The comments are increasingly becoming a way for coders to interact regarding the problem in ways they are not supposed to. I know that this is more the fault of the participants rather than the feature, but if disabling this feature stops such discussion, I would request admins to disable the feature of comments on the problem page.

@arun Read the FAQ

@Keshav We debated over this and found that the pros of having comments far outweight the cons. As specified earlier, anyone found discussing test cases will be disqualified.

@ Admin: Could you look at the submission

http://www.codechef.com/viewsolution/179332

Why a wrong answer ?

Assuming all the inputs are correct and according to the criteria given in problem, I think my submission is correct.

@Aniruddha Do u considered the humor too?

@ admin....thank you for responding....

Who will be considered as champian between: a team with n no. of wins with no games left to play AND a team with n+1 games unplayed and rest lost .

@ Admin

c#2 is working now.. however my doubt is still not clear.. Does Visual C# 2008 Express Edition come under C# or C#2 ?? Kindly Reply.. Thanks..

@ admin.......i have read the problem atleast 50 times.... and submitted it for every possible thing...... like if there is only one team playing then code should print 1 or 0.......... i have submitted both versions if i am not wrong all the constraints are correct like 20 for the test cases and 140 on the no of teams... but every time getting wrong answer.... please have a look on my code...... check it with your own test cases..... if then also it gives wrong answer then just give me an acknowlegement...........  check out my latest submitted code........

@Mahesh Only if you answer that question correctly will you be able to reproduce the sample output.

@arun said above that if n == 1, then the output should be "1". On the other hand, Nirley was getting Wrong Answer before and I don't know if they fixed it (for some reason, I can only see the first page of submissions).

Nirley is continuing to try, and fail, to solve this problem, and no one else has commented on the correct output for n == 1. Given the series of warnings we have already had from the admins and other users, it is probably inadvisable to comment further, except to suggest that Nirley try a different output for n == 1, if they haven't already.

you mean to say that admins can not see my submitted code..... i thought it was barred only for the participants....

@arun I know this is really frustrating, but given the comments above, both the problem statement and the test cases would surely have been thoroughly checked by now. You can try deliberately making your program crash under certain conditions; then if you get Runtime Error instead of Wrong Answer, you know you have those conditions. Read the problem carefully...the number of test cases is not constrained...

:)  I know this sounds silly but I've tried almost everything to make my problem correct. But this wrong answer is really getting on my nerves.

@arun I believe that, for all problems, any admin and anyone who has solved the problem can see any submission for that problem, while for some problems, anyone can see any submission for that problem. I never tried to suggest otherwise.

However, if there is nothing wrong with the judge, the admins generally will not do anything. They are happy for other users to give hints, as long as it's not a contest.

@admin: It is not mentioned in the problem but do we have to check for the correct input also? Also I am confused with the situation when one team has played all games, won 'N' no. of games and the other team has not played 'N+1' no. of games, rest lost. If such a situtation, who would be the champion for that case ? Here is one example:

0 2 2 2 2 0

2 0 1 0 1 0

2 0 0 1 1 0

2 1 0 0 1 1

2 0 0 0 0 1

1 1 1 0 0 0

Is it correct to say that only first team has the possiblity to be a champion ?

YOU HAVE BEEN WARNED! DISCUSSING TEST CASES WILL GET YOU DISQUALIFIED!

@Lucky (and anyone else you really wants to discuss this) You should e-mail them. At least that way you won't get in trouble.

Correction:

0 2 2 2 2 0

2 0 1 0 1 0

2 0 0 1 1 0

2 1 0 0 0 1

2 0 0 1 0 1

1 1 1 0 0 0

sure

>:( I'd really like to have test cases for this problem after the contest is over.

Can an extra space or an extra newline also generate "Wrong Answer"?

hmm.. this problem looks more trickier than i thought or am i trying too hard and its too simple anyhow.. Ill have to wait till the contest is over... sigh....

@Lucky According to the FAQ, the input is guaranteed to be correct.

in my netbeans ide the program is running currectly but here it is showing wrong answer what the problem can be there

http://www.codechef.com/viewsolution/179830

@admin Kindly check this solution and let me know if there are any mistakes..

Cuz the problem statement appears quite simple and im getting answers for all test cases(on my system) that i've tried, yet i keep getting WA whether i try it in C# or in C#2.

Thanks.

@Brian Drake- first of all thanks for responding.....

you mean to say that no. of test cases are not constrained to 20..... i mean does about 20 mean 21 or 23 can also be the no of test cases..... any ways it's been 2 days and now i am waiting for my euraka moment to solve this problem and still reading the problem..... can you give me your email id i will email my code to you... you can check it with your test cases.. BECAUSE NOW I WANT A HUMAN TO TELL IT'S WRONG ANSWER.....

@arun I would love to help you that way, except that, as everyone can now see, I am also competing in this contest. Therefore, I cannot accept code from anyone until I have solved the relevant problem. However, once I have solved a problem, I will be able to see all submissions for that problem anyway.

Currently, I'm in the same situation as you: getting Wrong Answer and having no idea why. I'm going to investigate further when I have a compiler...

@ Brian Drake-........ya i saw it..... all the best...........hope you will solve it soon...i liked your strategy i think you have already read all the problems thoroughly..........

@Brian, @arun Helping people during a contest is against the rules and you will be disqualified before. Asking for help too is against the rules. People have been disqualified before for the same reason. I would request you two to refrain from emailing / discussing code and / or test cases.

@Brian You would not be able to see anyone's code after submission. That works only for practice problems.

it seems that in calculating the probability of winning of a team the chances of the other team is not being considered . . .

if it is so... my program is right...but still getting W.A..........

please help !!! :)

think a bit about this problem. It is not so easy as it seems to be. Sample test cases do not cover the trickier part of this problem.

@arun I have no compiler now :(, but I will when I go out later :). I guess it's not surprising that I keep getting Wrong Answer, then. What do you mean, "i liked your strategy"?

even I could not understand why I was getting a WA but when a particular instance came to my mind , everything became so so clear .....

It is very subtle thing and u will appreciate the trick in the problem after solving it ....

so just take a break , come back and may be that special case will strike in ur mind .... keep tryin' and best of luck

@arun, @admin If I had already solved a problem myself and then came across someone else's code, I might test it against my own cases but (at least in a contest) I wouldn't give them the results, as people were doing in the comments above! I think arun just wanted someone to confirm that their program was wrong.

For the record, I haven't been in contact with any contestant except through this website.

The easiest way to confirm a program is wrong is by submitting it and seeing if it says accepted or not.

@ admin ---- i apologise if i have broken any rules.... and same goes here... i too haven't been in contact with any body participating in the contest.....

@Stephen arun obviously does not trust the judge (I can see why!): "BECAUSE NOW I WANT A HUMAN TO TELL IT'S WRONG ANSWER.....".

@arun: I don't need to see your code to know it's wrong.  My reasoning is as follows.  If your code is actually correct but not being accepted by the judge, that would mean that my code which is accepted by the judge must be incorrect (along with nearly 40 other people's code). :)

@David It is possible for forty people to be wrong. Whilst I am not yet suspicious of the judge, I too am very frustrated at this problem, and those comments don't really help.

I see alot of frustration at simple problem but no comments on hard problems... I guess people get more frustrated when they think what they are doing is simple and still cant do it.... well same goes for me aslo :)

aahhhh finally got it right............nd dat too in 2nd best time

feels great!!!!!

made 20-25 unsuccessfull submissions for this one (have to reconsider my thought that this is an easy prob)........n think still more to come..... ;).......but still its fun.............:)

n frustrating too ;)

i m tryin to submit a solution in g++ 4.3.2.... but i m being shown a compilation error.. even though it is workin prefectly fine in the dev C++ compiler that you hav recommended to use ..

pls reply..

@admin are inputs in each line separated by spaces or continuous????

@admin can u please check my code...m getting right answer for all the cases i can think of....

@admin My algorithm passed even though I have a test case where it fails.

@Richard If you haven't already, you can add a comment to your successful submission telling us what that test case is and everyone will be able to see it when the contest is over.

what is the OUTPUT for

2

4

0 1 1 0

0 0 2 0

0 2 0 0

1 1 1 0

5

0 2 2 2 2

2 0 1 1 0

2 0 0 1 0

2 0 0 0 1

2 1 1 0 0

@Pradeep

admin said this higher up the page (though it is stated on the contest page too):

<em>Anyone discussing test cases from this point on will be disqualified.</em>

Congratulations :)

yes  yes  yess...........

hurryy.. huh. finally i got it..

Feeling very well after 9 days i could able to solve it..

Just I remember one thing.

CROP LIKE YOUR LIFE DEPEND ON IT.:)

@admin when i submit a code, a message appears "contest_problem_id is required",,,what does that mean?

m newbie here

its my first time

can u please tell me how to take input

whether as .txt file or somhw else???

@admin

I am getting a right answer for the given set of test cases but after compiling I get a wrong answer msg. What could be the problem?

I am seriously pissed off right now. I dont know where I am going wrong but the following solution runs perfectly fine for any imaginable test case possible on mine computer but gives wrong answer here. Please shed some light and tell me whether it is because of the compiler difference because I am working on Turbo c and here it is gcc or there is something wrong in my code

Here's my solution : http://www.codechef.com/viewsolution/185900

If it is not accepted it does not run fine. Perhaps I will tell you why, but obviously not until the contest has finished.

@arun, @Abhishek Thanks for your support. I believe I have a correct algorithm, as coded in my last submission, submission 186319, but it is using too much memory. I don't have time to optimise it.

I'm not able to submit solution, is there any problem with site ???

Hpw long to put this in practice problem ?

Pls ne body can tell me what's the problem with this problem???

In my strategy,

I just tried to figure out how many wins a team can achieve.

And if that exceeds current highest win then i think the team has a chance to be champion.

I think there is an input for which my strategy is false, pls can nebody tell me what i m missing???

This is really surprising to know that most of the people getting accepted for this question dont have correct solution.

This is really ridiculous.

I have tested some solutions on a test case and some solutions do not match with Mark Greve solution.(which gives result as expected).

This is really frustrating.

I worked on that test cases and people are getting their solution accpeted without having their solution correct.

Really frustrating.

@Vikas: Indeed.  I suspect that solutions not using a variant of network flow are incorrect.  It is disappointing that the test data was so weak.

Can somebody please post all the test cases used while evaluating the answers?? It will really help me to know what did I miss in this problem with my approach..

My solution was to simply calculate number of non zero elements in a row for each team and if only one row had max non zero elements, then only that team had the chance of winning or else all teams having the max non zero elements had chances of winning, rest had zero. This worked peefectly for the above sample inputs and some others I created but I couldn't think of any other test case for which this wouldn't work. Please post all the test cases you have so that I can check what improvements should I make in this algorithm.

Uh, how about a test case where one team has already lost all of its games? Then it has the most nonzero elements but obviously can never come first..

Or a case where no team had any 0s left.. obviously it is possible to play all games and not have everyonetied

Hard to find cases where your algorithm does work, really.

@ blackcloud: How about a case

1

5
0 1 0 2 0
0 0 2 1 1
1 2 0 1 2
2 0 0 0 1
1 0 2 0 0

Output:01100

What is yours?

I hope this might solve your difficulty

@ blackcloud: How about a case

1

5
0 1 0 2 0
0 0 2 1 1
1 2 0 1 2
2 0 0 0 1
1 0 2 0 0

Output:01100

What does your  Output show?

I hope this might solve your difficulty

@ blackcloud: How about a case

1

5
0 1 0 2 0
0 0 2 1 1
1 2 0 1 2
2 0 0 0 1
1 0 2 0 0

Output:01100

What is yours?

I hope this might solve your difficulty

except few ones in top slot ,many solution are not working for either this:

1.

5

0 0 0 0 1

1 0 0 1 0

1 1 0 0 2

1 0 1 0 2

0 1 2 2 0

o/p should be 00111

2.

5

0 0 0 1 1
1 0 1 0 2
1 0 0 2 2
0 1 2 0 2
0 2 2 2 0

o/p should be 01111

Those who have not done max flow has o/p

01111 and 11111

can any explain the logic behind it clearly.....

my logic is add all the non zero number and print all the higest numbers=1 and the team with sum less than maximum sum =0 BUT i got wa every tiime....

http://discuss.codechef.com/showpost.php?p=2895&postcount=4

@Vikas Kumar

My solution gave a WA but I got the correct output for the two test cases you mentioned, the given test cases and many test cases I tried it on.

Would've liked to see the chef's test cases and see where my solution went wrong.

My logic was as follows:

In any any league, there will be nC2  matches.

Total points scored would be nC2*3

For an incomplete table Scored points=3*Matches Played.

Remaining Points=Total Points-Scored Points

A team "x" has a chance to win the championship if there is a way to distribute points among all teams such that no teams gets more points than team x.

To do so, first calculate the Maximum possible points(MaxPoints) each team can score.

Then arrange the teams in Descending order of MaxPoints.

Locate Team x in the sorted array and maximize its score (i.e. make it win every remaining match).

For all teams below Team X in the array maximize their points as they can't win having MaxPoints  less than or equal to Team X.

This reduces the pool of remaining points(RemainingPoints) from unplayed matches. Less points to distribute among the teams above X in our sorted array.

Next step is to distribute points among the top teams in a manner favorable to Team x. This is done by making the team above x win matches until it's score is equal to team x then making it lose all other matches. Repeat with the other teams above x.

If a teams victory in any match makes it's points higher than Team X's then the team is forced to lose. If either teams victory increases it's score above Team X's the match is not played.

If remaining points == 0 all matches have been played with the condition that no team has scored more than Team X.

Every unplayed match leaves 3 points in the Remaining points pool. If at the end, Remaining Points>0, at least one match was not played. Hence Team X cannot win.

As I mentioned in the forum, any greedy solution like this should fail (even though a lot passed). For example, you say '.. making the team above x win matches until its score is equal to team x then making it lose all other matches'.

How do you choose which matches it should win and which matches it should lose? This decision is obviously very important. As a simple example, say you have the following matches left to play, with all teams only allowed to win 1 more game:

A plays B, A plays C, A plays D, C plays D.

If you let A beat B, then the winner of C vs D will always end up with two wins. But A beating C or D allows a solution.

stephen can u expalin the logic clearly......

i didn't get ur point..... help plsss

i am new programmer........

I'm not sure what part you don't understand. If you don't know what maxflow is, try googling it.

I feel sort of crazy, my solution (which worked for any test cases I came up with) was

1) get the highest number of games won by any team --> X

2) if the number of games won plus number of games left to play is >= X, the team may win/tie for the championship.

Is that a feasible algorithm? If no, have a test case to consider? I got WA after handling the one team case both ways, so not that one..

No, as I've already said, any greedy solution will fail. Again, it is easy to come up with a test case, for example:

1
5
0 2 1 1 0
2 0 1 1 0
0 0 0 0 1
0 0 1 0 1
1 1 0 0 0

Currently, teams 1, 2, 4 and 5 are all on 2 points, and 3 is on one point. Your solution would say all the teams on 2 points could win; yet obviously as 1 and 2 are playing each other, one will end on three points and thus only team 1 or 2 can win.

And of course, that is a simple case; things can get a lot more complicated than that.

@Stephen Merriman

Hey dude I am having trouble figuring out what you wanted to say in your reply at my comment. Quoting from it :

My apologies, I did indeed misread your algorithm. It still isn't correct; I'll find you a test case later on today.

Very simple example:

1
4
0 2 2 2
2 0 1 0
2 0 0 1
2 1 0 0

The team with the most nonzero elements is the first team, so you would say only the first team can win - yet obviously if that teams loses all of its games, someone else will win. (In fact, the answer is 1111).

@Anyone who can help me out

Here was my solution to soccer league:

http://www.codechef.com/viewsolution/182926

but I am not able to understand where my algorithm goes wrong .

Thanks in advance

Sorry i forgot to mention that it seems to be workin correctly on all the test cases mentioned out here ..

There's really no point in me continually coming up with test cases for all the failed solutions. Tell me your 100% rigorous proof that your solution will always result in the correct answer.