10253 - Series-Parallel Networks

Observer · Post by **Observer** » Sun May 11, 2003 1:18 pm

I 'hard-coded' and got an AC for this problem......

But I really want to know how to calculate the answer.

Please tell me how. Thanks!

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sun May 11, 2003 2:39 pm

You said you got AC.
What is the problem?
Can you write an idea briefly? I have been solving this problem for 2 months and still don't know the answer...
Can you send me your code?

Observer · Post by **Observer** » Sun May 11, 2003 3:04 pm

Nah...

I just 'hard-coded' the whole thing.

That means I simply find the answers for n = 1 to 30 from the web and put them directly in the program. I have no idea how to do the calculation......

P.S. When n = 30, Ans. = 90479177302242 !!!!

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sun May 11, 2003 3:16 pm

Where did you find it???

Observer · Post by **Observer** » Sun May 11, 2003 3:28 pm

I don't appreciate hard-coding (I feel sorry for myself after hard-coding

).

But if you really need some help, try this website

The On-Line Encyclopedia of Integer Sequences
http://www.research.att.com/~njas/sequences/index.html

There you can find many interesting integer sequences (including the one in this qq!!!)

A formula (which I couldn't understand) is even provided.

Dmytro Chernysh · Post by **Dmytro Chernysh** » Sun May 11, 2003 4:06 pm

What is the answer for n=3? 3?
Because I can not find the sequence

It is really cool site

Observer · Post by **Observer** » Mon May 12, 2003 8:43 am

Hey, Dmytro_Chernysh, I saw your name on the Ranklist!!!

So how did you solve the problem?

Please tell me!!!!!!!!!!!!

Dmytro Chernysh · Post by **Dmytro Chernysh** » Mon May 12, 2003 12:15 pm

Well, I just precalculated the answer ...
Moreover, I took the outputs from that site

BUT, I DON'T think that this is "solution"

Observer · Post by **Observer** » Mon May 12, 2003 12:43 pm

Well......

So, could anyone tell me the "real solution" to that problem?

I really wanna know...................................

Btw, what does the formula given on that website mean?

Observer · Post by **Observer** » Thu May 29, 2003 6:20 am

Hello, is anybody here??!!!!

Dmytro Chernysh · Post by **Dmytro Chernysh** » Fri May 30, 2003 3:32 am

I have bad felling that everyone cheated

I guess only a few people know how to solve the problem, not just the copied answer.

Observer · Post by **Observer** » Fri Jun 13, 2003 5:34 am

Let's hope that's not true......

Amir Aavani · Post by **Amir Aavani** » Tue Oct 07, 2003 7:42 am

hi everyone

i think i find a way to count the number of different answer, but i dont try to implement it uptonow

my idea is this:

for any acceptable answer generate a sequence of number and then count the no of this sequence.
the sequence must be unique for every answer (i mean that no two answer should generate the same sequence) and every sequence must generate a valid answer.

the way that i use to generate the sequence is this:
i consider all the gate with length of 1 which has no parallel gate to be +1 and all the other to be -length (gate), except the case there exists two or more parallel gate with length = 1, in this case one of the gate will be shown by 1 and the other(s) will be shown by -1.also if there are multiple minus gate, i use -1(2), which means that two gates in backward direction exist.

to clearify i try write the sequence for example in the problem 10253, for n= 4:

1 1 1 1
1 -1(3)
1 1 1 -1(1)
1 1 -2 (2)
1 1 -2(1) 1
1 -1(1) 1 -2(1) is it correct
1 1 -1 (2)
1 1 1 -3(1)
1 -1(1) 1 -1(1)
1 1 -1 -1

i hope this idea works.
i think it is easy to avoid the repeated answer by checking their sequence

Whinii F. · Post by **Whinii F.** » Wed Oct 29, 2003 5:55 pm

I suffered from stupid mistakes I made in solving this problem and I just got AC.

You can tackle this problem with dynamic programming. You should focus on there are two types of networks: one kind which are parallel connected, and another kind which are serial connected.

You'll have enumerable number of partitioning edges among serial(parallel) connected sections (since N <= 30). The sections are independant to each other.

I posted my solution to find help when it didn't work, but deleted it because it might be a spoiler.

Hope this could be some help.

ps. Guess what? This is my 700th problem!

cytmike · Post by **cytmike** » Mon Apr 26, 2004 1:28 pm

oh, what are the details of this DyP solution?
can anybody tell me?

thx very much!!!

OJ Board

10253 - Series-Parallel Networks

10253 - Series-Parallel Networks

How???

Where!

Hm

Well...