10733 - The Colored Cubes

Eduard · Post by **Eduard** » Wed Oct 06, 2004 1:21 pm

Hello.
I'm getting WA for this problem.Please somebody who got it AC tell me outputs for this Inputs.
INPUT

Thanks.

gawry · Post by **gawry** » Wed Oct 06, 2004 5:45 pm

My (accepted) program's output is:

Code: Select all

57
240
800
2226
5390
11712
23355
43450
651886250
41679670000
651049541750000
7415811246281250
41417415833541750

Eduard · Post by **Eduard** » Wed Oct 06, 2004 8:09 pm

My program is giving the same answers as yours but i'm getting WA.I hade precalculate the whole values and store in one array but it didn't help.WA,WA,WA....What it could be???

For example some I/O.
INPUT

Code: Select all

OUTPUT

Code: Select all

1
10
41679670000
130795534551
833335599237051
8351406190633950
20429992757318592
9168895864471035
41417415833541750
144313962627
374614113302976
7656303440392490
144313962627
43450
144313962627
46937498610
55853094675
76351
10
709376
3602676

Somebody please check,are this outputs right?
Thanks.

Eduard · Post by **Eduard** » Wed Oct 06, 2004 8:47 pm

Finally I got it AC.I just change my cauculation to BigNumber cauculation and get AC.I will try to find for what cases my last program is giving wrong answer.I want to know does anybody else use BigNumber for this problem?
Thanks.

wiktor · Post by **wiktor** » Wed Oct 06, 2004 9:06 pm

BigNumbers are not necessry for this problem. The solution for n=1000 fits in long long.

midra · Post by **midra** » Thu Oct 07, 2004 1:47 am

please...
could someone help me to understand how to think this problem...
I have stayed hours and I can't get the correct idea
thx...

Eduard · Post by **Eduard** » Thu Oct 07, 2004 2:55 pm

I use nCm in my program that why I ca't use long long int and use double but get WA.

midra · Post by **midra** » Tue Oct 12, 2004 2:10 am

please...
could someone give me some hint to solve this problem??
I would appreciate very much
thanks

wiktor · Post by **wiktor** » Wed Oct 13, 2004 8:17 am

google -> Polya theorem

abishek · Post by **abishek** » Wed Oct 13, 2004 8:55 am

better search term
google for "burnside's lemma"

midra · Post by **midra** » Thu Oct 14, 2004 4:04 am

thanks a lot for your answers
byee

shamim · Post by **shamim** » Mon Oct 25, 2004 8:55 am

Hey, this problem seems to have a closed form solution. That is, a formula relating the input and output. The actual code would then be effectively two lines, take input and give output using formula.

The problem is a well known one in group theory. but I wonder, did the problemsetter wanted us to use the formula, or he expected us to derive it or an equivalent one using basic combinatorics.

Dreamer#1 · Post by **Dreamer#1** » Sun Oct 31, 2004 1:43 pm

hi ppl,

hmm... well i don't think you need to know all those mathematical things to solve it... it took me 20 mins to write a simple simulator that gave me the results from n=1 to 6 and from there it took me another 10 mins to code my solution using those values and simple nCm calculations that everyone knows more or less... the runtime of my solution is O(1) too but the initial pascal's triangle generation took some time (ofcourse you can avoid that) and so it ran for around 0.050 sec...

i never heard of all these mathematical things you have been discussing here cause i'm too poor in mathematics

(infact i've never done any mathematics apart from whats done at skool and ofcourse i ain't a CS student either)

but there are more people in my category and in most cases there remains a second way for us to get through.. thanks God...

regards...

Dreamer

abishek · Post by **abishek** » Sun Oct 31, 2004 7:35 pm

the answer is actually a polynomial in n. so you were lucky to get it right by fitting it with the first
six values.
actually, for any of these one doesnot need burnsides lemma because anyways the answers is polynomial in n and thus you can try to fit it.
but try 10601, cubes. Slightly more difficult to fit!

backslash null · Post by **backslash null** » Thu Nov 04, 2004 2:26 pm

this problem is easier than it seems.
you don't have to any `lemma' to solve this problem.just think of a simple combinatorial formula.
after u find that try to solve it manualy and you get a polynomial of n lie this:
(n^6 + ?*n^4 + ... +8*n^?)/?

good luck.