Good day everybody.
So yesterday I was trying to solve this problem here and now I need some help please.
So my problem is this in my soultion I got AC on the first test and RE on the rest I looked in the help section of the site and it turned out the RE might be caused by some large STL the only STL I was using was a queue so I put an if statment that if the queue size was bigger that 10000 stop putting stuff in the queue and it worked...sort of.
You see now I'm getting WA on tests 2 , 3 and 4 and AC on the rest and on tests 2 , 3 and 4 my program isn't outputing anything and that's because of the queue limit so now I'm asking you this can you tell me what is wrong with my code and how to fix it or do you have a working code for the problem or is there any site that has working C++ codes for old IOI problems.
Here's my code.
Any help is much appreciated.
thank you and sorry for the long post.
:)
Unfortunately it doesn't seem like you are caching.
Normally in a BFS you would maintain a "seen" array to make sure you don't come back to the same vertex multiple times. I don't see this in your implementation.
Please correct me if I am wrong.
I tried putting a map of < pair < vector < short > , vector < short > > , bool > but the problem that was caused by the queue will now be caused by the map because its size will be huge too.
The fact that you say that suggests you haven't solved the problem yet.
I suggest you return and evaluate the complexity properly again by finding some more observations. I advise you not to read the spoiler until you have tried to solve the problem yourself.
The number of states is small and it is bounded by 4^9. Therefore the total number of objects in the map is bounded, so a BFS can actually work in this case. The size of the map will be 262144 at most
Yeah, but I bet that because the problem is from 1994, the intended solution has smaller complexity
≈ 29 * log2(29)