@nisargshah95:
I tried AAAA…(5000 times) to check for stack overflow on ideone, runs perfectly fine, guess that’s not it.
@kostya_by: any thoughts? Could you provide test cases used now that the contest is over?
I have checked for all corner cases…My solution passed all test cases generated by betlista… Could somebody help me where i am missing? Or provide the test cases used for evaluation?
try:
1
CEAThis problem can also be solved with elementary knowledge of array, 1d, 2d
⮊ make two arrays p, q
pᵢ is the min-node-value of i eg pₐ = 0
qᵢ is the max-node-value of i eg qₐ = 5
⮊ make an array from[5][5] where fromᵢⱼ = node-value of the i in edge i➜ j
e.g. for A⟷B fromₐᵦ = 0
⮊ similarlry, make an array to[5][5] where toᵢⱼ = node-value of the j in edge i ➜ j
e.g. for A⟷B toₐᵦ = 1
☪ here i, j ∈ {A,B,C,D,E}
fromᵢⱼ , toᵢⱼ are always unique, except when i≣j (small manipulatⁿ to fix it, do later)
☪ assuming 0-based indexing , i.e., 1st ele in the string is at s₀
The test case can be categorize in two types:-
1️⃣ when all the letters in strings are same i.e., AAA, BBBB, C
answer : pᵢqᵢpᵢqᵢpᵢ………… (think why ? ∵ lexicographic string, see defⁿ of p, q above)
2️⃣ this case has nothing to do with lexicoraphic propt.
⮚ let say string s = 'AAAABBEECD', n = s.length = 10
⮚ assume answer be array ans[10]
⮚ we'll work on prefix 'AAAA'
⮚ since fromₐᵦ = 0, toₐᵦ = 1
⮚ ans₃ = fromₐᵦ = 0
⮚ ans₄ = toₐᵦ = 1
⮚ work reversely for getting ans₂,ans₁,ans₀
⮚this is easy task similiar to 1️⃣ , since ans₃ = 0 ∴ we have ans₂=5, ans₁=0, ans₀=5 ☪ in the problem we don't have self loops i.e., 0 ➜ 0,5 ➜ 5, not possible but 0 ➜ 5, 5 ➜ 0 is possibile
☪ prefix in this context here means the consecutive same letters at the beginnning of the string which in this particular case if 'AAAA'
⮚ now we are down with exhaustive part of the prefix
⮚ now take help of array from[][], to[][] to directly find ans₅ in similiar ways as we found ans₄
⮚ but this time do not go backward to find ans₄, ans₃,………… since we are done with them
⮚ proceed further for ans₆,... so on [similiar to ans₅ ]
#use type casting to convert ascii value 48-52 to A-E
you can see that that you can proceed in same way on any other test case , this is the more general test case , which suffice’s to explain all the possisbility
someone, please tell me why my dfs solution gives TLE .
https://www.codechef.com/viewsolution/49272630
thanks in advance.
This gives me Runtime error(NZEC) while submitting. What could be the problem?
https://www.codechef.com/viewsolution/62080022
Your solution breaks with a (valid) string of 50000 length