robin_0's blog

My Funniest Experience

By robin_0, history, 8 years ago, In English

IPSC is back again after a year. And on the eve of IPSC I can't forget a memory I made participating in IPSC. Last year I participated in IPSC for the first time. I had just started competitive programming for a while and when I was still in a juvenile state IPSC came. So I did participated in it. This brought such a funny memory in my life I can't ever forget :v

Unfortunately I am not from CS background so I didn't know much about algorithms and complexities back then :/ (which I still don't know much about :3 ) . And this lack of knowledge gave me that experience :V .

So when I was solving the problems , the first problem was a greedy one and it was easy to solve. But when I was solving the 2nd problem , I being completely novice wrote an O(n^3) algorithm or what I can't remember properly to solve it.Now for the easy sub problem n was <=50 so it was done in the blink of an eye. Now the funny part came when it was for the hard sub problem . For the hard sub problem n was <=10000.

But being unaware of time complexities and thinking to myself "Hey it's not constrained to 1 sec so who cares. How long is it going to take at most maybe 1 minutes or 2. Still no big deal" :V

So I being confident started executing my code and thought of waiting for a minute or two.

But 3 minutes passed ... 5 minutes passed ... 10 minutes passed ... 30 minutes passed ... 1 hour passed.

Still my code wasn't done executing :3

Now the contest time was going away and I was waiting and waiting. Then I was wondering " This is why in movies we see hackers with so many computers ". On that time I was hoping to have another pc to solve other problems. And I can remember that I was so much motivated to solve I even tried to solve the easy sub problem of another problem by hand :v .

After 5 hours the contest was over but still my code was running and running :v Being completely annoyed I terminated it :v

Later I learnt my mistake but still whenever I hear something about IPSC I can't get the memory of that day out of my mind :v

I don't know in which way my life will go , in which direction my problem solving career will go. But one thing for sure I'll never forget this day :v

Thank you for reading this long post , I derived pleasure sharing this with you :)

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

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

today he solved 3 problems (was in my team) :D Great improvement

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

    Thanks mate :v Actually I solved 1, the rest 2 was from your debugging skill B|

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

So... maybe learn about complexity :)

FYI — you can work on other problem while the first one is running.

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

    Yes, now I know quite a bit about complexity :)

    Hmm, sure but I was so novice and eager to see my results then, I waited for my program to finish executing :)

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

Correct me if i'm wrong, but shouldn't an O(n^6) algorithm for n <= 100 take 16 minute-ish to run on a typical computer?

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

    166 min, close to 3 hours. And who knows what other disasters had he put on that code :v

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

      Maybe the constant factor was too high :v

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

      "typical computer" can handle 10^9 operations, not 10^8. So it should be closer to 16 minutes than to 160.

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

        Umm there were multiple test cases :/ And my old pc was quite slow when executing code I don't know why :/

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

    I'm sorry I wrote it wrong here :( Actually the code was O(n^3) and n was <=10000.

    So the overall time required is the same. What I could remember was 10^18 only :v The post is edited sincere apology for giving you wrong information at first. :)

    → Reply