How to solve spoj's CLEVER ?
( Problem statement given below )
CLEVER — The Clever Typist no tags Time limit: 1s Source limit: 50000B Memory limit: 1536MB Blue Mary is a typist of some secret department.Now she has to type in many passwords in an hour,each of which has a fixed length: 6.Of course,the less times she presses the keyboard,the happier she is. Unfortunately,the keyboard to type in the password is extraordinary designed to keep secrets.The keyboard has 6 particular keys instead of 10 number keys.To explain the usages of these keys,let's define the 6 position on the screen 1,2,3,4,5,6 from left to right.The keys' usages are shown below: Swap0: swap the digit in the cursor position and the digit in position 1.The cursor doesn't move.If the cursor is now in position 1,the digits on the screen won't be changed. Swap1: swap the digit in the cursor position and the digit in position 6.The cursor doesn't move.If the cursor is now in position 6,the digits on the screen won't be changed. Up: increase the digit in the cursor position by 1.If the digit in the cursor position is 9,no change will happen. Down: decrease the digit in the cursor position by 1.If the digit in the cursor position is 0,no change will happen. Left: move the cursor one position left.If the cursor is in position 1,no change will happen. Right: move the cursor one position right.If the cursor is in position 6,no change will happen. At start,6 random digits will be given on the screen,and the cursor will in position 1.After some smart presses,she can type in the correct password,at that time the cursor position is unimportant. Here is an example("()"denotes to the cursor): key pressed screen (1)23456 Swap1 (6)23451 Right 6(2)3451 Swap0 2(6)3451 Down 2(5)3451 Right 25(3)451 Up 25(4)451 Right 254(4)51 Down 254(3)51 Right 2543(5)1 Up 2543(6)1 Swap0 6543(2)1 Now Mary wants to know the minimal number of keys she has to press.Can you help her? Input The first line contains a single integer t(about 1000).t lines follow,each contains two 6-digit string,which show the digits on the screen at start and the password Mary is to type in,separated by a single space. Output t lines,each contains a single integer — the answer. Example Sample input: 1 123456 654321 Sample output: 11
Dude There is no need of pasting statement,if u already wrote link!!
I thought that it'd be helpful if I did :/
Looks like standard BFS.
Let DP[X][V], be the shortest distance to the situation where your cursor is at x (0 to 5), and the number of the screen is v (0 to 1e6 — 1). Then just put pairs {x, v} into the queue, and stop when you reach the wanted state.
If that TLE's you can try BFS from both ends.
EDIT: I missed that there are multiple queries
what is reason behind ur cf handle name.u deosn't seem indian
@mango_lassi, none of them passed TL actually. My implementation might be an issue, though. But I tried to do as much as I could. My code for bfs from both ends: here.
I missed that the problem has queries, sorry.
That said, I think I have a solution now.
For every permutation, precalculate the minimum number of steps to swap the numbers around such that if the numbers first were in sorted order, they'd be in the permutation's order afterwards.
Additionally, you need to store whether you have at least once been in the same node as the last element, and where the cursor ends up in, for reasons explained later.
You can do the precalculation with BFS from the initial state.
Now when we have this information, we can for every query, go over all 720 permutations, find out how much we need to add to or subtract from every integer, and take the best of these offers.
Of course, you still need to make sure that you have at least once been in the same tile as each number you will change. You can make sure that this has happened, by the "visit last" bit being set if the last number needs to be modified, and cursor position being greater than or equal to index i if index i needs to be modified.
This way the time use should be something like 720*6*2 + 1000*720*6 = ~4e6
I'm writing the code now, results soon.
EDIT: turns out you can't just store the position of the cursor, you need to store the highest position the cursor has ever been in.
AC code
Would you please explain why I need to store the max cursor position? I am not very clear on that. :/
EDIT: Understood. Thanks a ton!