10839 - The Curse of Barbosa

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

[misof]

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]

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]

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

[misof]

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.

[cytmike]

thx. got AC

[minskcity]

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]

Could anybody who got AC verify my output?

My AC gives the same output.