sparshgunner12's blog

Codeforces Gym — ICPC Season 1 Ep 2(Those planning to give please ignore).
By sparshgunner12, 11 years ago, In English

I sat in the gym contest http://codeforces.net/gym/100228 .Well I am trying to come up with a solution for B)Decorations C)EKG Sequence with no success.Can someone please suggest the algorithm behind these two problems.Seems a lot of u(Over 100 teams) have solved it.Thanks in advance.

Tags gym
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

B:
make a graph with M vertices and there is an edge from i to j if and only if you can use bead[j] immediately after bead[i] — in other word last L-1 characters of bead[i] and first L-1 characters of bead[j] is same .
Answer is number of paths with length of L in this graph .
to find this value , use dynamic programming with this state : index of current node and remaining length of path .

→ Reply