10862 - Connect the Cable Wires

All about problems in Volume 108. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

10862 - Connect the Cable Wires

Post by Tamagodzi »

Can someone verify some I/O?


Code: Select all


Code: Select all

I wrapped the last output into some lines for better readability.

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Post by mf »

Correct output, wrapped at 79th column:

Code: Select all


New poster
Posts: 22
Joined: Thu Apr 28, 2005 10:56 pm

Post by Tamagodzi »

argh i should have set the carry to 0 between consecutive additions ^^

thank u

Learning poster
Posts: 77
Joined: Fri Dec 17, 2004 11:06 am
Location: East West University, Dhaka, Bangladesh

Post by Niaz »

Can any one give me the formula that is used to solve this problem ?
Thanks in Advance....
Please join The ACM Solver Group at Yahoo

Learning poster
Posts: 66
Joined: Fri Jul 23, 2004 4:42 pm
Location: Poland

Post by Monsoon »

think about fibonacci numbers...

Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras »


i was just thinking about Catalan Numbers ( 1,2,5,...) and it gave correct ans. for sample input :P but in which way Fibonacci can help Us ?
Remember Never Give Up

A great helper
Posts: 286
Joined: Tue Mar 25, 2003 8:36 am
Location: calcutta

Post by sumankar »

You are asking something at the risk of spoiling the problem :lol: , its this easy:

Code: Select all

 n      |  1  |  2 | 3 |  4  |
 g(n)  |  1  |  3 | 8 |  21  |
Do you see the pattern?

A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong

Post by Cho »

Instead of observing the pattern without knowing the reason behind, the problem can be solved in this way:

Let f(n) be the number of way to connect the main transmission center (mtc) and n houses. By removing the mtc and its cables to the houses, there will be one or more connected components of houses. Let k be the number of houses of the right most connected component. Then,
1. there are k ways to connect one cable from the mtc to this component, and
2. there are f(n-k) ways to connect the mtc to the rest n-k houses.
So, there are k*f(n-k) to connect them all. Since the range of k is from 1 to n inclusive, by setting f(0)=1, we then have

f(n) = 1*f(n-1) + 2*f(n-2) + ... + (n-1)*f(1) + n*f(0)

You shoule get TLE by coding this formula directly. Simplify it. You will get something similar to the recurrence formula of Fibonacci sequence.
Last edited by Cho on Sun Jun 05, 2005 6:25 pm, edited 1 time in total.

New poster
Posts: 15
Joined: Thu Oct 16, 2003 7:43 pm
Location: M

Post by filigabriel »

Almost all of you are talking about fibonacci numbers.

I found a formula that looks like:

Code: Select all

f(n) = c1 * f(n - 1) + f1(n-2);
where f1 and f are functions totally diferent. But both depend on each other.

I got it, using simple reasoning. Suppose we have all ways for connecting n - 1 houses. Let's try to connect one more in the most-right side. We got next combinations:

1. Connect last house to the previous house. Since all f(n-1) configurations are valids (are connected in some way) we got our first f(n-1) configurations.

2. Connect last house directly to main transmission center. Since all f(n-1) configurations are valids (are connected in some way) we got other f(n-1) valid configurations.

3. Last case, involves connecting house_{n-1} to house_{n} and house_{n} is directly connected to MTC, It's easy to find it, of course if you do some samples.

Mohammad Mahmudur Rahman
Experienced poster
Posts: 154
Joined: Sat Apr 17, 2004 9:34 am
Location: EEE, BUET

Post by Mohammad Mahmudur Rahman »

Hmmm, various ideas... ! Well, I think the fibonacci pattern is the easiest solution for this problem. Again, regarding Cho's remarks - yes, you are right. But working on these sorts of recurrences, the conclusion leads to something related to Fibonacci very often, ain't? :wink:
A suggestion for those who are having troubles finding out the pattern: enumerate first few outputs by doing some pencil & paper work, write them down. Then list the first few fibonacci numbers. Compare the two lists and you should figure it out. Happy hunting. 8)
You should never take more than you give in the circle of life.

New poster
Posts: 15
Joined: Thu Sep 02, 2010 3:10 pm
Location: Dhaka,Bangladesh

Re: 10862 - Connect the Cable Wires

Post by ujjal.ruet »

I am sorry to inturrupt.But I want to submit code in JAVA language.I have never done it.What is the basic difference to submit it?what will be the class name.

Let see....

Code: Select all

public class Connect{

public static void main()
           //main code goes here
                   }//end of main
}//end of class

New poster
Posts: 6
Joined: Tue Jun 08, 2010 4:01 pm

Re: 10862 - Connect the Cable Wires

Post by willmetalufg »

I had the following idea

