SUM12

plz explain the question

Why answer for 2 is 1. 2 = 2 , 2 = 1+1 so it should be 2.

Is it partition or composition??? Explain the example of 4?? We are getting 5 compositions for 4.

The test case seems wrong for n=2.

it shld be 2(1+1 and 2).

and 5 for n=4 and so on.

I think you mean "1 and 2".. not "either 1 or 2"

please clarify.. PRONTO!

You cannot have a weak composition ie. 2+0 is not allowed as it contains a 0.

according to wikipedia,
for number 4 compositions:
1 + 1 + 2 and 1 + 2 + 1 are two diffrent compositions

are we looking for all compositions in which there is either 1 or 2 as a summand?

then for number 2 result would be:

1 + 1,

2 (according to wiki this is a valid composition of 2)

for number 4:

1 + 1 + 2,

1 + 2 + 1,

2 + 2,

2 + 1 + 1,

1 + 1 + 1 + 1

there are lot more compositions satisfying foor 4 than 3.. something is not clear in problem statement..

The answer for the second test case is 5 and the sample test cases are being updated.

We are getting 13 ways as follows for 6, can you please clarify

2 + 2 + 2 - 1 way

2 + 2 + 1 + 1 - 6 ways

2 + 1 + 1 + 1 + 1 - 5 ways

1 + 1 + 1 + 1 + 1 + 1 - 1 way

Total = 13 ways

We are getting 13 ways as follows for 6, can you please clarify

2 + 2 + 2 - 1 way

2 + 2 + 1 + 1 - 6 ways

2 + 1 + 1 + 1 + 1 - 5 ways

1 + 1 + 1 + 1 + 1 + 1 - 1 way

Total = 13 ways

for n = 6

1 1 1 1 1 1 (1 combo)

1 1 1 1 2 (5 combos)

1 1 2 2 (6 combos)

2 2 2 (1 combo)

how come ans is 8.

13???

if it is "1 and 2" how can you get answer 1 for n = 2?

for any interpretation of the problem that's been suggested, the sample input/output makes no sense yet.

"but  2 = 2 doesn't contain 0  ?"

Please clarify.

if for input 4 output is 5
then for 6 also it is wrong

The answer for the last test case is 13. The sample output is getting updated.

Shouldn't the output for the case '6' be 9 with the following possible combinations:

1. 5+1, 2. 4+2, 3. 4+1+1, 4. 3+2+1, 5. 3+1+1+1, 6. 2+2+2, 7. 2+2+1+1, 8. 2+1+1+1+1, 9. 1+1+1+1+1+1

how come people are getting correct submissions if the test cases are still being updated...

hey admin.. pls answer other forums as well... plsease look at muy doubt for prob 2

The test cases in the server are correct so submissions will be accepted if they are correct. Only the sample test cases were incorrect however they have been updated now.

Answer for 6 is not 9. Please read the question carefully.

is the question completely correct??Does he really need "1 OR 2"??Becoz then how is result for 4 just 3??

Plz explain..

@Ravi please refresh the page. The sample test cases have been updated.

Can you please explain once how the answer for 2 is 1?

is the answer for test case 3 is 1????????

What about first test case? The answer for 2 should be 2

2 = 2

2 = 1+1

Or we can't make composition with one summand?

according to wiki, you can, check example for number 5

2=1+1

is the only composition.

Why is 2=2 not a composition? Its summands are only 1 or 2 right? Which of the rules defined in the problem does it fail?

why is the answer for 4 3

4= 2+2

4= 1+1+1+1

4= 1+1+2

4=2+1+1

so it should be 4

Your_mom - 21st Nov,2009 20:35:50.

why is the answer for 4 3

4= 2+2

4= 1+1+1+1

4= 1+1+2

4=2+1+1



so it should be 4

// answer for 4 is 5 (you forget 4 = 1+2+1), and this answer is already in examples.

But I don't understand why 2=2 is not valid composition.

if for 2 answer 1 then for 1 answer 0?

does dis work for odd numbers also

does dis work for odd numbers also?

@LBM coders

The input constraints have been specified in the problem statement.

but there are no input constraints for this problem.

why?

can the value of n be 0 ?????

about 0:

...a composition of a positive integer n is a way

but in wiki also said:

Conventionally the empty composition is counted as the sole composition of 0

