11198 - Dancing Digits

[mmonish]

I use BFS for this problem but i am getting tle. I check some random test cases in which my program passed. I don't get any faster idea.

Code: Select all

//remove after AC

Can anyone please tell me how can i optimize my code.

[shanto86]

well ur code is very lengthy. i also did BFS and got AC during the contest time. (though got 3TLEs then).

what i did was, keeping a map and always using decimal operation.

[mmonish]

>> shanto86

Thanks for u'r reply.

now i recode it but i am getting WA. can anyone give me some test cases

[Jan]

Try the cases...

Input:

Code: Select all

6 -4 -8 7 -1 3 -5 -2
-4 -8 2 5 -1 -6 7 -3
6 8 5 2 -1 7 4 -3
4 7 8 5 1 -6 -3 2
-5 8 -2 6 1 -7 4 3
5 -6 -3 -8 2 -1 7 -4
-6 -7 5 -1 2 4 -3 8
5 4 -8 -3 -2 -7 -6 1
5 -2 -4 -6 3 -8 -1 7
5 -4 7 -2 -1 -6 -3 -8
-1 7 -8 3 -4 6 -5 -2
-8 2 7 5 -6 -4 1 3
-2 6 -8 -7 -1 -5 3 -4
0

Output:

Code: Select all

Case 1: 11
Case 2: 8
Case 3: 8
Case 4: 10
Case 5: 8
Case 6: 8
Case 7: 8
Case 8: 8
Case 9: 8
Case 10: 8
Case 11: 10
Case 12: 8
Case 13: 9

Hope these help.

[mmonish]

>> Jan

Thanks

At last i found my bugs and get accepted. I use hashing to check the unique states.

[PVM]

Hi I have been in acm site for 1 week. so i am pretty novice.
i cannot understand the fact how you can use BFS or a Graph for instance in this problem? can anyone explain in brief? :D

[sclo]

Hi I have been in acm site for 1 week. so i am pretty novice.
i cannot understand the fact how you can use BFS or a Graph for instance in this problem? can anyone explain in brief?

Problems 11195-11199 are not that easy. Sometimes, it is better to solve other problems first.
Here, it is not hard to see what the states are and how to go from one state to another state.

[PVM]

Here, it is not hard to see what the states are and how to go from one state to another state.

.. still i dont understand why it is meant by state. i tried to use insertion sort algorithm, but got WA. can you explain a bit more how I can use graph??

[helloneo]

.. still i dont understand why it is meant by state. i tried to use insertion sort algorithm, but got WA. can you explain a bit more how I can use graph??

Let every permutation of the sequence be a vertex.. if a sequece can become another sequence with one operation, then it has an edge..

[luishhh]

Hi! Can anybody tell me what is the expected execution time for an AC solution in the cases kindly given above? (about half of the total time for the complete input in the judge?)

[free]

hi, i read the problem, but i can't understand what it mean.

could anyone explain the sample input and the sample out to me ?

thanks in advance.

[sunshine12]

any one can explain me how i need to solve this problem.. i totally dont understand how i need to solve it.. i tried insertion sort on it.. but got WA. and how i can use BFS on it... any one care to explain me.. thanks in advance

[brianfry713]

This is from a contest of brute force. You insert the starting position into a queue. For each position at the front of the queue, insert every possible unvisited move into the back of the queue.

For the first sample input, you can solve it in one move by -3 moving to 4's left.
The second is already solved.
The third can be solved by -4 moving to 5's left.
The fourth has no female digits so no moves are possible.
The fifth can be solved by
2 -8 -4 5 6 7 3 -1
-1 moving to 2's left
-1 2 -8 -4 5 6 7 3
-8 moving to 3's left
-1 2 -4 5 6 7 -8 3
3 moving to -4's left
-1 2 3 -4 5 6 7 -8

From the position 2 -8 -4 5 6 7 3 -1, here are all of the possible positions reachable in one move:
-1 2 -8 -4 5 6 7 3
2 -1 -8 -4 5 6 7 3
2 5 -8 -4 6 7 3 -1
2 -8 5 -4 6 7 3 -1
2 3 -8 -4 5 6 7 -1
2 -8 3 -4 5 6 7 -1
2 -8 7 -4 5 6 3 -1
2 -8 -4 7 5 6 3 -1
2 -8 -4 3 5 6 7 -1
2 -4 -8 5 6 7 3 -1
2 -4 5 -8 6 7 3 -1
2 -8 -4 5 -1 6 7 3
2 -8 -4 5 6 -1 7 3
2 -8 5 6 -4 7 3 -1
2 -8 5 6 7 -4 3 -1
2 -4 5 6 7 -8 3 -1
2 -4 5 6 7 3 -8 -1
2 -8 5 6 7 3 -4 -1
-8 -4 5 6 7 3 2 -1
-8 -4 5 6 7 3 -1 2
2 -8 -4 5 7 3 6 -1
2 -8 -4 5 7 3 -1 6

[sunshine12]

i dont understand how can i keep track of the point of the last visited... and i tried queue.. i tried to place the digit that was not in sorted form in the queue. than i searched where the index is value is..and than replaced it if the sum is prime..
i also tried to solve it via permutation. i got the unique permutation of 2 pairs i.e. keeping in mind that the sum should be a prime.
but still the code was WA. for some of the input given above.. my code works but for some it does not..

[brianfry713]

I used a set to keep track of states visited.

I use a queue for the BFS. Every reachable unvisited state from the current state is marked as visited and pushed onto the back of the queue. Note the explanation I posted for all the reachable states starting from 2 -8 -4 5 6 7 3 -1