jigsaw7's blog

What is the closet thing you've done in a real project that resembles competitive programming?
By jigsaw7, history, 5 years ago, In English

I believe that doing competitive programming helps you become a better software engineer. It would be interesting to hear from the community a problem in a real project that has the same flavor as competitive programming problems.

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

Comments Comments (9)
| Write comment?
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

In last semester I had a course on Software Engineering, as a course requirement a group of 7 members had to work on a project, my group had to make an automatic timetable generating system, basically, it takes in the preference of all faculty member, and as an output gives the timetable for all batches.

So I came up with an algorithm to serve this purpose, the algorithm is not very complex but it was the closest thing I did, which resembled competitive programming by far.

Project Link

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    You think anyone would like to go through your 1284 lines of code to actually know what is it really doing

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      No, please don't bother looking it's only for curious minds.

      → Reply
»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Working on a personal project right now that doesn't seem too difficult on the surface, but I'm now stuck on how to build a data structure.
Here's the problem:
I have a bunch of events with start and end times. I need to find a way to store these events so I can make a query( L, R ) so that the query function returns a list of events one at a time, with end times > L and start times < R, sorted in ascending order of end times.

→ Reply
»
5 years ago, # |
  Vote: I like it +32 Vote: I do not like it

Changing rows to columns in a matrix

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've made a little "game" (it's actually very boring to play for now) on C's SDL2 Library. I've had to code circunference to line collisions with speed vector bounce for this game and if it wasn't for the computational geometry that I've learnt in competitive programming, I would never have been able to do it.

Take a look at the code in question the relevant bit is the last routine at the very bottom of the page.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  1. Fenwick tree (with Binary search on prefix sums) for random selection of actions by probabilities which can increase/decrease over time.
  2. Investigation of string matching algorithms for dynamic fragment replacement in cached documents.
  3. Generating unique codes based on user input prefix + number (eg. CODE1, CODE2, ...) in log N (instead of N) attempts.

I think noticing the opportunity to utilize algorithmic techniques is more important than knowing the techniques themselves.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Re 1, if the sum of probabilities is always 1, wouldn't making updates to the Alias table[1] be faster? It is critical to one of the programs I'm writing, so trying to somehow get rid of the if condition with little luck.

    * check out [2] for a more detailed explanation.
    ---
    [1]: https://en.wikipedia.org/wiki/Alias_method
    [2]: http://www.keithschwarz.com/darts-dice-coins/

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Well, probabilities was very inexact term to use, perhaps I should say priorities. Those are integer numbers that add up to some sum S. I then generate a random number between 0 and S, and select one of the actions with probabilities proportional to their priorities. Key thing is that priorities / probabilities are frequently changing. I have looked at your links only briefly, do these methods support the updates efficiently (at most log n)?

      → Reply