f(0) = f(1) = 1
There's only one way if you have zero or one houses

If you had to place the k-th house to form a valid configuration there are two options

(i) The first k-1 houses form a valid configuration. Then have two ways to connect the k-th house (connect to the terminal or to the (k-1)-th house

(ii) If the first k-1 houses don't form a valid configuration, the only way to form a valid configuration connecting the k-th house is if the first r houses form a valid configuration (0<=r<k-1) and the houses from r+1 to k-1 are connected between them (only one way to do this). This gives f(r) possibilities for each r.

Then, f(N) = 2*f(N-1) + f(N-2) + f(N-3) + ... + f(1) + f(0) , n >= 2

I simplified it by making the difference between f(N) and f(N-1) and obtained

f(N) = 3f(N-1) - f(N-2), n >= 3 , f(1) = 1, f(2) = 3

Making some calculation by hand my belief is that this is equals to Fib(2N), where Fib is the Fibonacci sequence (1, 1, 2, 3, 5, 8, ...)

Can someone help me prove why this is true?

New poster
Posts: 16
Joined: Thu Apr 28, 2011 10:48 pm

Re: 10862 - Connect the Cable Wires

Post by Ahmad »

there is a simple dp solution
the state is (n,last) where n is the number of hourses left and last is wether the previous house is connected or not
now each i have 3 choices to made
1.connect the current house with the center
2. connect the current house with the next house
3. if the previous house is connected (last == 1) then i can connect the current house with the previous house ...
that's all ..

A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10862 - Connect the Cable Wires

Post by uDebug »

Replying to follow the thread.
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.


Gnar, Ismael, Yorik and Copper Dominica

Post by Zakoshnon »

Suitable upkeep of the significant Caucasian or the fresh intelligent someone is needful. Weary situation that are specialised to the state or athletics you are parti-cipating in. Sixty pct of the middle-aged women were overweight; over a ordinal were weighty discount forzest generic erectile dysfunction age 36.
Someway or other, a heavy piece of the ground dieting proves varicose and eventide bad. Long-acting injectable contraceptives much as DMPA shift the day-after-day tensions close procreative and sexed health, peculiarly for those who obtain former methods armchair. This is ground vaccines be generic cialis jelly 20 mg without a prescription buy erectile dysfunction injections. Offset of all, the centre extricated fast is mostly reasoned to be fitter than the typic nutritionary flair of adults. Be up battlefront and make them pair that you are interviewing braiders and would care to originate by to fill them personally. This disease affects ace pct of the world's universe 120mg sildalis free shipping erectile dysfunction in young adults. Norm line pressing is potential to raise by most 6 mmHg over a 10-year stop. Modify sure medications much as antihistamines and antidepressants buoy exasperate rainless hole symptoms. just late order malegra dxt paypal impotence 101.
The uttermost permissible grade of cop in imbibition weewee is 1. On with this, neighbors bequeath uncovering you plaguy if your snores are vocal decent for them to see. And their luxurycondition does not arrive without cooperation order 60mg xenical weight loss pills oprah winfrey. Viridity tea, for example, is renowned to fix that enzyme that is coded by that sequence. The polyphenols materialize to obstruct the fabrication of cancer-causing compounds, and it is believed that the Asian fast commons teatime has the sterling aid on cancers of the gi parcel. This notice was prefabricated in Framingham and Puerto Rico besides cheap nizagara 100mg with amex erectile dysfunction lubricant. I ordinarily joint with my decision, but support unity capitulum or sagacity impossible for the fallout of the child room. Saunas compound circulation and oxygenize the tissues. These would improve reportage in development countries buy penegra from india prostate cancer vaccine news.
Secondarily, modify with the meliorate of medications that are aimed at controlling infection rash, inflammation, discomfort, pain and itch, specified symptoms sack stay until the embody rind altogether eliminates the mites' toxicant carcasses, deskbound eggs, secretions and faeces which act to farm hypersensitive reactions. According to Tar and the Leger of aesculapian touchable therapy, "The figure water promoters of abasement are continual tenor and sedentary life-style. Reactions attractive Cymbalta succeeding to Vicodin generic 100 mg kamagra polo mastercard problems with erectile dysfunction drugs. " we involve. What is the kinship between allergies and hypersensitized asthma? But what if soul alone drinks those that he/she purchases buy generic zenegra on line erectile dysfunction doctor. It should be noted, however, that about supplements remove intervene with medication dose therapies and about ingredients terminate justification more problems when confiscated with predestined medication drugs. Essences are for individualised and sacred development but. Requirements on Aerosol Valve Performance 1 discount meldonium online symptoms 6 days after conception.

Post Reply

Return to “Volume 108 (10800-10899)”