Please Clearly mention that what exactly would be the answer for values of n=0 and n=1 ?

again...the same fucked up sitiuation...

Are you guys fuckin morons? should have been concentrating in your English classes rather than licking lollies in ur 3rd grades.

Assholes! How come u expect us to code, if we cant understand your questions.

We got a lot better things to do, rather than correcting your stupid mistakes.

I got a suggestion for you all, get a new life.

Try www.getanewlife.com free download!

If u actually clicked that link, u proved you are a fuckin idiot!

Hello! Could you please, for an example and to feed our curiosity, post compositions counted for n=2 and n=4?

What is the output for 0 and 1 ?

Do they result in 0?

Please specify the lower bound of n...

You may consider n >= 2.

for n=4

1+1+1+1

1+1+2

1+2+1

2+1+1

2+2

=5 ways

There are many people who have got the solution accepted.

what is the mininum value for n ?

0,1,2 ??

Whenevr i try to submit my code it says compile error.....

i am using java and the interface i am using is blue j (class design)

can u plz temme how do i submit my code den....?

umm.. I am pretty much sure my algo is correct, yet judge gives me a wrong answer.. can you look into that?

Ya same here ..

@ LBMCoders

there are accepted java submissions.

everythin is comin rite on ma compiler..dnt noe y on submission i'm being shown a RUNTIME ERROR..

Milk of Samovar, Exhaust of East, into [beep] of judge

@ ohmygod

check the faq for rumtime error

what do you mean by summand "1 or 2" if we have 1 summand then for 2 we can have 2,but on the other hand u said that we cant have a weak summand as 2=2+0 is not allowd....??? i am not geting it...ADMIN plzz help

what do you mean by summand "1 or 2" if we have 1 summand then for 2 we can have 2,but on the other hand u said that we cant have a weak summand as 2=2+0 is not allowd....??? i am not geting it...ADMIN plzz help

Can you clarify what is the expected output for n = 1 ? Is it 0 or 1 ?

@ BigRed

n>=2

ok...

you actually get the wrong checker or something... I've just got accepted... and me accepted solution outputs

1

3

8

for the sample input...

@ ivmis@yahoo.co.uk

what ?? we hv been asked composition nt partition

no I mean they corrected the output in the statement and haven't corrected the checker... they just got the wrong checker...

admins, do you read this?.. you got the wrong checker...

admin plz say something what is this

currently working checker accepts number of compositions of n-1 as the answer for each test

i had submitted the code according to the sample output and got 10 penalties ... but after ivmis@yahoo.co.uk i changed my code and got accepted .... what the hell is this... atleast second time you coukd have given the correct outputs ...

Thanks to ivmis@yahoo.co.uk Judges should recheck we wasted hel lots of time just to get it right....

ivmis@yahoo.co.uk: Thanks! You are right. I made the off-by-one change and I get Accepted. Admins! Fix this!

i request that this problem be corrected and rejudged ....

All the penalties because of wrong solution should be taken off.....and the correct answers should be rejudged...

WTF??

Wasted 4 hours of my life just bacause of your wrong judge.

The sample updated output is incorrect according to the judge. Our accepted code gives a different answer as output.

such irresponsibility wasn't expected from CodeChef, you people should have verified the judge before conducting an event of so high stature.

