Getting wrong answer in this problem

Revision en2, by mono_lith, 2022-07-31 12:27:17

recently we had a coding test in our college the question was you are given a string S and a vector of triplets which contains three things a,b,c where you can replace a character with b character at the cost of c(integer value rest a,b are character) you have to find the minimum total cost to make the string S have a palindromic substring of size >=2

s.size<=10^5

vector.size<=10^5

if you are unable to make a palindromic substring print -1 ;

eg

abcab

2

a b 3

b a 4

output -> 3

my approach ->

was to make a directed weighted graph from the given triplet vector and the we will only have 2 or 3 size palindromic substring so i brutefoce on that and for each pair of character (i,j) do a dfs on the graph and store the values in a dp still getting wa

i think this type of question i have seen on codeforces some D or E problem but I am unable to find that problem

please if anyone could help in this problem also the coding test is over so not doing this for cheating just curious about the mistake after investing so much time to solve it.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English mono_lith 2022-07-31 12:27:17 51 Tiny change: '1 ;\n\neg &mdash; > abcab\' -> '1 ;\n\neg > abcab\'
en1 English mono_lith 2022-07-31 12:22:46 1169 Initial revision (published)