linkret's blog

By linkret, history, 5 weeks ago, In English

While checking out other people's submissions (too see what the simplest/shortest way to implement a problem is), I noticed that many of the last 10 submissions were... exactly the same. It's all just copy-pasted from one person.

https://codeforces.com/contest/1569/status/E

My question is, why would anybody do this? The contest is over. And by copy-pasting another person's solution and submitting it, you learn exactly nothing. Isn't it just a waste of time?

Can anybody explain this to me, am I missing something obvious? I can't think of any reason why anybody would do this.

Read more »

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

By linkret, history, 5 years ago, In English

The task I want to discuss is 739E - Gosha is hunting. While the official solution is a greedy algorithm sped up enough to pass the time limit, I recently came upon another solution. The main idea is to speed up the obvious dp approach, where we define dp[i][x][y] as the maximum expected number of caught pokemon in the prefix of first i pokemon, if we throw at most x A-pokeballs and at most y B-pokeballs. The computation of each state is O(1), so the complexity of this solution is O(n^3).

Read more »

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