I'm stuck on some problems for quite a while and no matter how much I tried I couldn't get any idea on how to solve them. It would be great if any of you can provide some directions in which I can proceed. (Not the whole solution just the idea is appreciated).

Problems:

Liar Liar :- Here's what I thought so far. Classify each person as a Liar and Truth Speaker and check if data is consistent. Can check consistency for truth person but don't know how to check consistency for a liar.(Don't know whether this is the correct approach ).

TRANSL (Tried backtracking with pruning but gives TLE so maybe approach is not correct)

EMPODIA (Can solve in O(n2), but no idea about O(n)).

Thanks in advance.