10778 - Mathemagicland

[little joey]

IMHO this problem description easily qualifies for the worst one ever.
Can anybody please explain what is meant by all those symbols, indexes, indexed-indexes, etc? In the summation a variable l (or is it i, the picture is barely readable) is introduced, but I can't figure out what it has to do with the rest. Same for the variable m in the output statement. And then the variable k, which can be negative, if I interpret the input description correctly. But how should I regard it as the upper limit to the product PI(j=l,k) ?
There are bad problem statements and bad problem statements. But this one beats them all.

"~~The brothers in white suits will come for me to take me to Mathemagicland. There I'll meet Donald Duck who will give me my medicine. Then I will understand the problemstatement.~~"

[bugzpodder]

okay I purposely made the problem confusing so that an relatively easy problem would seem hard (so the problem statement which describes the problem gets a little messy, but everything you need to know is there). So it is unfair to say this is the worst problem statement ever (i agree that it is hard to understand, but it is NOT vague - I tried to give a PRECISE mathematical definition rather than a vague heuristic definition which might be clearer). note that the unproportional image size wasnt caused by me. it is caused by OpenOffice when i was saving it as a html file.

denote the sigmas as s_i

basically i give you a system of equations involving x_i and s_i
and you are trying to solve it.

now the relationship with s and x is as follows (taken directly from the problem statement):
Sum (1<=a1<a2<...<ai<=n) Product (j=1..k)x_aj=s_k

the indicies ai just implies that when we are multiplying x_1*x_3*x_5
we take 1<=3<=5, so we avoid other possibilities such as x_3*x_1*x_5, or equal indices such as x_3*x_3*x_5

take k=1
Sum x_a1=s_1
so what are possible values of a1 such that 1<=a1<=n? there are n possible values

ie Sum (i=1..n) x_i=s_1

Take k=2
Sum x_a1*x_a2=s_1

for all possible values of ai such that 1<=a_1<a_2<=n

so it is:
(x_1*x_2+x_1*x_3+...+x_1*x_n)+(x_2*x_3+x_2*x_4+...+x_2*x_n)+...+(x_(n-1)*x_n)=s_2

k=3 gives you

(x_1*x_2*x_3+...+x_1*x_2*x_n)+...+x_(n-2)*x_(n-1)*x_n


so in general, summing up the product of k x's with indices as all possible ways of choosing k numbers from n, and to get s_k

and your job is to determine all solutions of (x_1,x_2,...,x_n), and print the values of x_i and print all of them which are rational numbers in the order specified with the output. If all of them are irrational, print "No Solution."
if you still have problems understanding it, let me know

[hujialie]

To author bugzpodder:

I tried a lot of times to solve this problem, but all got WA.
i think what this problem ask us to do is this:

1.Buid up a n-polynomial equation of x ;
2.find all rational solutions from small to large, say x[1]<=x[2]<=......<=x[m];
3.if m equals zero, print "No soltution.", otherwise print x[1] x[2] ..... till x[m].

Do you think this understanding is correct, and please give some more
complex examples than those in the sample?

Thanks in advance.

[Loirey]

i wonder whether the only person who ACCEPTED this problem is just the author...

from contest time till today we (i and my teammates) are submitting our code again and again and again (but got WRONG ANSWER again and again and again...) i think we've completely understand what the statement said and WHAT THE AUTHOR WANT (i.e. what this problem is exactly). well i'm not writing down our algorithm here, for an all-known reason. i'm just hoping that the author can give us a real sample format for outputing NO. as all u can see the format is different between what the statement describled and what he wrote on this ele-board.

i've try formats below, all getting WA.
1) \n
2) No solution\n
3) No solution.\n
4) NO SOLUTION\n
5) NO SOLUTION.\n

anthoer tip: i used "long long" for temporary calculation. if it is not enough, i'm afraid that this problem is tooooo difficult for online contests. anyhow please let me know the proper int type ( or need high precision ??)

further more, i have some words with the request given by the author.
"If all of them are irrational, print "NO SOLUTION""
i think this is somehow not reasonable on mathematica. "no rational numbers" does not mean "no valid solutions". if the author will, i hope that he can fix the request into a more proper one. however we will just follow what he require

[bugzpodder]

To author bugzpodder:

I tried a lot of times to solve this problem, but all got WA.
i think what this problem ask us to do is this:

1.Buid up a n-polynomial equation of x ;
2.find all rational solutions from small to large, say x[1]<=x[2]<=......<=x[m];
3.if m equals zero, print "No soltution.", otherwise print x[1] x[2] ..... till x[m].

Do you think this understanding is correct, and please give some more
complex examples than those in the sample?

Thanks in advance.

Thats good. note that you want to print c*x[1], c*x[2] where c is the leading coefficient.
the first actual test case:
39 968
3894 -18854 14432 -18788 8404 27808 -14102 15444 -26202 -4114 4158 -3080 11528 20130 -2706 -7546 5016 -27742 -2970 9856 -10274 26092 -6710 -4510 -132 0 0 0 0 0 0 0 0 0 0 0 0 0 0
output
-968 0 0 0 0 0 0 0 0 0 0 0 0 0 0 264

