Page 1 of 2

11198 - Dancing Digits

Posted: Tue Apr 03, 2007 11:55 am
by 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.

Posted: Tue Apr 03, 2007 8:16 pm
by 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.

Dancing Digits(TLE)

Posted: Fri Apr 06, 2007 12:15 pm
by mmonish
>> shanto86

Thanks for u'r reply.

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

Posted: Fri Apr 06, 2007 1:37 pm
by 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.

Dancing Digits(TLE)

Posted: Sat Apr 07, 2007 9:22 am
by mmonish
>> Jan

Thanks

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

how you can use BFS?

Posted: Mon Apr 09, 2007 7:43 am
by 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

Re: how you can use BFS?

Posted: Tue Apr 10, 2007 8:04 am
by sclo
PVM wrote: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
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.

Re: how you can use BFS?

Posted: Tue Apr 10, 2007 9:25 am
by PVM
sclo wrote: 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??

Re: how you can use BFS?

Posted: Tue Apr 10, 2007 9:42 am
by helloneo
PVM wrote: .. 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..

Posted: Sun Apr 15, 2007 11:49 am
by 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?)

I can't understand the problem

Posted: Sun Oct 03, 2010 7:25 am
by 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.

Re: 11198 - Dancing Digits

Posted: Sun Dec 08, 2013 1:22 pm
by 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

Re: 11198 - Dancing Digits

Posted: Wed Dec 11, 2013 12:07 am
by 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

Re: 11198 - Dancing Digits

Posted: Thu Dec 19, 2013 12:18 am
by 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..

Re: 11198 - Dancing Digits

Posted: Thu Dec 19, 2013 1:39 am
by 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