Блог пользователя jigsaw7

Автор jigsaw7, история, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится -11 Проголосовать: не нравится

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

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

Changing rows to columns in a matrix

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  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.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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/

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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)?