Link : https://cses.fi/problemset/task/1670 is it a wise idea to think of recursion by making a function with 9 parameters there will be only two types: at the correct position, not correct position. Sometimes we will lock the numbers which will be at correct positions sometimes we will not and move it from correct to incorrect. so how to compute this problem

Auto comment: topic has been updated by codeprokeshav (previous revision, new revision, compare).There could be $$$9!$$$ such permutations. So you don't need to make a function with $$$9$$$ parameters, just storing the index of the permutations would be enough. And then just perform a straightforward dynamic programming.

Oh, you can also solve it using BFS.

Sir I don't think 9! or dp approach will work because you can have base condition but what algorithm you will have below base condition. Sir can you please elaborate BFS approach Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem

Yeah, you are right. Dp won't work.

So just use BFS as spookywooky said. But you don't need to use string, instead, you can use the index of the permutations which will be faster as in that case you won't need to use map, but a simple array would suffice.

right right we can just use max variable no need to use map it will decrease time complexity but how usage of index will reduce time

I did a brute force by bfs. The state of the board can be stored as a string, ie start with "123456789". Then there are 12 different swaps possible. So just store every possible state in a map with the number of swaps needed to reach that state. My code needs 0.9 sec to calculate all possible states, which gives AC.

looks good doing it but Sir what I am feeling is that there is a small trick which can lead to a very simple and intuitive solution of this problem

Your approach is fabulous. Can you share your implementation?

Note that this is not very efficient. However, it looks like this:

CodeThanks for this but I already wrote my own. However, I'm getting TLE

How should I optimize?

Easiest optimization is to BFS from both ends.

Can you elaborate more?

Essentially the answer isn't very large (I believe up to 16 for largest cases), so instead of doing a full BFS up to distance 16, only do a BFS up to distance 8 from both the starting grid and the final grid, and iterate over the "meetup grid".

If we imagine BFS as a tree, the number of edges between depths increases roughly exponentially, so BFS'ing to only half of the depth is going to significantly reduce the amount of edges we check.

Here's my submission that got 0.57 s on CSES. It's pretty basic with minimal optimization, so you can probably get it even faster.

https://cses.fi/paste/5b823493d891d75d12d603/

EDIT: Apparently there's a name for this: https://en.wikipedia.org/wiki/Bidirectional_search

If for an arrangement that is (let's say 9 units from the start) and 7 units away from the goal. Ig the approach you mentioned wouldn't consider this case?

Yes, but that's ok, because there exists an arrangement that's distance 8 from the start and goal, so we'll use that instead.

So is there any certainty that this arrangement will definitely exist

By DefinitionEDIT: Image doesn't want to load so direct link: https://www.imageupload.net/image/bIGfa

I made one which uses an array instead of hashmap for the dp values, which speed things up.

https://cses.fi/paste/e40a153a2154cdee13d897/