Yesterday I was investigating about 1255C - League of Leesins. I got several TLE during the contest. But so far I have found no obvious reason. Here is the link to my submission- 65499234. Now I will be explaining my code.
For every number I counted how many times they are in a triplet. I stored it in vis array.
I made a vector of triplets. For each number I stored the triplets it is in. For example v[a].push_back({a,b,c}) means the number a shares a triplet with b and c.
By observation we can see that the first element will always have total occurrence of 1. So I did a loop to find out that element. And again by observation we can see that the second element will always occur twice and it will always be in the triplet with the first element. And the other element with the first element will be the third element. So basically I got the first 3 elements from the loop and stored them in the ans vector.
I made an array called mis. Which will be saying to me if an element was already pushed in the ans array or not. If the value of mis is 1 for any element then we can say that it was already used somewhere else and we won't use it. I started a loop from 2 to n-1. Obviously my array was 0 based.
By observation we can see that one element can be connected to at most 3 triplets. So the highest size of ww variable is going to be 3. And each triplet will have 3 elements. So in the worst case we are going to do 3*3 or 9 operations and traverse from 2 to n-1. So the time complexity of it should be around O(n).
In the loop from 0 to ww I checked if there exists a triplet which has exactly 2 elements in common with ans[cur] and ans[cur-1] and the third element was not already chosen. If we can find such a triplet then we will increment cur variable, push the number to ans and mark it as visited on the mis array and break the loop. At last I just traversed from 0 to n-1 and printed the ans vector.
I tried similar code with for loop and got TLE. I don't understand the exact reason. I am extremely sorry for my poor English. Help me if you can.
