11813 - Shopping

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

Moderator: Board moderators

Post Reply
Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

11813 - Shopping

Post by Imti »

I tried this with BFS+Bit-masking.But getting TLE.Same result for Dijkstra+bit-masking too.
whats the correct approach to solve it?
Last edited by Imti on Wed Oct 12, 2011 5:47 pm, edited 2 times in total.

plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11813:Shopping

Post by plamplam »

I got AC after running Dijkstra S (S = number of shopping malls) times, and then applied n^2 * 2^n bitmasking TSP in 2.28 seconds
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11813:Shopping

Post by just_yousef »

How can I optimize my code better, Im stuck in TLE !!

Code: Select all

Removed after edit
Last edited by just_yousef on Thu Jul 10, 2014 2:06 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11813:Shopping

Post by brianfry713 »

You are allocating a lot of memory before each test case. Try making your arrays a fixed size except for the adjacency list.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11813:Shopping

Post by just_yousef »

Thank you, But now i get WA !! :( :(

Code: Select all

removed after AC :D 
Last edited by just_yousef on Thu Jul 10, 2014 11:31 pm, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11813:Shopping

Post by brianfry713 »

Try making dist and dp long long.
Check input and AC output for thousands of problems on uDebug!

just_yousef
New poster
Posts: 50
Joined: Tue Dec 17, 2013 11:01 pm

Re: 11813:Shopping

Post by just_yousef »

brianfry713 wrote:Try making dist and dp long long.
I incremented variable "s" and removed equal sign from all loop and Got AC, with all array as integers
Thanks :D

Post Reply

Return to “Volume 118 (11800-11899)”