I am not breaking ties. I didn’t go in that direction. The answer would be of n+m-1 length. So lets say my current node (i,j) is in the answer, so this will be at position i+j. Now I need to get the i+j+1 char. So let us assume both it’s children are equal and there exists a path from both it’s children to (n-1,m-1). So The only thing I am storing is this next_char(after position i+j , when current char is c) = d where d is the min_char_among_it’s_valid_children. So a tie would not occur in this I guess. Please correct me if I am wrong.
Yeah, I’m realizing that I way overcomplicated the problem. Ignore what I said
Please let me know if you find my mistake. I am banging my head since 2 hours. Thanks for looking at it though.
Thanks a lot bro. Thank you so much.
F*** me and F***
r=x[0][0].c-‘a’;
PS: It did not work after this too.
If you thought par = parent, it is not. It is actually child. So you are saying is kind of top down while I did kind of bottom up. For a node (i,j) I am only finding next character if this is in the answer. So for the testcase you mentioned, when I will be at a, I will two options of a and b, so their min will be a and I will proceed with aaz only right after the 1st char.
Yes, I realized that.
When will the rating be updated?
I am not sure if I am correct but lets say in the below graph, ‘a’ is the source and ‘z’ is the destination, and d1 = d2 = ‘d’, since you are storing parents for (level, character) pairs, I think your code would output ‘abdxz’.
Yeah I think you are correct. Both d’s are on the same level so their next min would be x whereas it should be y. Understood the mistake. Thank you so much bro _/_ .
@sarthakmanna Hey, great contest but I wanted to ask you something. Why were the time limits so tight? A mere change from map to unordered_map converted TLE to AC. This feels unfair as the core logic was right.
TLE: CodeChef: Practical coding for everyone
AC: CodeChef: Practical coding for everyone
only diff is unordered_map
Nice contest, had a lot of fun solving the questions. If only website wasn’t half dead I would have had 1 less WA(I resubmitted same solution because first time I clicked on submit, it gave an error, but it actually recorded the response)
Overall, great contest.
Updated.
I think the constraints in both problem C and D were really tight. It was as if you have to write a completely optimized code with fast i/o and not writing any line of code extra. Was there any specific reason for such extreme constraints. O(S+Q) solution was also giving TLE in problem C if one didn’t write it very optimally. The problems were interesting no doubt but I really disliked the idea of having such tight constraints. P.S: this is just a personal opinion.
Hey @priyansh19077 , I was the author of both the problems.
I agree TL of CLBRKT was tight. It was intentional because we tried to prevent O(N log N) solutions from passing(still some passed). Initially, the TL was set to 1 sec but later it was modified to 1.5 secs, just to be lenient and many solutions with the standard cin
, cout
along with ios_base::sync_with_stdio(false);cin.tie(NULL);
passes within TL.
Coming to CLLEXO, the TL was not at all strict. The intended solution was O(N*M) but still O(N * M * log(N + M)) solution passes comfortably in 0.8 secs. So I don’t see any point of complain in this one. Many where getting TLE because their implementation was incorrect(e.g. not using visited array).
Anyways, glad you liked the problems !
Thanks a lot for the clarification.