Ahmad's blog

By Ahmad, history, 18 months ago, In English,

As far as I know, to view solutions and test data to problems in the Gym, you need to be able to enable coach mode (the requirements are being Div.1 and having some number of contests).

However if you clone the contest to a mashup then any submission made (and all tests that ran on that submission) in the mashup can be viewed by the contest manager (which defaults to the user). It doesn't seem to work for viewing the submissions of others that haven't participated in the mashup so it's not exactly like coach mode but it's better than nothing I guess.

Read more »

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

By Ahmad, history, 3 years ago, In English,

I recently solved 219C - Color Stripe (Submission) and I can't seem to get it to run in under a second in Java.

I've looked through faster Java submissions and still have no idea why mine takes a second to a second and a half longer than theirs. Is there something obvious that I'm missing?

Read more »

 
 
 
 
  • Vote: I like it
  • -5
  • Vote: I do not like it

By Ahmad, history, 3 years ago, In English,

Let's say you're given a string where the start point is the beginning of the string and the end point is the end of the string. For each turn, you can jump at most s positions in the string but there are obstacles in the string which you are not allowed to land on.

So for example a string like "SOOOXOE" (where "O" represents a free space and "X" represents an obstacle) and there's an s value of 3. The minimum number of moves in this case to get from S to E is 2. But in a case like "SOOOXXOE" with the same s value, the minimum number of moves is 3.

I came up with a greedy where you jump as far as possible as long as it's valid position each turn and it works. But I need to calculate the minimum number where the difference between S and E is at most 1,000,000,000 so simulating the jumping is too slow. Does anyone have any ideas about how to solve this efficiently?

*Note that I'm not actually given a string of length 1,000,000,000 but I visualized it as a string so it's easier to understand. Also if it helps, there will be at most 40 obstacles per string and s is always greater than 1 and less than or equal to 6. It is always possible to reach E from S.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By Ahmad, history, 3 years ago, In English,

Hello, relatively new to dynamic programming but I feel it's necessary for me to begin learning it well.

As far as I know, DP depends on storing the solution to previously solved subproblems and reusing them. But in this problem, I do not clearly see how that principle helps to solve this problem. I can only think of a naïve brute force where I try each pair of numbers that sum to s and count them like that.

Could anyone give me a hint as to how to approach thinking about this problem as well as other dynamic programming problems. Thanks in advance for any help.

Edit: I also want to try and avoid the editorial since it usually gives the solution away for me. Just a hint would be appreciated.

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it