10862 - Connect the Cable Wires

[Tamagodzi]

Can someone verify some I/O?

Input:

Code: Select all

1
2
3
50
51
52
2000
0

Output:

Code: Select all

1
3
8
354224848179261915219
927372692193078999553
2427893228399975083440
3990947343500442280830546170806649238155051199615353345914772120632815708132280
4338997484524319804087232968483284519947977908567180889058580189484003876034253
8752917206164449691593778477904681437401511814273572019290757390492533940733362
3054274144004981391918824499604878074161344229694602122500604584370877633166757
9807354758409588124860967164547489849405990003864431874700055443037902915628327
8982655800052274950614793231799010416424621046909526244353710859996255889675443
9748970794774925353376797369773118982073104960083840051391410803586877610132199
9531182001057859125663441791213653284419861412777624194580852543394751034294997
7285334995641472493027192716540538330859685257615536825977709992187165356174841
1912757451100422678996883221036922626588562064271387574617216324926239249008177
3255189153517049832959704637053673425321466608

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

[mf]

Correct output, wrapped at 79th column:

Code: Select all

1
3
8
354224848179261915075
927372692193078999176
2427893228399975082453
3990947343500442279208124809496091260079257098282025785262887632652305181864137
3433549136769424132442293969306537520118273879628025443235370362250955435654171
5928979667908648144582231419142725908974684721803706396953344496626503128747355
6092629824624940416830906421435104445907774942523677766080922609515185205278135
2975449482565838369809183771787439660825140502824343131911711296392457138867486
5939235441778937354286022382122491565646314525076586034000120036853229848384889
6235149263257775535445290404924129456566251941723502004987387387860273137920789
3212335423484873469083054556329894167262818692599815209582517277965059068235543
1394593750282768512214358159573742731438244229094163953751787392685443681268942
4097913532217608037478099801065771077562585604159407849541172423656024259775918
5543824798332467919613598667003025993715274875

[Tamagodzi]

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

thank u

[Niaz]

Can any one give me the formula that is used to solve this problem ?
Thanks in Advance....
Niaz

[Monsoon]

think about fibonacci numbers...

[miras]

hey...

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

[sumankar]

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

Code: Select all

 n      |  1  |  2 | 3 |  4  |
--------------------------------------
 g(n)  |  1  |  3 | 8 |  21  |

Do you see the pattern?

[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.

[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]

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?
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.

[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

[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?

[Ahmad]

**SPOILER**
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 ..

[uDebug]

Replying to follow the thread.

[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.