11198 - Dancing Digits

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

11198 - Dancing Digits

Post by mmonish » Tue Apr 03, 2007 11:55 am

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.
Last edited by mmonish on Sat Apr 07, 2007 9:18 am, edited 1 time in total.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Apr 03, 2007 8:16 pm

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.
Self judging is the best judging!

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Dancing Digits(TLE)

Post by mmonish » Fri Apr 06, 2007 12:15 pm

>> shanto86

Thanks for u'r reply.

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Fri Apr 06, 2007 1:37 pm

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.
Ami ekhono shopno dekhi...
HomePage

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST

Dancing Digits(TLE)

Post by mmonish » Sat Apr 07, 2007 9:22 am

>> Jan

Thanks

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

PVM
New poster
Posts: 7
Joined: Mon Apr 09, 2007 7:40 am
Contact:

how you can use BFS?

Post by PVM » Mon Apr 09, 2007 7:43 am

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
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Re: how you can use BFS?

Post by sclo » Tue Apr 10, 2007 8:04 am

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.

PVM
New poster
Posts: 7
Joined: Mon Apr 09, 2007 7:40 am
Contact:

Re: how you can use BFS?

Post by PVM » Tue Apr 10, 2007 9:25 am

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??

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: how you can use BFS?

Post by helloneo » Tue Apr 10, 2007 9:42 am

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..

luishhh
New poster
Posts: 26
Joined: Mon Oct 25, 2004 8:11 pm
Location: Spain

Post by luishhh » Sun Apr 15, 2007 11:49 am

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?)
"From lost to the river" --> Spanish quote

free
New poster
Posts: 6
Joined: Fri Aug 13, 2010 8:35 am
Location: China

I can't understand the problem

Post by free » Sun Oct 03, 2010 7:25 am

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
New poster
Posts: 3
Joined: Sun Dec 08, 2013 1:13 pm

Re: 11198 - Dancing Digits

Post by sunshine12 » Sun Dec 08, 2013 1:22 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11198 - Dancing Digits

Post by brianfry713 » Wed Dec 11, 2013 12:07 am

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
Check input and AC output for thousands of problems on uDebug!

sunshine12
New poster
Posts: 3
Joined: Sun Dec 08, 2013 1:13 pm

Re: 11198 - Dancing Digits

Post by sunshine12 » Thu Dec 19, 2013 12:18 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11198 - Dancing Digits

Post by brianfry713 » Thu Dec 19, 2013 1:39 am

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
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 111 (11100-11199)”