cgy4ever's blog

By cgy4ever, history, 2 years ago, In English,

If you haven't advance to Round 2 yet — don't miss the last opportunity.

Round 1C will start at 12:00 noon EDT Saturday, May 6, 2017

You need to get top 750 with a positive score to advance. Note that if you have already advanced (in 1A, 1B or received a bye), then you can't participate.

Find rules this year with the schedule here: https://tco17.topcoder.com/algorithm/rules/

 
 
 
 
  • Vote: I like it
  • +20
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This round has sixth Data Science Weekly Challenge associated with it: the person whose score after System Testing is the closest to the average of all the scores in Round 1C will get a TCO'17 t-shirt!

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Where can one find editorial for 1000 problem?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

So I bungled the 500 point problem because after translating it to a shortest path problem in a graph with negative cycles, I didn't realize that the data was setup such that every cycle has zero length and the intermediate steps in any path are irrelevant. (Not sure I've ever seen a TC problem where one parameter could be completely ignored...).

Anyway, this got me to thinking of the more general problem. Suppose there was no special rule for calculating the value of a word and you are given the cost of each trade. So instead of the market array giving just "L R" is will have a set of "L R C" where C is a cost that can be positive or negative. And you can only execute each trade once, just like the problem.

Put another way, you have a digraph with negative edges and possibly negative cycles, the special rule that each edge can be used at most once, then what would be the best way to calculate the shortest path? I think Dijkstra is out just because it's greedy, but wouldn't Floyd-Warshall still work? Because we're not concerned about getting infinite profit by taking a cycle repeatedly, we can take each cycle just once.