Page 1 of 1
10839 - The Curse of Barbosa
Posted: Wed Mar 23, 2005 9:16 pm
by Programmer
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.
Re: how to solve 10839?
Posted: Wed Mar 23, 2005 10:14 pm
by misof
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.
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?
Posted: Wed Mar 23, 2005 10:35 pm
by mf
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.
Posted: Thu Mar 24, 2005 12:36 am
by cytmike
i don't quite understand what both of u are saying.
can somebody kindly explain a bit more?
Posted: Thu Mar 24, 2005 12:53 am
by misof
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
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.
Posted: Tue Mar 29, 2005 2:09 am
by cytmike
thx. got AC
Posted: Thu Dec 15, 2005 7:24 pm
by minskcity
Could anybody who got AC verify my output?
input:
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
Posted: Fri Dec 16, 2005 3:52 pm
by Martin Macko
minskcity wrote:Could anybody who got AC verify my output?
My AC gives the same output.