Our end sems are going on, still we took part and are feeling really cheated x-(.

What the hell is it?

I solved this problem with wrong code.

I printed the value just previous sequence of the real value.

But, judge said "correct".

Damn it.

Our first submission should have been accepted.

By standard rules of composition even 2 is not a special case. 12 penalties just to figure out judge data was wrong is quite painful :(

There has been some confusion and therefore the penalties for this problem will not be counted. Codechef will come to a decission of how this problem has to be delt with.

solution should be rejudged. It was quite shameful event.

To BruteForce, you should have commented here long ago like ivmis@yahoo.co.uk and not only you to all of them who got it correct after those painful attempts should have made some comments here....

Will there be a re-judge ?

because this is insane ..!! i should have got AC in my first attempt !

Any plans to reconduct the event? :P

Am quite sure, you are going to lose lot of your regular participants by this incident.

Atleast, I am one of them :(

@ All

No penalties for this solution would be counted. Whether this problem is suppose to be considered or not while rating the teams is not yet decided. All contesting teams will have to wait till monday for the same.

Our apologies for the glitches in the problem statement and the judge.

@Admin : What are you going to do about the time we wasted in finding out the error in your judge?

It was a hell lot of difficult task. may be you can form a question out of this in your next event :P

Shame to other users who got the solution accepted and didn't notify about the error to the admin.

hail ivmis@yahoo.co.uk! . Atleast, now I can sleep peacefully.

@ TheGodParticle

We are trying to figure out the fairest decission for this problem in the best interest of all participants. You will soon be notified about it.

Please cancel this question and give one or two question in another session of this event

:O

I was beating myself for over 3 hours that I couldn't even code a simple fibonacci without errors.. FML

We started with this problem.. as we felt its easy ( which infact it is ).. and wasted a lot of time on that, and that surely affected our time to solve other problems and also got us a lot of frustration.  we were able to do only one other .. and I don't think.. there can be any 'fairest decision' except a rematch with things taken care neatly this time. I wonder.. how can such a obviously.. big mistake happen in such a big contest with just 5 problems to be taken care of .

@Blitzkrieg:

True

@Admin : No matter what you decide, I don't believe anything other than rescheduling the event is a solution for the mistake.

Besides the 'big blunder', there were other issues also, like server down, database error, dns error, Connection timeout, etc etc etc. You were simply unprepared!

Conduct an event after a thorough test.

In my opinion, there is no decision that is completely fair, even rescheduling the event. How can you simply forget about the teams who did well in the contest by concentrating on the other questions? The server problems were there equally for all teams (infact, IIITH teams had internal server problems also at that time!).

The best decision now would be to take all the 7 teams who did 3 problems to the finals.

@TheGodParticle : True.. thats how it is with other famous programming sites.. in a time based contest. They have a reserve day ( mostly the following day ) for each and every match in their mega events or tournaments and are prepared for any small technical glitches or big ones like we have here now. May be things happened very fast with codechef.. they should have done server maintainance etc., before snacktest and get the problems/solutions checked thoroughly well before the main contest with at least 3 - 4 different guys. Any way.. as Aniruddha said.. " ... fairest decission in the best interest of all participants ..." we can hope for a re-match, because its not about this sum12 alone, this affects solving other problems too.

@Aniruddha:  You wrote.. "The test cases in the server are correct so submissions will be accepted if they are correct. Only the sample test cases were incorrect however they have been updated now." .. Did you check the main i/p o/p thoroughly .. before stating this ??

quoting anil kishore:

"Aniruddha said.. " ... fairest decission in the best interest of all participants ..." we can hope for a re-match, because its not about this sum12 alone, this affects solving other problems too. "

Rematch won't help..  as u can see all these studious guys of various colleges took interest and participated despite it being the "end sems" season in  India and may be this time they dare not risk their sessionals for bad servers.

Also, the prob with SUM12 was with all participants not just specific teams(though some picked it at first sight others just didn't bother to look at the comments..)

Its true that SUM12 affected solving other problems ,but again it was the same  with all participants.

@Dream "The best decision now would be to take all the 7 teams who did 3 problems to the finals." yeah I support you ..yes that would be fair enough..!!

and for SUM12, either discard the entire problem or don't count the penalties for those who finally got it AC that seems the best option available.

Discarding the problem SUM12 would be unfair to those who solved only two problems including SUM12 and had to make a lot of submissions to get it accepted which involved a lot of precious time. The teams that solved only one problem (other than SUM12) might get an advantage if they solved their only problem earlier.

Not counting the penalties would be unfair to those who got this problem accepted earlier having made certain assumptions (which are neither correct nor incorrect since the problem statement was ambiguous) and could not solve all three problems whereas counting the penalties would be unfair to those whose solutions were correct but couldn't get it accepted due to the ambiguity in the problem statement.

Planning a rematch would be unfair to those teams that have now qualified for the onsite finals. Not planning a rematch would be unfair to those who could have got selected for the onsite finals had there been no ambiguity in the problem statement of SUM12.

Taking the top 7 teams to the onsite finals would be unfair to the other teams that solved only two problems including SUM12 and could have solved another had there been no ambiguity in the problem statement.

There does not seem to be a universal solution to this problem. In my opinion, what can be done is that the top 20 teams be allowed for the onsite finals (the arrangements could be tough but we can, at the least, talk about it and try to figure out if it can be made possible) but the teams that were among the top 5(or top 7) in the online competition be given a special prize as well.

Some of my not-so-fair thoughts....

1.) A whole new (re)match is what happens with other famous sites.. even if someone solves very tough problems and there are errors in very easy problem. If final exams for many of us is a problem, we can reshedule to Jan.

2.) may be.. the teams who solved 3 can be taken for onsite finals.. and there can be a  rematch for other ranks.. for all others (or may be for all who got 1 AC ).

and also.. teams should not be differentiated with ranks now (like.. top5 , top 20 etc.,).. it can be on the number of problems solved (3,2,1,0).

" We are aware that some of you faced some issues with the problem SUM12. We will make a final decision on this on Monday. The current rankings are provisional and will be updated on Monday."

WE had a problem or YOU had a problem?

I agree with Akshay.

The battlefield was same for everyone. If wrong examples were there it was same for everyone.

Now discarding penalities will be more unfair. We were sure about the logic and tried to adapt according to the cases. This was valid for all. But now, the people who wasted time in this problem, it will unfair to them. Even in TOPCODER, their was a SRM in which 500 points problem was ambiguos.

SO, they rescheduled the match, as thier can be no other fair means.( to a max). So, I say either the match should be reheld, or it should be left as it is considering the same situation to every contestant during contest time. There could be no better solution than that.

Yes agreed ..

No Matter what there cannot be a rematch !

quoting anil kishore:

"and also.. teams should not be differentiated with ranks now (like.. top5 , top 20 etc.,).. it can be on the number of problems solved (3,2,1,0)."

yeah that can be considered fair enough..  and

a possible solution can be:

1. those who got 3 probs solved shud be taken for the finals.(7 teams)

2. those who got 2 probs solved given equal prizes.(16 teams)

quoting Doesitmatter:

@Manmeet Singh :

The battlefield was same for everyone. If wrong examples were there it was same for everyone.

While the battlefield was the same for everyone, it's not a battlefield you would want to set an example of. It was definitely not a level playing field in terms of algorithms contests. Wrong judge data is something that is definitely a huge time wastage for contestants. You don't want to check the guessing skills of contestants in a programming contest. If the objective is to judge one's guessing prowesses, hold some other kind of contest, maybe minesweeper.

While I didn't participate in Snackdown, I have been to other contests where the issues in judge data have just rubbished the whole contest for me. If you debug your problem for 3+ hours just because the judge data is out of constraints, it simply rubbishes the contest for you. It might not even be fair for teams that decide to give up after some time.

As far as this particular incident is concerned, I am sure some people might have given up due to frustration. After all, how difficult can it be to code a simple O(log n) Fibonacci ? I would have been upset had I run into this issue.

The best thing the contest organizers can and should do is have another contest with a level and fairer playing field.

A level field doesn't mean a field that is unfair for everyone. Let's have a contest that is well prepared and well done.

@ Kshitij

I think I have wriiten about rematch in my post. Its not that we were not frustrated with such cases.

You are not saying anything new. I am in favour of rematch or no results changed. You want a rematch.

Thats it.

@ Manmeet Singh

Totally Agree with you.
Have a rematch or no results change.

quoting AKSHAY

"

a possible solution can be:

1. those who got 3 probs solved shud be taken for the finals.(7 teams)

2. those who got 2 probs solved given equal prizes.(16 teams)

"

This is agreeable !!

or else have a rematch !

@Manmeet :

I wasn't trying to say anything new either. The only bone of contention was your statement that the playing field was level.

To draw an anlogy, you statement was like saying that having a football match on a basketball court is alright because the playing field is level for both the teams.

No offences meant though.

I suppose the best decision would be to have the ranking finally on the basis of when a team solving SUM12 submitted their first correct solution...despite the judge issuing a wrong answer at that time and keeping all others as it is...if there is such provisions..

or to have a rematch

or if nothing is possible keep this as it is now..

"I suppose the best decision would be to have the ranking finally on the basis of when a team solving SUM12 submitted their first correct solution...despite the judge issuing a wrong answer"

the problem statement was updated and not to forget the comments..   and those who got it AC with 0 penalty.. (I think there are certain teams)..  wht abt tht?

so thts nt the right solution...

By the way..when will be the decision by the judges will be declared??

http://blog.codechef.com/2009/11/23/re-snackdown-december-20th-4-7pm/ Check this.