Today I just learned a new amazing algorithm. It's called Manacher's algorithm, the algorithm that finds the longest palindromic substring in linear time. Previously, I never thought that it can be done faster than O(N^2) time complexity (by dynamic programming). I felt really impressive after reading this blog and knew that this algorithm was found in 1975 :) So I wanna share it.
Link: Manacher's algorithm
Sunday, July 21, 2013
Sunday, June 23, 2013
Right Under My Nose
This morning, I participated in Codeforces Round #189. It's an online programming contest for Division 1 users as usual. This contest seems crucial for me, because if I didn't do well enough, my rating would decrease and it can cause me to fall into Division 2 which I really didn't want it obviously. I'd been going back and forth between Division 1 and 2 for a while until I got improved and my skill now is just over Division 2. So I've managed to stay in Division 1 for quite a long time (I guess) and I'm trying to turn to Yellow Rating which is the next step.
Even though I've been participating in Division 1 many times, I still ephemerally got nervous because of all the pressure from competition and the fact that I can't miss it. So my plan, the same as every other times, is to start solving problem A, B, then C. There are 5 problems, but the Problem D, E are often too hard for me. Being able to solve 2-3 problems in this level of difficulty within 2-hour contest is an achivement ...well at least in my skill level right now. After the time counted down to 00.00, the competition started. I immediately read Problem A. The problem wasn't too long. I understood it in just a moment. The problem seemed a little complicated. It had to deal with XOR operation. I knew that I could solve it, so I started thinking about the possible solution. It took me a while to think, code, check for bugs and submit it. During that time, I got circuitously nervous again, because I might spent too much time to solve A and the longer time I spent, the less score I got. I was always careful with Problem A and wanted to submit it only one time and get accepted to avoid the penalty point for a wrong submission. At around 40 minutes of the contest, I submitted it and it passed the pretests. I knew that solving A in 40 minutes wasn't good enough, but if I could solve B and/or C. My rank will be good enough. So let's continue to solve B.
Problem B was very short and easy to understand, but it's hard and sort of an ad-hoc problem. I spent 30 minutes to code the algorithm that I thought it's correct. Unfortunately my algorithm didn't work for some special cases. So it's time for me to decide whether I should continue with this problem or read Problem C. I looked at the scoreboard, and some people did C instead of B. It might be somehow easier, so I read C. Problem C statement is a little confusing, so I stopped reading it and went back to do B. I thought that it's better to fix the bug in B than start doing a new problem (considering about the time I have left). I have a bad habit that if I can't solve an easier problem, I don't want to go and solve the harder one. But it's real misthought here. A problem that is supposed to be harder in general might be easier for me...who knows?...especially in the competition like this.
Finally the time's up. I didn't even solve B in time. Thus, my rating is doubtlessly down, but fortunately I'm still in Division 1. After that I continued to code B and got it accepted. I read problem C and I suddenly felt really sad. After finishing reading it, I knew how to solve it for sure. It needed Convex Hull Trick idea to solve and I just learned it. I was depressed, because I didn't finish reading it during the contest, otherwise I would be able to solve it! This is one of the mistakes that I need not to forget that I should read new problems when I'm stuck. Well, as having been said, I will try to do better next time! I won't hail this mistake again.
Even though I've been participating in Division 1 many times, I still ephemerally got nervous because of all the pressure from competition and the fact that I can't miss it. So my plan, the same as every other times, is to start solving problem A, B, then C. There are 5 problems, but the Problem D, E are often too hard for me. Being able to solve 2-3 problems in this level of difficulty within 2-hour contest is an achivement ...well at least in my skill level right now. After the time counted down to 00.00, the competition started. I immediately read Problem A. The problem wasn't too long. I understood it in just a moment. The problem seemed a little complicated. It had to deal with XOR operation. I knew that I could solve it, so I started thinking about the possible solution. It took me a while to think, code, check for bugs and submit it. During that time, I got circuitously nervous again, because I might spent too much time to solve A and the longer time I spent, the less score I got. I was always careful with Problem A and wanted to submit it only one time and get accepted to avoid the penalty point for a wrong submission. At around 40 minutes of the contest, I submitted it and it passed the pretests. I knew that solving A in 40 minutes wasn't good enough, but if I could solve B and/or C. My rank will be good enough. So let's continue to solve B.
Problem B was very short and easy to understand, but it's hard and sort of an ad-hoc problem. I spent 30 minutes to code the algorithm that I thought it's correct. Unfortunately my algorithm didn't work for some special cases. So it's time for me to decide whether I should continue with this problem or read Problem C. I looked at the scoreboard, and some people did C instead of B. It might be somehow easier, so I read C. Problem C statement is a little confusing, so I stopped reading it and went back to do B. I thought that it's better to fix the bug in B than start doing a new problem (considering about the time I have left). I have a bad habit that if I can't solve an easier problem, I don't want to go and solve the harder one. But it's real misthought here. A problem that is supposed to be harder in general might be easier for me...who knows?...especially in the competition like this.
Finally the time's up. I didn't even solve B in time. Thus, my rating is doubtlessly down, but fortunately I'm still in Division 1. After that I continued to code B and got it accepted. I read problem C and I suddenly felt really sad. After finishing reading it, I knew how to solve it for sure. It needed Convex Hull Trick idea to solve and I just learned it. I was depressed, because I didn't finish reading it during the contest, otherwise I would be able to solve it! This is one of the mistakes that I need not to forget that I should read new problems when I'm stuck. Well, as having been said, I will try to do better next time! I won't hail this mistake again.
Subscribe to:
Posts (Atom)