Lately

To be updating the blog, I'll post about things I've been doing lately.

As South America ICPC Regionals are getting closer, my studying time for this competition is raising. I'm currently putting more effort in my weak points (probability/geometry/string). I'm also a bit unquiet though the possibility that one of the strongest universities in ICPC is going to compete in our sub-regionals, nothing is confirmed, but I'm anxious, whether it proves to be true or not, I'll keep up my study basis.

As an intern for almost 2 years, where still dealing with pearl and catalyst framework along with other things (my focus is in the server side of this project) and now, with a few more modules to work with openssl to certificate authority purposes.

I' really trying to get back to my TopCoder rounds actively but I doesn't feel ready yet for a continuous DIV 1 contests run, so, I'll probably keep studying hard on DIV 1 problems for a time.

As a matter of curiosity, I've been using Manjaro Linux for about 3 months, it's my first 'rolling-release' experience and it's been pleasure. Manjaro is based in arch-linux, which obligates me to learn more about linux in it's fullness.

Bye

Topcoder DIV1 - A dream became true

I can surely remember the fist time I logged in the topcoder applet, actually I was looking for a new game to play, but I realized it was problem solving platform, as I had a Java 'How to program' book I bought 2 years earlier. This years were full of study and effort, trying to reach the barrier of a weak math background and a non-existent algorithmic thinking. Almost 4 years after it, I decided to take part in SRM 609. As after full plate of fish for the lunch, I turned up my notebook on and registered.

As a new strategy, I'll post the links to the problems statements here, to be faster in explaining solutions right to the point. 

MagicalStringDiv2: 

The 250 problem was a piece of cake, a simple simulation doing what the statement asks. Iterate over the string, if the index is lower the the middle of the string and the symbol is '<' or the index is above string's middle and it's '>', one have to increase the answer.
Link
 

PackingBallsDiv2: 

The problem asks for the minimum number of packages to wrap balls, some people managed to solve this problem in a greedy manner, as I already had a lot of issues trying greedy approaches in 500 problems, the classic dynamic programming was my first choice, using 'the minimum number of packages to pack R, G and B balls' as a state, then we can roll states recursively or in a iterative manner trying all the possible outcomes for the current state.

Link

VocaloidsAndSongs: 

The weird fact in this problem is that it's also solvable with dynamic programming, and it states are very close to the 500 problems too. It a counting problem with big numbers, requiring mod operations, this one is also 'do what statement asks' but do carefully, it's easy to make mistakes with this 'mod' operations.
Link


So thats it, thanks for reading, comments are welcome.

yet another promise

I think all my post contains messages telling that I'll be posting things more often, but it never happens. I'm back here to a quick update, I'm optimist to be very close to Div 1 in both TopCoder and Codeforces and expecting to make it as soon as possible. I'm also studying for a research paper, so I'm currently very busy. That's it.

Summer Training Camp

It's been a time since I don't post anything here, I've been participating actively in competitions, but seeing so more elaborated editorials floating around makes me less motivated to write. Within a few hours I'll be leaving for a 2 weeks training camp in Campinas, the second largest city in São Paulo. I'm looking forward to have a good time there and improve my coding skills, as well as posting updates about what's going on there.

SRM 594

Last Thursday's SRM was a rather unusual round, I don't know yet whether I made an improvement in my coding skills or both 250 and 500 problems were easier than usual and 1000 was harder than usual, with big constraints and xor operations, so will write the ones I managed to solve.

LittleElephantAndBallsAgain - 250

Given a string composed of 'R', 'G' or 'B', the problem asks for the minimum number of border removals to make the string with only one kind of character. As I'm in a dynamic programming moment, I ended up with a dp solution, stating the minimum value of a left removal or a right removal, as my code follows, but there's ways easier to code solution. Imagine that the string is composed of only non sequential characters ("RGBRGB") the obvious answer is (|string.length| - 1). Using a string ("RGBBBRG") as an example, i'ts clear that the best option is to remove both the prefix "RG" and the suffix "RG" to make a string containing only 'B' characters. With this in mind, it's clear that the best answer will be always (|string.length| - |length of the longest sub string with equal characters|).

My solution complexity: O(n^2)
Best solution complexity: O(n)

LittleElephantAndIntervalsDiv2 - 500

Given a sequence of |M| white balls and |N| intervals of the sequence to be painted of black of white, the problem asks the return the number of different sequences after |N| paints. With low constraints (N < 10 and M < 100), a complete search was clearly feasible. But with and clever idea, you can see that there's a finite number of balls to be painted, counting the number of balls that can be painted, we know that for them, there are 2 possible outcomes, paint black or white, resulting as (2^(|balls possibly painted|)).

My solution complexity: O(2^n)

Best solution complexity: O(n * log(n))

About SRM 585

Hello, competition is over and ratings started to change, I increased + 72 points, make me closer than ever to DIV 1. I'm quite excited.

LISNumberDivTwo:

The problem was pretty straightforward, it asked for the number of contiguous strictly increasing sub sequences. I unfortunately waste so many time coding a simple solution for this problem, thus, I managed to earn only 236.31 in a simple problem as this one.


TrafficCongestionDivTwo:

This problem required more analysis. The statement asks for the minimum number of 'cars' to be inserted in a complete binary tree, such that each car has a path (a paths can be empty) and no car paths intersect and each vertex must be visited by a car. As the problem statement illustration suggests, the optimal solution is to make from bottom to top, each card has a path of size 2, leaving a leaf note to a 1 step higher node and then to another leaf.

EnclosingTriangleColorful:

This problem is a tricky one, I managed to solve if in contest, but with a very unfeasible solution O(2^4 * (M - 2)^3 + (N log(N)). I'm trying to get a better solution that will be posted here.

Closer

Hi, I'm currently writing this post while finish some details in my tomorrow's presentation and watches the gazettE's last DVD. It's been a busy month, I didn't post anything about programming and even broke my compromise to solve at least 1 'medium' problem a day.

I really hope to be more active here in July, along to warm-up to the Brazil regional which will'be held in September, and probably to post about other topics besides programming competitions;