Help in this problem.

Revision en3, by chinesecoder, 2019-03-10 22:53:51

The problem , 814c , my approach was , for each segment [l, r ] , check whether its possible to color it with at most m colors or not.

since there can be 26*n queries and n^2 segments , the solution will work in 26*n^3 which will give TLE .

The editorial mentions some prefix based approach but i couldn't understand the 2nd part , how its optimizing the solution .

How to reduce 26 * n ^3 to 26*n ^2 .

is there any dp solution possible to it . ?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English chinesecoder 2019-03-10 22:53:51 100
en2 English chinesecoder 2019-03-10 20:39:26 10
en1 English chinesecoder 2019-03-10 20:38:49 596 Initial revision (published)