10839 - The Curse of Barbosa

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
Programmer
New poster
Posts: 9
Joined: Sun Mar 13, 2005 11:41 am

10839 - The Curse of Barbosa

Post by Programmer » Wed Mar 23, 2005 9:16 pm

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.

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

Re: how to solve 10839?

Post by misof » Wed Mar 23, 2005 10:14 pm

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?

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

Post by mf » Wed Mar 23, 2005 10:35 pm

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.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Thu Mar 24, 2005 12:36 am

i don't quite understand what both of u are saying.:oops: can somebody kindly explain a bit more?
Impossible is Nothing.

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

Post by misof » Thu Mar 24, 2005 12:53 am

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 :P

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.

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Tue Mar 29, 2005 2:09 am

thx. got AC
Impossible is Nothing.

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Thu Dec 15, 2005 7:24 pm

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

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Fri Dec 16, 2005 3:52 pm

minskcity wrote:Could anybody who got AC verify my output?
My AC gives the same output.

Post Reply

Return to “Volume 108 (10800-10899)”