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 :)
today he solved 3 problems (was in my team) :D Great improvement
Thanks mate :v Actually I solved 1, the rest 2 was from your debugging skill B|
So... maybe learn about complexity :)
FYI — you can work on other problem while the first one is running.
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 :)
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?
166 min, close to 3 hours. And who knows what other disasters had he put on that code :v
Maybe the constant factor was too high :v
"typical computer" can handle 10^9 operations, not 10^8. So it should be closer to 16 minutes than to 160.
Umm there were multiple test cases :/ And my old pc was quite slow when executing code I don't know why :/
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. :)