2081 - Saving Money

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

2081 - Saving Money

Post by ymondelo20 » 8 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
Dariel
Posts: 51
Joined: 9 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Why TLE in this problem?

Post by Dariel » 8 years ago

I do not understand, because this problem gives me TLE, when the solution is trivial. This is my solution, what is wrong?
Last edited by Dariel on Thu Jan 17, 2013 7:48 pm, edited 1 time in total.

User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 2081 - Saving Money

Post by ymondelo20 » 8 years ago

Very Slow Solution :D
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
Dariel
Posts: 51
Joined: 9 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 2081 - Saving Money

Post by Dariel » 8 years ago

Okay, the solution is slow but it is correct, the same code and I accept the online judge ... Greetings.
ymondelo20 wrote:Very Slow Solution :D

User avatar
ymondelo20
Posts: 1968
Joined: 9 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 2081 - Saving Money

Post by ymondelo20 » 8 years ago

Warshall Algorithm for Shortest Path is O(N^3), with N = 100, and the number of tests cases T = 100, then the total compelxity for your solution (http://coj.uci.cu/24h/submission.xhtml?id=351355) is O(10^8) ---> Very Slow for 1000 MS... but in 5000 MS should be ACC... (by the way, in codeforces 2000 MS is enough for any solution with complexity O(10^8), an interesting curiosity for those competing in this site).
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

Post Reply

Return to “Problem set”