10839 - The Curse of Barbosa

Moderator: Board moderators

Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

10839 - The Curse of Barbosa

Somebody can give hint how to solve this problem.I think it must be solved using DP or ?(I see that people are using too much memory).

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm

Re: how to solve 10839?

Programmer wrote:Somebody can give hint how to solve this problem.I think it must be solved using DP or ?(I see that people are using too much memory).
My solution uses DP + large arithmetics.

Hints: Consider a graph on 3 vertices, each pair connected by N edges. You want to calculate the number of "differently-labeled" Eulerian tours on this graph (starting in the vertex 1). This can be done using DP -- or even better, using memoization.

The second step is to get rid of the symmetry. There are lots of pairs of non-symmetrical tours (one is the reverse of the other), so basically we need to divide the number of tours by two. But sometimes there are also symmetrical tours, e.g. 1-2-3-1-3-2-1. When does this case occur? How many such paths are there? How to count these?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
Well, you don't need any graph-theoretic result to solve this problem.

My solution was to count the number of different sequences composed from numbers { 1, 2, 3 }, satisfying given restrictions. It's fairly easy with memoization.

To get rid of symmetrical sequences I also counted them separatedly, just like misof did.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
i don't quite understand what both of u are saying. can somebody kindly explain a bit more?
Impossible is Nothing.

misof
A great helper
Posts: 430
Joined: Wed Jun 09, 2004 1:31 pm
mf wrote:Well, you don't need any graph-theoretic result to solve this problem.

My solution was to count the number of different sequences composed from numbers { 1, 2, 3 }, satisfying given restrictions. It's fairly easy with memoization.
Well, I'm not really using any graph-theoretical results. It's just that by drawing the graph I got the idea on how to do the dynamic programming

But okay, let's forget the graph

Suppose you want to count all sequences. Write a recursive algorithm that enumerates them. At any given moment you have an unfinished sequence. The count of all sequences that can be generated from this unfinished sequence depends only on:
- what is the last number in the already generated part
- how many 1s, 2s and 3s are left
Thus you may use memoization to avoid doing the same work multiple times.

cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:
thx. got AC
Impossible is Nothing.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver
Could anybody who got AC verify my output?
input:

Code: Select all

``````7
1
10
16
19
94
97
100``````
output:

Code: Select all

``````Case 1: 1
Case 2: 22
Case 3: 866
Case 4: 5834
Case 5: 43720821034205638558914304
Case 6: 338911165392799895449278012
Case 7: 2629674531242561989651362458
``````

Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
minskcity wrote:Could anybody who got AC verify my output?
My AC gives the same output.