10839  The Curse of Barbosa
Moderator: Board moderators

 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).
Some hint please.
Some hint please.
Re: how to solve 10839?
My solution uses DP + large arithmetics.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).
Some hint please.
Hints: Consider a graph on 3 vertices, each pair connected by N edges. You want to calculate the number of "differentlylabeled" 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 nonsymmetrical 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. 1231321. When does this case occur? How many such paths are there? How to count these?
Well, you don't need any graphtheoretic 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.
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.
Well, I'm not really using any graphtheoretical results. It's just that by drawing the graph I got the idea on how to do the dynamic programmingmf wrote:Well, you don't need any graphtheoretic 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.
But okay, let's forget the graph
POSSIBLE SPOILER ALERT.
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.
Could anybody who got AC verify my output?
input:output:
input:
Code: Select all
7
1
10
16
19
94
97
100
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)