[bugzpodder]

i wonder whether the only person who ACCEPTED this problem is just the author...

two ppl got accepted, either both of us have the same bug in our code, or that the answer is correct

from contest time till today we (i and my teammates) are submitting our code again and again and again (but got WRONG ANSWER again and again and again...)

yah yah, stop complaining there is only one person who made a submission to my problem during the contest and no one made a submission until after i submitted my solution yesterday and it is not you.

as all u can see the format is different between what the statement describled and what he wrote on this ele-board.

what i said on this board was just by my memory, which could be wrong. the test data was made according to the official problem statement, not stuff i said after the contest on the e-board. the problem statement is precise to the best of my knowledge

i've try formats below, all getting WA.
1) \n
2) No solution\n
3) No solution.\n
4) NO SOLUTION\n
5) NO SOLUTION.\n

if you sent this as a clarification during the contest, i would tell you "read the problem statement"

anthoer tip: i used "long long" for temporary calculation.

good me too. its enough. again all answers fits in an int.

further more, i have some words with the request given by the author.
"If all of them are irrational, print "NO SOLUTION""

we are not playing word games here now are we? you may wish to output whatever you wish, but if you get it wrong, dont blame me. there is always a solution in the complex, so the word rational is implied, not to mention it is mentioned several times in the text. The context of rational is implied, and it is not ambiguous. which means that it is enough.

[Michael Goldshteyn]

I refuse to even bother working on this problem for the following reasons:

1) The problem description is confusing. I don't care how mathematically rigorous it is, it is difficult to understand.
2) The messages posted so far to elaborate on the confusing mathematical definition do not offer much help in this regard. A restatement with more words isn't necessary. A plain English non-rigourous definition is.
3) The sample input/output set is trivial and degenerate, doing absolutely nothing to elucidate the correlation of the output to the input. Future problem setters take note - provide us with examples to try to demonstrate the various aspects of the problem statement. They do not have to be very complex and contrived cases, but they should under no circumstances be tiny degenerate ones either.
4) Mathematical rigor has its place in math textbooks. It has no place on a contest site where people try to solve these things for fun. If you must have a mathematically rigorous definition, in order to resolve ambiguity, make sure you provide enough plain English text to make the problem description obvious to the average non-PhD math student, unless, of course, you only want two entries in your contest.

A true statement of how good and interesting your problem definition is, will be the number of correct entries for the problem.

Michael Goldshteyn
First place holder on 10738, 10745 and 10763

"~~ A man in a black suit will come to take you away at 1:42 (AM or PM? Where is the mathematical rigor where you need it?)... you should bite his hand off, rather than suffer the rigorous torture of a definition of some leaf on a tree without stating how the leaf relates to the tree or the tree relates to the rest of the forest. Don't worry, though, a single thin stripped bare branch will be provided to illustrate this complex relationship. ~~"

[Adrian Kuegel]

two ppl got accepted, either both of us have the same bug in our code, or that the answer is correct

The 2nd one is Anupam, so it doesn't count (I guess he send your code). Anyway, I don't want to say your program is wrong, only to clarify that there is only one solution so far.

[Per]

Some of the biggest problems with the problem statement (in order of magnitude) are the following:

1) "Each n-tuple solution should be outputted in exactly one line and in the form of: kx_{a_1} ... kx_{a_m} such that ...".

That's an m-tuple, what is m?! I'm guessing that what you mean is: "in the form of: kx_1 ... kx_n such that x_i \in Q and kx_1 \le kx_2 \le kx_n". If not, I have no clue as to what you might mean.

2) "extract the rational numbers in order of magnitude from the n-tuple above, given that: {\sigma_1, ..., \sigma_n}"

I'm pretty sure you mean "given the values of \sigma_1, ... \sigma_n", but it took me a while to understand that (given that I really have understood it). The way it's stated it sounds like the sigma_i:s are logical statements.

3) As Joey said, the image of the formula describing the relation between \sigma and x is too small. It is impossible to read, though I'm pretty sure it says that \sigma_i is the i:th elementary symmetric polynomial evaluated on x_1... x_n.
http://mathworld.wolfram.com/SymmetricPolynomial.html

[little joey]

okay I purposely made the problem confusing so that an relatively easy problem would seem hard (so the problem statement which describes the problem gets a little messy, but everything you need to know is there).

Well, if it was your intention to confuse, you succeeded excelently. I'm sorry, but I always thought programming contest were meant to test one's programming skills, not to get confused.

So it is unfair to say this is the worst problem statement ever (i agree that it is hard to understand, but it is NOT vague - I tried to give a PRECISE mathematical definition rather than a vague heuristic definition which might be clearer).

I was giving my opinion, call it fair or unfair. I read some problem statements and solved some problems, so I thought I was entitled to have one. Now that I understand what this problem is about (at least I think I do), I _know_ it is the worst problem statement I've ever seen. I'm no mathematician, but I very much doubt that any mathemathician would call your definition PRECICE.

note that the unproportional image size wasnt caused by me. it is caused by OpenOffice when i was saving it as a html file.

Yeah, that's a very good excuse. Next time you're cought driving drunk, tell the officer that it's not your fault but blame it on the alcohol in the beer you drank.

