11792 - Krochanska is Here!

All about problems in Volume 117. 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
Ronok1307
New poster
Posts: 8
Joined: Tue May 29, 2012 7:37 pm

11792 - Krochanska is Here!

Post by Ronok1307 » Tue Oct 09, 2012 3:16 pm

Could someone clarify the problem statement for me? From what I understand it is either

a) Find an important station form which the cost of visiting all other stations is minimum --(if multiple answers)--> Find the important station from which the cost of visiting all other important stations is minimum --(if multiple answers)--> Find the important station with the minimum ID number

OR

b) Find the important station from which the cost of visiting all other important stations is minimum --(if multiple answers)--> Find the important station with the minimum ID number

EDIT : Ok, I figured it out. It's B

Tawcharowsky
New poster
Posts: 2
Joined: Thu Oct 23, 2014 9:34 pm

Re: 11792 - Krochanska is Here!

Post by Tawcharowsky » Thu Oct 23, 2014 9:50 pm

Hi there,

does anyone know more efficient algorithm for solving this other than running bfs numOfImportantStations times.
While that may work in c/c++, it produces TLE in java .
I would appreciate your help.

This is my first post on this forum :)

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

Re: 11792 - Krochanska is Here!

Post by brianfry713 » Fri Oct 24, 2014 11:43 pm

It is possible to solve this problem using Java.
Try creating a graph with only the important stations and then run the Floyd-Warshall algorithm.
Check input and AC output for thousands of problems on uDebug!

Tawcharowsky
New poster
Posts: 2
Joined: Thu Oct 23, 2014 9:34 pm

Re: 11792 - Krochanska is Here!

Post by Tawcharowsky » Tue Oct 28, 2014 3:01 am

Thank you brianfry713, for you reply.
WIth your help I solved this problem using c++11 in 149ms but java just isn't fast enough.

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

Re: 11792 - Krochanska is Here!

Post by brianfry713 » Tue Oct 28, 2014 11:15 pm

Yes C++ is faster but other people have been able to get AC using Java.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 117 (11700-11799)”