The IEEEXtreme Experience
Yes, we’re gonna talk about competitive programming. Quite a controversial topic but I do like doing it sometimes. I’m not that serious of a competitor, but I always liked solving problems. I’m not going to explain fully what competitive programming is, but let’s just say It’s a type of mind sports where you try to solve problems by creating programs.
The most prestigious and famous competitive programming competition in the world is probably ICPC World Finals. ICPC is definitely the one competition all competitive programmers always know (outside of IOI anyway, but that’s only for highschoolers). Today I’m gonna talk about a different competition, Namely, IEEEXtreme.
What is IEEEXtreme?
IEEEXtreme might seem like yet another competitive programming competition. But unlike most of its counterparts, IEEEXtreme lasts for 24 hours, meaning you need to code for 24 hours straight! 🤯 (well, not necessarily but more on that later). In my country it starts at 7 AM and ends at 7 AM the next morning. They give out 1-2 new problems every hour so you can’t really speedrun the whole problem set (might be more difficult than doing them one by one every hour to be honest).
IEEEXtreme 14 Experience
My friends and I registered for this year’s IEEEXtreme 14.0. For me it was my first ever IEEEXtreme. The problems were quite interesting, here I’m going to share about the problems that I attempted and my thoughts on them.
Problems
Problem 1: Mosaic Decoration I
This is pretty much a bonus problem, not interesting by any means.
Problem 2: IEEEXplore Indexing
Ah, the dreaded implementation heavy problem. I only got around 85% on the score, and after that my friend rewrote the solution and got accepted.
Problem 9: Rotational Lights
Now THIS is one interesting problem, the constraints of the problem made it super challenging to guess what’s the expected time complexity of the solution should be. The idea of the solution is to notice that if the list of difference between positions on the circle is periodic, then the answer is the sum of differences in 1 period minus 1. You can easily find the maximum length period by factoring the length of the array. And the constraint on T doesn’t even matter since it doesn’t contribute to anything.
Problem 12: Non-Overlapping Palindromes
Probably my favorite problem from the whole set. The problem statement is really simple, anyone would probably understand what it’s asking for after reading it once or twice. The tricky part is to actually calculate it.
To solve this problem easily, we will need to precompute the maximum length of any palindromes centered at a certain position (both even and odd palindrome) and that can be calculated in a straightforward manner in linear time using Manacher’s Algorithm.
After that you need to precompute another array, it’s sort of like a DP (Dynamic Programming) where you check if you can get a more optimal solution from the previous solution. The array will return the maximum palindrome length that starts at that particular position. From here, you can just calculate it as a suffix. And then loop through all the positions and calculate the rest using maximum suffix and you will get the answer. All of the algorithms mentioned here are linear hence the total time complexity of the solution is also linear.
Problem 17: ARM Constant Multiplication
This problem reminded me of computer architecture class that I took last semester. I think this is a really interesting take on a problem’s scoring system since the score can be partial. The score depends on the number of steps that your algorithm generated for a particular number. Overall I managed to only fit in a score of around 40%. My basic idea is to represent a number as bits and shift the number accordingly, the greedy idea is to then check the number of 1s and 0s and calculate which of them is bigger.
Problem 24: Coin Collector
I didn’t really know how to solve this one (I still don’t), I just tried a random greedy strategy and only got a score of 17%.
Problem 25: Mosaic Decoration III
Another interesting problem, the idea is to only try the first base pattern on the top left of the grid. and thenshift it accordingly while also calculating the occurence of the color on the whole grid.
Overall, I liked the contest. The whole code for 24 hours straight theme is pretty intriguing at first, but since this is a team competition we can just take turn if one of us needs to sleep for a bit. So yes, we didn’t exactly code for 24 hours straight. But hey, it’s always fun to tell people that 😉.