[bugzpodder]

ok i know that you've solved over 1000 problems, and you ar third on the list. but so what? let me reiterate. The problem statement is precise, but it seems to me that you just dont understand math notation, which is taken from mathworld. And thats too bad. if you dont like it, then go solve some other problems

[bugzpodder]

I refuse to even bother working on this problem for the following reasons:

good for you, since you are not going to work on it, i dont care what your reasons are. and your sacrasm does not amuse me. excuse me for not laughing. Also, please do not bother to give advice to me.

[bugzpodder]

Some of the biggest problems with the problem statement (in order of magnitude) are the following:

1) "Each n-tuple solution should be outputted in exactly one line and in the form of: kx_{a_1} ... kx_{a_m} such that ...".

That's an m-tuple, what is m?! I'm guessing that what you mean is: "in the form of: kx_1 ... kx_n such that x_i \in Q and kx_1 \le kx_2 \le kx_n". If not, I have no clue as to what you might mean.

well m is defined after "such that" it means that you skip over all the irrational/complex values, and output only the rational ones. {a_1,a_2,...,a_m} is a subset of {1,2,3,...,n} such that x_a_i is rational number.

2) "extract the rational numbers in order of magnitude from the n-tuple above, given that: {\sigma_1, ..., \sigma_n}"

I'm pretty sure you mean "given the values of \sigma_1, ... \sigma_n", but it took me a while to understand that (given that I really have understood it). The way it's stated it sounds like the sigma_i:s are logical statements.

yes, it is "given the values of {\sigma_1,...,\sigma_n}"

3) As Joey said, the image of the formula describing the relation between \sigma and x is too small. It is impossible to read, though I'm pretty sure it says that \sigma_i is the i:th elementary symmetric polynomial evaluated on x_1... x_n.
http://mathworld.wolfram.com/SymmetricPolynomial.html

yes, that exactly. in fact, thats where i got my definition from when i wrote the problem statement

[bugzpodder]

two ppl got accepted, either both of us have the same bug in our code, or that the answer is correct

The 2nd one is Anupam, so it doesn't count (I guess he send your code). Anyway, I don't want to say your program is wrong, only to clarify that there is only one solution so far.

thanks for letting me know.

Anyone who has a WA solution is welcome to send me their code. i wish to compare it with my own and my IO to ensure the correctness, and fix any problems.

Oh and, I've really had enough of this... if you have something legit to say, dont hesistate to post. I'll be happy to address any issues/problems. I will probably fix the problem statement in a later time after i make sure i get every suggestion.


But if all you are doing is to mock the problem statement like little joey and Michael Goldshteyn did (i dont care if you think you are the best programmer in the world), then I will tell you this... If you dont like it, skip it, just quit WHINING, and GET A LIFE!

"~~The brothers in white suits will come for me to take me to Mathemagicland. There I'll meet Donald Duck who will give me my medicine. Then I will understand the problemstatement.~~"

"~~ A man in a black suit will come to take you away at 1:42 (AM or PM? Where is the mathematical rigor where you need it?)... you should bite his hand off, rather than suffer the rigorous torture of a definition of some leaf on a tree without stating how the leaf relates to the tree or the tree relates to the rest of the forest. Don't worry, though, a single thin stripped bare branch will be provided to illustrate this complex relationship. ~~"

[Per]

1) "Each n-tuple solution should be outputted in exactly one line and in the form of: kx_{a_1} ... kx_{a_m} such that ...".

That's an m-tuple, what is m?! I'm guessing that what you mean is: "in the form of: kx_1 ... kx_n such that x_i \in Q and kx_1 \le kx_2 \le kx_n". If not, I have no clue as to what you might mean.

well m is defined after "such that" it means that you skip over all the irrational/complex values, and output only the rational ones. {a_1,a_2,...,a_m} is a subset of {1,2,3,...,n} such that x_a_i is rational number.

I'm sorry, but if we're talking mathematical preciseness, then that's definitely not what you're saying in the problem statement. You're only saying that the a_i:s are a subset of those indices where x is rational, not that it is exactly those indices. Also, that would indicate that a solution where all the indices are non-rational should be outputted as a blank line (and that the answer "No solution." is impossible).

A better formulation would be: "Each n-tuple solution with at least one rational component should be outputted in exactly one line, in the form of kx_{a_1} ... kx_{a_m}, where a_1, a_2, ... a_m are those indices such that x_{a_i} \in Q, and such that kx_{a_1} \le ... \le kx_{a_m}".

Either way, I think this is just messing up an already messy problem, so my actual suggestion would be for you to change the problem so that you only ask for solutions where all n components of x are rational.

If you want more suggestions to make the problem statement more readable, here are a few:

# The whole definition of the problem should be restructured. One possibility is the following: "only if he first finds all n-tuple solutions: ..." --> "only if he first finds all rational n-tuple solutions {x_1, ..., x_n} to the system of equations \sigma_k = [....], given the values of sigma_1, ..., sigma_n".

# "Two solutions are said to be distinct if they are not the same." --> "Two solutions are said to be distinct if their output is not the same."